Трансляция выражений в компиляторе С0
В компиляторе С0 выражения транслируются методом стека с приоритетами [1, 2, 6, 16], который реализован в подпрограмме virag. Задача этой подпрограммы - определение порядка выполнения операций выражения.
Выражение рассматривается как последовательность секций, состоящих из терма (операнда), который может отсутствовать, и ограничителя:
выражение ::= секция...
секция ::= [терм] ограничитель
терм ::= число | имя
ограничитель ::= ( | ) | , | ; | = | == | != |
< | > | <= | >= | + | - | * | / | %
К ограничителям относятся знаки операций, скобки, а также запятая, разделяющая фактические параметры вызова функции, и точка с запятой, обозначающая конец оператора-выражения. Ограничителям присвоены приоритеты по старшинству операций, как в языке С (см. табл.). Запятая и точка с запятой играют роль закрывающей скобки, соответственно, для фактического параметра и выражения в целом и имеют такой же приоритет.
Для определения порядка выполнения операций используется стек из глобальных параллельных массивов: st, sz, sogz, spr с указателем i.
Элемент стека содержит секцию: терм, ограничитель и его приоритет. В компиляторе С0 они хранятся в виде четырех значений: st [i] - тип терма (0 - отсутствующий терм, 1 - число, 3 - имя, 4 - число в стеке выполнения: результат выполнения операции); sz[i]- значение терма (для имени указывается его позиция в таблице имен; у пустого терма и терма типа 4 значение отсутствует); sogr[i] и spr[i] – ограничитель и приоритет.
|
|
|
Транслятор С0 сочетает компиляцию с интерпретацией. Если операнды являются константами, то операция интерпретируется, т.е. выполняется, и в стек трансляции помещается результат операции. В противном случае операция компилируется, т. е. генерируется (выводится в объектную программу) реализующая операцию группа команд, а в стек трансляции записывается указание о том, что результат операции будет находиться в стеке выполнения (типу терма st[i-1] присваивается 4).
При этом подпрограмма zopreg генерирует различные команды загрузки операнда (терма) в регистр АХ или ВХ в зависимости от типа, т.е. местонахождения терма.
Выталкивание открывающей скобки выполняется подпрограммой vitsk. Если перед открывающей скобкой имеется имя функции, то при ее выталкивании генерируется команда вызова этой функции с предварительной записью в стек ее параметра, если это необходимо.
Выталкивание открывающей скобки подвыражения (перед которой отсутствует имя функции) сводится к продвижению находящейся в верхушке стека информации о значении подвыражения на одну позицию вглубь стека.
Трансляция фрагмента программы
|
|
|
Рассмотрим пример трансляции фрагмента программы "Коды символов".
На рис. 2 показана таблица имен при трансляции описания функции kod, а на рис. 3 - кадр стека функции kod.
kod (x,baza)
{ int y;
if ((y = x/baza) != 0)
kod (y,baza);
putchar (x%baza + 48);
}
int c;
main ()
{ c=0;
while (c!=13)
{ c = getchar ();
putchar (61); Рис.2. Таблица имен при
kod (c,10); трансляции функции kod
putchar (61); kod (c,8);
}
}
Трансляция этой программы происходит следующим образом.
Для трансляции описания функции kod программа main вызывает подпрограмму oprfun, которая заносит в таблицу имя функции kod, ee формальные параметры х, baza и локальную переменную y и определяет их смещения в кадре стека. После этого Рис.3. Кадр стека функции kod
на весь период трансляции функции kod, таблица имен приобретает вид, показанный на рис. 2.
На рис. 4 приведена трассировочная таблица трансляции оператора
if ((y = x / baza) != 0) kod (y,baza);.
При трансляции этого оператора вызванная из oprfun подпрограмма poslop вызывает подпрограмму operatr для трансляции оператора if.
В свою очередь, operatr вызывает подпрограмму virag для трансляции выражения-условия, а затем (рекурсивно) вызывает подпрограмму operatr, которая вызывает virag для трансляции вложенного оператора-выражения.
|
|
|
Программа virag транслирует выражение по секциям. Обработка секции состоит из трех шагов.
1. Если предыдущий ограничитель не является закрывающей скобкой, то читается терм и записывается в стек (для этого в стек вталкивается новый элемент). Дело в том, что после закрывающей скобки секция никогда не содержит терма. Роль терма для нее играет уже находящаяся в стеке информация о значении заключенного в скобки подвыражения.
2. Читается ограничитель секции. Если он не является открывающей скобкой, то его приоритет сравнивается с приоритетом последнего ограничителя, помещенного в стек (если в стеке есть ограничители). Пока приоритет текущего ограничителя меньше приоритета последнего ограничителя стека,
| leksema = if ogr = prior = | ( ( 0 | ( ( 0 | y = = 2 | x / / 6 | baza ) ) 1 | |||
| st, sz, sogr, spr= | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 |
| 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 4 | ||
| 3,4,=,2 | 3,4,=,2 | 3,4,=,2 | 3,4,=,2 | 4 | ||||
| 3,2, /,6 | 3,2, /,6 | 4 | ||||||
| 3,3 |
|
|
|
Объектный код, генерируемый при MOV BX,4[BP]
выталкивании операции из стека:MOV AX,6[BP]
CWD POP AX
IDIV BX MOV -2[BP],AX
PUSH AX PUSH AX
Продолжение таблицы вправо:
| != != 3 | 0 ) ) 1 | kod ( ( 0 | y , , 1 | baza ) ) 1 | ; ; 1 | ||||
| 0, , (, 0 | 0, , (, 0 | 0, , (, 0 | 4 | 3,1,(,0 | 3,1,(,0 | 3,1,(,0 | 4 | ||
| 4, ,!=,3 | 4, ,!=,3 | 4 | 3,4 | 3,3 | |||||
| 1,0 |
MOV AX,-2[BP] CC_2:
MOV BX,0 POP AX PUSH AX
POP AX TEST AX,AX
CMP AX,BX JNZ CC_3 MOV AX,4[BP]
MOV AX,1 JMP CC_2 PUSH AX
JNE CC_1 CC_3: CALL KOD
SUB AX,AX
CC_1:
PUSH AX
Примечание: В отличие от пособия [1], содержимое стека показано
подробно: в числовом виде.
Рис.4. Трассировочная таблица трансляции оператора
if ((y = x / baza) != 0) kod (y,baza);
этот более приоритетный ограничитель выталкивается из стека. В случае равенства приоритетов выталкивание происходит только тогда, когда соответствующие операции должны выполняться слева направо (как сложение и вычитание или умножение и деление), а не справа налево, как, например, присваивание. При выталкивании ограничителя из стека реализуется операция, соответствующая этому ограничителю. Если операндами операции являются константы, то она выполняется (интерпретируется). В противном случае операция компилируется, т. е. в выходную программу выводится объектный код операции.
3. Если ограничитель не является закрывающей скобкой, то по окончании цикла выталкивания он записывается в последний элемент стека (новый элемент не создается). Для ускорения работы туда же помещается его приоритет. Закрывающая скобка в стек не записывается. Вместо этого из стека выталкивается соответствующая открывающая скобка. При выталкивании открывающей скобки подвыражения (перед которой терм отсутствует) терм из вершины стека (информация о значении подвыражения) продвигается на один элемент вглубь стека. Если же открывающая скобка находится перед списком параметров вызова функции (ее термом является имя функции), то при ее выталкивании в выходной файл выводится команда вызова этой функции CALL. Если функция имеет параметр-выражение, то к этому моменту в выходную программу уже будет помещен объектный код этого выражения, т. е. команды, вычисляющие значение параметра и вталкивающие его в стек. В этом случае последний терм стека имеет тип 4 (число, помещенное в стек выполнения). В противном случае параметр не содержит операций (представляет собой константу или переменную). Тогда генерируются команды, помещающие его значение в стек. Запятая разделяет параметры вызова функции и служит как бы закрывающей скобкой предыдущего параметра и открывающей скобкой следующего за ней параметра. Поэтому она обрабатывается подобно закрывающей скобке, но открывающая скобка не выталкивается, а остается в стеке. Таким же образом обрабатывается точка с запятой.
Порядок выполнения работы
1. Пользуясь текстом транслятора и описанием его функционирования, изучить назначение и алгоритмы работы всех его подпрограмм.
2. Изобразить содержимое таблицы имен и составить трассировочную таблицу трансляции указанного преподавателем фрагмента программы (с разрешения преподавателя, можно самостоятельно выбрать из программы, составленной в лабораторной работе 1, фрагмент приблизительно такой же сложности по числу операций, как в приведенном выше примере).
3. Выполняя транслятор в пошаговом режиме в интегрированной системе Turbo-C, можно проследить за процессом трансляции выбранного фрагмента программы (это делать не обязательно).
4. Составить отчет о работе, включающий исходную и объектную программы, содержимое таблицы имен и трассировочную таблицу трансляции заданного фрагмента программы.
4. Сдать работу, ответив на вопросы преподавателя по транслятору С0, алгоритмам работы его подпрограмм, процессу трансляции заданной программы.
Контрольные вопросы и упражнения
1. Какие подпрограммы транслятора C0 выполняют лексический анализ?
2. Какие подпрограммы транслятора C0 выполняют синтаксический анализ?
3. Какие подпрограммы транслятора C0 выполняют семантический анализ?
4. Какие подпрограммы транслятора C0 выполняют генерацию объектного кода?
5. Какие подпрограммы транслятора C0 занимаются оптимизацией программы?
6. Какие подпрограммы транслятора C0 занимаются трансляцией выражений?
7. Какие подпрограммы транслятора C0 выполняют синтаксический анализ?
8. Какие подпрограммы транслятора C0 занимаются интерпретацией программы?
9. Какие подпрограммы транслятора C0 изменятся при изменении структуры кадра стека?
Лабораторная работа № 3
Дата добавления: 2019-02-12; просмотров: 254; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!