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

│

│ └────┬──────┘ │

│ │ │

│ ___│___ │

│ / │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.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: