- •Цель лабораторных работ:
- •Лабораторная работа № 1 разработка грамматики заданного языка.
- •Краткие теоретические сведения
- •Формы записи грамматики
- •Порядок выполнения работы
- •Требования к оформлению отчета
- •Основные контрольные вопросы
- •Лабораторная работа № 2 работа с таблицей символов Проектирование лексического анализатора
- •Краткие теоретические сведения
- •Требования к оформлению отчета
- •Основные контрольные вопросы
- •Лабораторная работа № 3 Синтаксический и семантический анализ. Построение простейшего дерева вывода
- •Краткие теоретические сведения
- •Порядок выполнения работы
- •Требования к оформлению отчета
- •Основные контрольные вопросы
- •Лабораторная работа № 4 Генерация и оптимизация объектного кода
- •Краткие теоретические сведения
- •1 Алгоритм генерации объектного кода по дереву вывода
- •Построение ассемблерного кода по дереву вывода
- •Построение списка триад по дереву вывода.
- •Оптимизация объектного кода методом свертки
- •Оптимизация объектного кода методом исключения лишних операций
- •Общий алгоритм генерации и оптимизации объектного кода
- •Порядок выполнения работы
- •Требования к оформлению отчета
- •Основные контрольные вопросы
- •Варианты заданий
- •Рекомендуемая литература
Построение ассемблерного кода по дереву вывода
В качестве языка ассемблера возьмем язык ассемблера процессоров типа Intel 80x86. При этом будем считать, что операнды могут быть помещены в 16-разрядные регистры процессора и в коде результирующей объектной программы могут использоваться регистры AX (аккумулятор) и DX (регистр данных), а также стек для хранения промежуточных результатов.
Тогда четырем формам текущего узла дерева будут соответствовать следующие фрагменты кода на языке ассемблера (табл. 5):
Таблица 5.
Преобразование типовых узлов дерева вывода в код на языке ассемблера
Вид узла дерева |
Результирующий код |
Примечание |
|
mov ax,oper1 act ax,oper2 |
act - команда соответствующей операции oper1,oper2 - операнды (листья дерева) |
|
Code(Узел 2) mov dx,ax mov ax,oper1 act ax,dx |
Узел 2 - нижележащий узел (не лист!) дерева Code(Узел 2) - код, порождаемый процедурой для нижележащего узла |
|
Code(Узел 2) act ax,oper2 |
Code(Узел 2) - код, порождаемый процедурой для нижележащего узла |
|
Code(Узел 2) push ax Code(Узел 3) mov dx,ax pop ax act ax,dx |
Code(Узел 2) - код, порождаемый процедурой для нижележащего узла Code(Узел 3) - код, порождаемый процедурой для нижележащего узла push и pop - команды сохранения результатов в стеке и извлечения результатов из стека |
Рассмотрим пример дерева вывода для выражения A := B*C + D - B*10 на рис. 5 и соответствующий ему фрагмент кода на языке ассемблера, построенный по описанным выше правилам (обратите внимание, что для операции присваивания используется отдельный код, не подпадающий под общие правила):
Рис. 5. Дерево
вывода для арифметического выражения.
mov A,ax ;операция присваивания
Шаг 2: Code(U3)
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Шаг 3: Code(U4)
add ax,D
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Шаг 4: mov ax,B
mul ax,C
add ax,D
push ax
Code(U5)
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Шаг 5: mov ax,B
mul ax,C
add ax,D
push ax
mov ax,B
mul ax,10
mov dx,ax
pop ax
sub ax,dx
mov A,ax ;операция присваивания
Полученный объектный код на языке ассемблера, очевидно, может быть оптимизирован, однако для его обработки требуются специальные (ориентированные именно на данный язык ассемблера) методы и структуры, учитывающие взаимосвязь операций. Кроме того, ориентация на определенный язык ассемблера сводит на нет универсальность метода. Так в приведенном примере используется команда mul, которая в ранних версиях процессоров фирмы Intel имеет ограничения на типы операндов, а следовательно, в универсальном компиляторе не может быть использована так, как в данном примере. Это потребует, чтобы генерация кода для узлов дерева шла в зависимости не только от операндов, но и от типа операции (даже в приведенном примере такую зависимость пришлось установить для операции присваивания).
Обычно такие проблемы решаются таким образом, что вместо команд непосредственно языка ассемблера используются команды некоторого близкого к нему промежуточного псевдокода. Большинство этих команд один в один отображаются затем в команды языка ассемблера, другие же однозначно преобразуются в фиксированную последовательность команд.