Реферат: Проектирование трансляторов

которая составляется заранее, проверяют отношения предшествова-

ния между символом, находящимся в верхней ячейке магазина 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)-ый элемент пуст (знак