- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
6.3. Преобразование промежуточной программы в ассемблерный код
Фаза генерации кода так же как и предшествующие ей фазы, является процессом перевода промежуточной программы в объектную. Поэтому многие конструкции промежуточной программы могут быть преобразованы в последовательность кодов при помощи уже известной нам модели транслятора — МП-преобразователя, а также различных ее модификаций, в частности, МП - процессора. Кроме того, в качестве моделей могут использоваться различные схемы синтаксически управляемых переводов (СУ-схемы), реализуемые при помощи соответствующих алгоритмов генерации кода.
Чтобы дать некоторое представление об этих алгоритмах, мы вернемся к примеру, рассмотренному в п.1.1 и приведем алгоритм генерации кода для простых операторов присваивания, содержащих в правой части операции “+” и “*”. После обработки оператора такого типа, синтаксический анализатор формирует на выходе синтаксическое дерево, которое может иметь только три типа внутренних вершин — а, б и в соответственно (рис. 6.6).
Рис. 6.6
Так, для оператора присваивания S:= (A+B) *0.17
анализатор построит дерево, показанное на рис.6.7, и его внутренние вершины n3, n2, и n1 будут иметь типы а, б и в соответственно. Будем считать, что каждой вершине n дерева приписано целое число, называемое ее уровнем. Все листья дерева имеют уровень 0, непосредственные предки листьев — уровень 1 и т. д., как показано на рис. 6.7.
Р ис. 6.7
Свяжем с каждой внутренней вершиной n дерева цепочку кодов (ассемблерных команд) — С(n). Цепочка кодов будет иметь следующую интерпретацию:
1. Если n — вершина типа а, то такой вершине будет соответствовать цепочка С(n), которая вычисляет значение выражения, соответствующего правому поддереву, и помещает результат в ячейку соответствующей переменной, именем которой помечено левое поддерево.
2. Если n — вершина типа б или в, то цепочка LOAD C(n) будет содержать последовательность команд, которая засылает в регистр значение выражения, соответствующего поддереву, над которым доминирует вершина n.
Приведем теперь формальное описание алгоритма.
Алгоритм А (генерация ассемблерного кода).
Вход А (помеченное упорядоченное дерево, представляющее оператор присваивания с операциями “+” и “*”).
Выход А (ассемблерный код, вычисляющий этот оператор).
Описание А.
1. Обработать листья дерева:
а) если лист помечен “<пер>“, то соответствующий код этой вершины — это просто имя этой переменной , т.е.С(n) = имя;
б) если вершина помечена как <const>, то С(n) = const;
в) если вершина помечена =, *, +, то С(n) — пусто.
2. Обработать вершины уровня 1,затем вершины уровня 2 и т.д.:
а) если вершина имеет тип а, а ее прямые потомки — вершины n1,n2 и n3 , то будет сгенерирован такой код С(n):
LOAD C(n3), STORE C(n1);
б) если n — вершина типа б с прямыми потомками n1, n2 и n3, то будет сгенерирован такой код С(n):
C(n3); STORE $L; LOAD C(n1); ADD $L ;
в) если n - вершина типа в, то будет сгенерирован такой код: C(n3); STORE $L; LOAD C(n2); MPY $L.
Здесь $L обозначает имя временной ячейки, состоящее из символа $ и значения уровня вершины L.
В результате обработки дерева, показанного на рис. 6.7, на первом шаге А1 будут сформированы коды, соответствующие ячейкам: S, A, B, 0.17.
На втором шаге будут сформированы коды для внутренних вершин:
тип б C(n1)=B; STORE $1; LJAD A; ADD$1;
тип в C(n2)=0.17; STORE $2; LOAD B; STORE &1;
LOAD A;ADD$1; MPY $2;
тип а C(n3)=LOAD 0.17; STORE$2; LOAD B; STORE$1; LOAD A;ADD$1; MPY$2; STORE S.
Записывая каждый код с новой строки, получим:
LOAD 0.17
STORE $2
LOAD B
STORE $1
LOAD A
ADD $1
MPY $2
STORE S
В качестве упражнения получите ассемблерный код при помощи А для оператора S:=(A*B+C*D) *0.5.
Основы конструирования компиляторов
Учебное пособие
Редактор Н.А. Юшко
Темплан 1997г. ЛР №020417 12.02.92.
Подписано в печать 97. Формат 60x84 1/16.
Бумага тип № 2. Печать оперативная.
Усл.п.л. 4.65. Уч.-изд.л. 5.0 Усл. кр.-отт. 4.77.
Тираж 75 экз. Заказ . С 201.
Южно-Российский государственный технический университет
Типография ЮРГТУ.
Адрес университета и типографии:
346428, Новочеркасск, ул.Просвещения, 132