- •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. Генерация команд сравнения и перехода
4.6. Детерминированный ll-разбор
КС-грамматика, преобразованная к обобщенной нормальной форме Грейбах, допускает однозначный LL-разбор, если для каждой группы порождающих правил с одним и тем же нетерминалом в левой части правые части будут однозначно различимы по нескольким первым терминальным символам. В самом простом случае они должны различаться по одному символу, тогда на каждом шаге разбора проверяется на совпадение один верхний символ магазина (если он терминал) и очередной символ на входе. Такой разбор называется LL(1)-анализом, а алгоритм разбора – LL(1)-анализатором.
Будем считать, что входная цепочка символов, также как для лексического анализатора, всегда заканчивается ограничителем ┴. Для работы LL(1)-анализатора необходимо построить таблицу, в которой столбцы помечены терминальными символами (включая ┴), а строки – нетерминалами преобразованной грамматики. Для каждого из правил вида A → aγ, правая часть заносится на пересечение строки, помеченной нетерминалом A, и столбца, помеченного терминалом a. Если же правая часть правила пустая, то во все клетки строки, не занятые другими правилами, записывается λ.
До начала работы в магазин записывается ограничитель ┴ , а затем начальный нетерминал. На каждом шаге анализатор проверяет, допустим ли очередной входной символ, и если да, то выполняет одно из двух действий:
1) если на вершине магазина нетерминал, то, в зависимости от того, каков очередной входной символ, этот нетерминал заменяется символами правой части соответствующего правила, причем символы записываются в обратном порядке. Если для очередного входного символа в таблице записано λ, то нетерминал удаляется из магазина, а если в таблице пустая клетка, то анализатор прекращает цикл из-за ошибочного символа во входной цепочке;
2) если на вершине магазина терминал, то он сравнивается с очередным входным символом. При совпадении терминал удаляется из магазина и делается переход к следующему символу входной цепочки. При несовпадении анализатор прекращает цикл из-за ошибочного символа во входной цепочке.
Цикл прекращается, когда входная цепочка символов оказалась вся просмотрена. Если при этом магазин пуст, то входная цепочка символов считается распознанной, если не пуст – то нераспознанной.
Пример 8. Пусть задана грамматика простых арифметических выражений, преобразованная к обобщенной нормальной форме Грейбах:
S → (S)VU | aVU
U → + TU | λ
T → (S)V | aV
V → * FV | λ
F → (S) | a
В табл. 7 приведены действия LL(1)-анализатора.
Табл. 7
-
+
*
(
)
a
┴
S
(S)VU
aVU
U
+ TU
λ
λ
λ
λ
λ
T
(S)V
aV
V
λ
* FV
λ
λ
λ
λ
F
(S)
a
Пусть на вход анализатора поступает цепочка: a * (a + a) ┴ . Шаги работы анализатора представлены в табл. 8.
Табл. 8
-
№
шага
Входные
символы
Содержимое
магазина
Порождающее
правило
1
a*(a+a) ┴
S ┴
S → aVU
2
a*(a+a) ┴
aVU ┴
3
*(a+a) ┴
VU ┴
V → * FV
4
*(a+a) ┴
*FVU ┴
5
(a+a) ┴
FVU ┴
F → (S)
6
(a+a) ┴
(S)VU ┴
7
a+a) ┴
S)VU ┴
S → aVU
8
a+a) ┴
aVU)VU ┴
9
+a) ┴
VU)VU ┴
V → λ
10
+a) ┴
U)VU ┴
U → + TU
11
+a) ┴
+TU )VU ┴
12
a) ┴
TU )VU ┴
T → aV
13
a) ┴
aVU )VU ┴
14
) ┴
VU )VU ┴
V → λ
15
) ┴
U )VU ┴
U → λ
16
) ┴
)VU ┴
17
┴
VU ┴
V → λ
18
┴
U ┴
U → λ
19
┴
┴
Пусть на вход анализатора поступает ошибочная цепочка: a) ┴ . Шаги работы анализатора представлены в табл. 9.
Табл. 9
-
№
шага
Входные
символы
Содержимое
магазина
Порождающее
правило
1
a) ┴
S ┴
S → aVU
2
a) ┴
aVU ┴
3
) ┴
VU ┴
V → λ
4
) ┴
U ┴
U → λ
5
) ┴
┴
<ошибка>
Конец примера.