Проектирование трансляторов
│ └────┬──────┘ │
│ │ │
│ ___│___ │
│ / │3 ┌─────────┬──┐ │
│ / └── Да │ Конец │10│ │
│ / R равно @ ─────>┤ работы └──┤ │
│ i / │ алгорита │ │
│ / └────────────┘ │
│ _______/ │
│ │ │
│ │ │
└───────────────────>─┤ │
┌───────────────────>─┤ Нет │
│ ___│____ │
│ / │4 │
│ / └── Нет │
│ / R > L __________________________│
│ i k /
│ ? /
│ ________/
│ Да│
│ ├<────────────────────┐
│ ____│______ │
│ / │5 │
│ / └── ┌─────┴───┬─┐
│ / R = R ______│ │6│
│ j-1 j / Да │ j:=j-1 └─┤
│ / │ │
│ ___________/ └───────────┘
│ │Нет
│ ┌────────┴─────┬─┐
│ │ │7│
│ │ U < R ... R└─┤
│ │ j i │
│ └────────┬───────┘
│ │
│ │
│ ┌───────┴─────┬─┐
│ │ │8│
│ │ Переход на └─┤
│ │ семантические │
│ │ подпрограммы │
│ │ │
│ └───────┬───────┘
│ │
│ ┌───────┴────┬─┐
│ │ i:=j │9│
└───────────────┤ R :=u └─┤
│ i │
└──────────────┘
Рис. 1. Блок-схема алгоритма свертывания
В начале анализа строки в верхнюю ячейку магазина записы-
вается первый символ программы, т.е. символ "@" (блок 1).
Затем находится самый правый символ самой левой свертывае-
мой части строки (блок 4). Для этого по матрице предшествования,
которая составляется заранее, проверяют отношения предшествова-
ния между символом, находящимся в верхней ячейке магазина Ri, и
очередным входным символом строки Lk. Если условие Ri > Lk не вы-
полняется, то очередной входной символ записывается в верхушку
магазина (блок 2) и процесс продолжается до тех пор, пока не бу-
дет выполнено условие Ri > Lk, т. е. не будет найден самый пра-
вый символ самой левой свертываемой части строки.
Затем находится самый левый символ этой свертываемой части
строки. Для этого проверяется отношение предшествования между
каждой парой символов Rj-1 = Rj, записанных в магазине (блоки 5 и
6). Нарушение условия Ri = Rj означает, что свертываемая часть
строки кончилась и последовательность символов Rj...Ri есть са-
мая левая свертываемая часть строки.
У каждого нетерминального символа может быть несколько са-
мых левых и самых правых символов.
По таблице, имеющейся в трансляторе, в которой записаны
правила свертывания, производится свертывание (блок 7) и управ-
ление передается на соответствующую семантическую подпрограмму.
Семантическая подпрограмма генерирует программу на выходном язы-
ке, соответствующую данному синтаксическому правилу (блок 8).
После того, как генерирование соответствующего куска выход-
ной программы закончено, символы Rj...Ri "выталкиваются" из мага-
зина и в его верхнюю ячейку записывается символ u (блок 9).
Процесс продолжается до тех пор, пока в верхней ячейке мага-
зина не будет обнаружен символ "@" (блок 3), определяющий конец
программы.
Для анализа ошибок в алгоритм включены следующие блоки:
Блок 11 проверяет, могут ли символы Rj и Lk стоять в строке
рядом. Если в матрице предшествования (i,j)-ый элемент пуст (знак
_), то символы Si и Sj стоять рядом не могут и осуществляется пе-
реход к блоку 15. Иначе управление передается в блок 4.
Блок 12 проверяет значение величины j: если j=1, то должно
производиться сравнение с символом "@", что по алгоритму анализа
вообще быть не может. В этом случае переход к блоку 15. Если j не
равно 1, то переход к блоку 5.
Блок 13 проверяет, есть ли правило с правой частью Rj...Ri в
грамматике языка. Если да,переход к блоку 7, иначе - к блоку 15.