- •6. Генерация команд в компиляторе 44
- •1. Языки и грамматики
- •1.1. Язык как множество
- •1.2. Порождающая грамматика
- •1.3. Процесс порождения
- •1.4. Классификация грамматик по Хомскому
- •1.5. Классификация языков по Хомскому
- •1.6. Задача распознавания цепочек языка
- •2. Принципы трансляции языков программирования
- •3. Лексический анализ
- •3.1. Конечный автомат
- •3.2. Построение детерминированного конечного автомата
- •3.3. Недетерминированный конечный автомат
- •3.4. Преобразование неоднозначной а-грамматики к однозначной
- •3.5. Удаление из грамматики бесполезных нетерминалов
- •3.6. Лексический анализатор
- •4. Синтаксический анализ
- •4.1. Дерево порождения для кс-грамматики
- •4.2. Автомат с магазинной памятью
- •4.4. Левая рекурсия и ее устранение
- •4.5. Преобразование кс-грамматики к обобщенной нормальной форме Грейбах
- •4.6. Детерминированный ll-разбор
- •5. Обратная польская строка, как промежуточная форма программы
- •5.1. Обратная польская строка для арифметических выражений
- •5.2. Генерация опс для арифметических выражений
- •5.3. Вычисление опс для присваиваний и арифметических выражений с индексами
- •5.4. Генерация опс для присваиваний и арифметических выражений с индексами
- •5.5. Опс для условных, циклических и составных операторов
- •5.6. Опс для стандартных операторов
- •5.7. Распределение памяти и описание переменных
- •5.8. Обработка ошибок
- •6. Генерация команд в компиляторе
- •6.1. Распределение памяти при генерации команд
- •6.2. Генерация команд для присваиваний и арифметических выражений
- •6.3. Генерация команд с индексными выражениями
- •6.4. Генерация команд сравнения и перехода
5.5. Опс для условных, циклических и составных операторов
В условных и циклических операторах должно вычисляться логическое выражение. В самом простом случае это операция сравнения двух арифметических выражений. Всего операций сравнения шесть: =, ≠, <, >, <=, >=. ОПС для любой операции сравнения записывается и выполняется так же, как арифметическая операция, отличие лишь в том, что результат операции сравнения – логическое значение true или false. Далее рассмотрим пример грамматики с условными операторами и генерацию соответствующей ОПС.
Пример 15. Расширим грамматику присваиваний и арифметических выражений с индексами для одно- и двумерных массивов (A – начальный нетерминал), рассмотренную в примере 14.
Порождающее правило для выражения, содержащего сравнение, можно определить с помощью общего обозначения всей группы операций сравнения через <c>:
C → S<c>S
Вначале преобразуем это правило, добавив новый нетерминал D, для того, чтобы при входном символе <c> была замена в стеке нетерминала D, на правую часть, начинающуюся с конкретной операции сравнения:
C → SD
D → <c>S
Затем первое правило преобразуем к нормальной форме Грейбах:
C → (S)VUD | aHVUD
При работе анализатора, если верхний символ в магазине будет C, то при входном символе открывающей скобке в магазин будет копироваться последовательность: (S)VUD, а при входном символе имя или константа – последовательность: aHVUD. Соответственно в дополнительный магазин будет записываться: □□□□□□ или a□□□□.
При верхнем символе D в магазине и при входном символе <c> в магазин будет копироваться: <c>S□, а в дополнительный магазин: □□<c>, для того, чтобы операция сравнения записывалась в ОПС после того, как в ОПС полностью сгенерирован второй операнд.
Условный оператор в полной и сокращенной формах можно определить порождающими правилами, начинающимися с нетерминала A:
A → if C then AE
E → else A | λ
Эти правила позволяют записывать не только условные операторы с присваиваниями (так как нетерминал A может порождать присваивания), но и вложенные условные операторы.
При работе анализатора, если верхний символ в магазине будет A, то при входном символе if в магазин будет копироваться последовательность: if C then AE, а в дополнительный магазин: □□<1>□□. Здесь и далее обозначение <1>, <2> и т.д. означает номер семантической программы, генерирующей ОПС, и которая будет выполняться при выталкивании этого элемента из дополнительного магазина.
При верхнем символе E в магазине и при входном символе else в магазин будет копироваться: else A□, а в дополнительный магазин: <2>□<3>. Если же будет другой входной символ (не else), то в магазин будет копироваться: □, а в дополнительный магазин: <3>.
Семантические программы будут генерировать такие операнды, как метки (<m1>, <m2> и т.д.), и операции условного (<jf> – переход при условии false) и безусловного перехода (<j>). Метка представляет собой номер элемента в генерируемой ОПС, куда будет производиться переход при выполнении операции перехода. Для такой генерации будет использоваться еще один магазин – магазин меток.
Рассмотрим эти семантические программы. В них будет использована переменная k – счетчик (номер) очередного генерируемого элемента ОПС. Этот счетчик увеличивается на 1 всякий раз, как только генерируется очередной элемент ОПС.
Программа <1>.
1. В магазин меток записывается k.
2. В ОПС записывается пустой элемент – место для будущей метки.
3. В ОПС записывается операция <jf> – переход при условии false.
Программа <2>.
1. Через верхний элемент магазина меток, как ссылку на ранее заготовленное место для метки, записывается k + 2.
2. В магазин меток записывается k.
3. В ОПС записывается пустой элемент – место для будущей метки.
4. В ОПС записывается операция <j> – безусловный переход.
Программа <3>.
1. Через верхний элемент магазина меток, как ссылку на ранее заготовленное место для метки, записывается k.
Конец программ.
Если, например, на входе будет цепочка:
if a>b then a:=b else b:=a ┴
то будет сгенерирована следующая ОПС:
a b > <m1> <jf> a b := <m2> <j> b a :=
↑ ↑
<m1> <m2>
Пусть, например, a = 5, b = 2. Тогда при вычислении этой ОПС содержимое магазина интерпретатора будет изменяться таким образом:
-
a
b
Операция >
-
true
<m1>
Операция <jf> – перехода нет
-
a
b
Операция :=
-
<m2>
Операция <j> – переход есть
В результате получится a = 2, b = 2 (изменилось a).
Если же a = 2, b = 5, то вычисление будет таким:
-
a
b
Операция >
-
true
<m1>
Операция <jf> – переход есть
-
b
a
Операция :=
В результате получится a = 2, b = 2 (изменилось b).
Конец примера.
Рассмотрим пример грамматики с циклами и генерацию ОПС для них.
Пример 16. Расширим грамматику, рассмотренную в примере 15, задав цикл порождающим правилом, начинающимся с нетерминала A:
A → while C do A
При работе анализатора, если верхний символ в магазине будет A, то при входном символе while в магазин будет копироваться последовательность: while C do A□, а в дополнительный магазин: <4>□<1>□<5>.
Рассмотрим семантические программы <4> и <5>.
Программа <4>.
1. В магазин меток записывается k.
Программа <5>.
1. В ОПС записывается метка, значение для которой читается из магазина меток.
2. В ОПС записывается операция <j> – безусловный переход.
Конец семантических программ.
Если, например, на входе будет цепочка:
while a>b do a:=b ┴
то будет сгенерирована следующая ОПС:
a b > <m1> <jf> a b := <m0> <j>
↑ ↑
<m0> <m1>
Пусть, например, a = 5, b = 2. Тогда при вычислении этой ОПС содержимое магазина интерпретатора будет изменяться таким образом:
-
a
b
Операция >
-
true
<m1>
Операция <jf> – перехода нет
-
a
b
Операция :=
-
<m0>
Операция <j> – переход есть
-
a
b
Операция >
-
true
<m1>
Операция <jf> – переход есть
В результате получится a = 2, b = 2 (цикл выполнился один раз, и изменилось b).
Конец примера.
А теперь рассмотрим пример грамматики с составными операторами и генерацию ОПС для них.
Пример 17. Расширим грамматику, рассмотренную в примере 16, задав составной оператор порождающими правилами, начинающимися с нетерминала A:
A → begin Q end
Q → A ; Q | λ
Т.е. составной оператор представляет собой последовательность из произвольного числа таких операторов, как присваивание, условный, цикл, составной, которые записаны через точку с запятой и взяты в операторные скобки begin – end.
Вторую группу правил (для нетерминала Q) преобразуем к обобщенной нормальной форме Грейбах:
Q → aH := S ; Q | if C then AE ; Q | while C do A; Q | begin Q end A ; Q | λ
При работе анализатора, если верхний символ в магазине будет Q, то при входном символе begin в магазин будет копироваться последовательность: begin Q end ; Q, а в дополнительный магазин: □□□□□. Если же входной символ будет имя или константа, или if, или while, то в магазин будут копироваться последовательности, как для присваивания или условного оператора, или цикла, дополненные двумя символами: ; Q. В дополнительный магазин при этом будут копироваться соответствующие последовательности, дополненные двумя символами: □□.
Конец примера.