Задачи по программированию по курсу ЯПиМТ. Родионова Т.Е. - 29 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

29
входной цепочки в магазин(стек), асвертка– применение к вершине магазина какого-либо правила грамма-
тики. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки.
LR-грамматика и грамматики предшествования, наиболее часто используемые из грамматик восхо-
дящего разбора.LR(k)–грамматикой называется грамматика, при использовании которой в качестве основы
для анализатора все конфликты типа сдвиг – свертка и свертка – свертка можно разрешать на основании уже
прочитанного текста и фиксированного числа предварительно просматриваемых символов.
Буква L показывает, что строки читаются слева направо, а R–что получается правосторонний раз-
бор. На практике k принимает значение 0 или 1. Читая входную цепочку слева направо, анализатор пытается
свернуть ее в начальный символ.
Шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы вы-
яснить, образуют ли верхние символы правую часть какого-нибудь правила. Если это так, то производится
свертка, заменяющая эти символы левой частью того самого правила. Если свертка невозможна, то в магазин
переносится следующий входной символ и процесс продолжается.
Рассмотрим пример LR(0) – грамматики. При разборе строки LR(0) языка аванцепочка не использу-
ется. Просмотренные символы правила, расположенные левее текущей позиции (обозначается “_”) называют
активным префиксом.
(1) S → aSS
(2) S → b
При рассмотрении LR – грамматик используют “пополненные грамматики”. Добавляем новый на-
чальный символ и получаем следующую грамматику:
(1) S′→S
(2) S → aSS
(3) S → b
Выпишем для пополненной грамматики множества ситуаций, допустимых для различных активных
префиксов.
0V(e) [S′→_S], [S → _aSS], [S → _b]
1V(a) [S→ a_SS], [S → _aSS], [S → _b]
2V(b) [S→ b_]
3V(S) [S′→S_]
4 V(aS) [S → aS_S], [S → _aSS], [S → _b]
5V(aSS) [S→ aSS_]
Если текущая позиция стоит перед S,то во множество ситуаций входят все ситуации с правилами
для S. Если во множестве ситуаций правила не закончены, то дальнейшее действие – сдвиг. После сдвига в
состоянии 1 возможны следующие активные префиксы: aa, aS,ab. Когда правило закончено ( состоянии 2 и
5), необходима свертка. Состояние 3 говорит о получении начального символа, следовательно, разбор закон-

Страницы