Синтаксический разбор слева направо (LR)

Сейчас мы рассмотрим еще один метод синтаксического разбора, называемый LR(1)-разбором, а также некоторые упрощенные его варианты.

16.1. LR-процессы

Два отличия LR(1)-разбора от LL(1)-разбора: во-первых, строится не левый вывод, а правый, во-вторых, он строится не с начала, а с конца. (Вывод в КС-грамматике называется правым, если на каждом шаге замене подвергается самый правый нетерминал.)

16.1.1. Доказать, что если слово, состоящее из терминалов, выводимо, то оно имеет правый вывод.

Нам будет удобно смотреть на правый вывод "задом наперед". Определим понятие LR-процесса над словом $$A$$. В этом процессе, помимо $$A$$, будет участвовать и другое слово $$S$$, которое может содержать как терминалы, так и нетерминалы. Вначале слово $$S$$ пусто. В ходе LR-процесса разрешены два вида действий:

Отметим, что LR-процесс не является детерминированным: в одной и той же ситуации могут быть разрешены разные действия.

Говорят, что LR-процесс на слове $$A$$ успешно завершается, если слово $$A$$ становится пустым, а в слове $$S$$ остается единственный нетерминал - начальный нетерминал грамматики.

16.1.2. Доказать, что для любого слова $$A$$ (из терминалов) успешно завершающийся LR-процесс существует тогда и только тогда, когда слово $$A$$ выводимо в грамматике. В ходе доказательства установить взаимно однозначное соответствие между правыми выводами и успешно завершающимися LR-процессами.

Решение. При сдвиге слово $$SA$$ не меняется, при свертке слово $$SA$$ подвергается преобразованию, обратному шагу вывода. Этот вывод будет правым, так как сворачивается конец $$S$$, а в $$A$$ все символы - терминальные. Таким образом, каждому LR-процессу соответствует правый вывод. Обратное соответствие: пусть дан правый вывод. Представим себе, что за последним нетерминалом в слове стоит перегородка. Применив к этому нетерминалу правило грамматики, мы должны сдвинуть перегородку влево (если правая часть правила кончается на терминал). Разбивая этот сдвиг на отдельные шаги, получим процесс, в точности обратный LR-процессу.

Поскольку в ходе LR-процесса все изменения в слове $$S$$ происходят с правого конца, слово $$S$$ называют стеком LR-процесса .

Задача построения правого вывода для данного слова сводится, таким образом, к правильному выбору очередного шага LR-процесса. Нам нужно решить, будем ли мы делать сдвиг или свертку, и если свертку, то по какому правилу - ведь подходящих правил может быть несколько. В LR(1)-алгоритме это решение принимается на основе $$S$$ и первого символа слова $$A$$ ; если используется только $$S$$, то говорят о LR(0)-алгоритме. (Точные определения смотри ниже.)

Пусть фиксирована грамматика, в которой из любого нетерминала можно вывести какое-либо слово из терминалов. (Это ограничение мы будет всегда предполагать выполненным.)

Пусть $${K}\to{U}$$ - одно из правил грамматики ( K - нетерминал, U - слово из терминалов и нетерминалов). Определим множество слов (из терминалов и нетерминалов), называемое левым контекстом правила $${K}\to{U}$$. (Обозначение: $${ЛевКонт}({K}\to{U})$$.) По определению в него входят все слова, которые являются содержимым стека непосредственно перед сверткой U в K в ходе некоторого успешно завершающегося LR-процесса.

16.1.3. Переформулировать это определение на языке правых выводов.

Решение. Рассмотрим все правые выводы вида$$\langle{\text {начальный нетерминал}}\rangle \leadsto{XKA} \to {XUA},$$ где A - слово из терминалов, X - слово из терминалов и нетерминалов. Все возникающие при этом слова XU и образуют левый контекст правила $${K}\to{U}$$. Чтобы убедиться в этом, следует вспомнить, что мы предполагаем, что из любого нетерминала можно вывести какое-то слово из терминалов, так что правый вывод слова XUA может быть продолжен до правого вывода какого-то слова из терминалов.

16.1.4. Все слова из $${ЛевКонт}({K}\to{U})$$ кончаются, очевидно, на U. Доказать, что если у всех них этот конец U отбросить, то полученное множество слов не зависит от того, какое из правил для нетерминала K выбрано. (Это множество обозначается $${Лев}({K})$$.)

Решение. Из предыдущей задачи ясно, что $${Лев}({K})$$ - это все, что может появиться в правых выводах левее самого правого нетерминала K.

16.1.5. Доказать, что в предыдущей фразе можно отбросить слова " самого правого": $${Лев}({K})$$ - это все то, что может появляться в правых выводах левее любого вхождения нетерминала K.

Решение. Продолжив построение правого вывода, все нетерминалы справа от K можно заменить на терминалы (а слева от K при этом ничего не изменится).

16.1.6. Построить грамматику, содержащую для каждого нетерминала K исходной грамматики нетерминал $$\langle{Лев}{K}\rangle$$, причем следующее свойство должно выполняться для любого нетерминала K исходной грамматики: в новой грамматике из $$\langle{Лев}{K}\rangle$$ выводимы все элементы $${Лев}({K})$$ и только они. (При этом терминалы и нетерминалы исходной грамматики являются терминалами новой.)

Решение. Пусть P - начальный нетерминал грамматики. Тогда в новой грамматике будет правило$$\langle{Лев}{P}\rangle \to \qquad(\hbox{пустое слово})$$ Для каждого правила исходной грамматики, например, правила$${K} \to {L}\,{t}\,{M}\,{N}\qquad \hbox{({L}, {M}, {N} - нетерминалы, {t} - терминал),}$$ в новую грамматику мы добавим правила$$\begin{align*} \langle{Лев}{L}\rangle\to \langle{Лев}{K}\rangle\\ \langle{Лев}{M}\rangle\to \langle{Лев}{K}\rangle\,{L}\,{t}\\ \langle{Лев}{N}\rangle\to \langle{Лев}{K}\rangle\,{L}\,{t}\,{M} \end{align*}$$ и аналогично поступим с другими правилами. Смысл новых правил таков: пустое слово может появиться слева от P ; если слово X может появиться слева от K, то X может появиться слева от L, XLt может появиться слева от M, XLtM - слева от N. Индукцией по длине правого вывода легко проверить, что все, что может появиться слева от какого-то нетерминала, появляется в соответствии с этими правилами.

16.1.7. Почему в предыдущей задаче важно, что мы рассматриваем только правые выводы?

Ответ. В противном случае следовало бы учитывать преобразования, происходящие внутри слова, стоящего слева от K.

16.1.8. Для данной грамматики построить алгоритм, который по любому слову выясняет, каким из множеств $${Лев}({K})$$ оно принадлежит.

(Замечание для знатоков. Существование такого алгоритма - и даже конечного автомата, то есть индуктивного расширения с конечным числом значений, см. раздел 1.3., - вытекает из предыдущей задачи, так как построенная в ней грамматика имеет специальный вид: в правых частях всего один нетерминал, причем он стоит у левого края. Тем не менее мы приведем явное построение.)

Решение. Будем называть ситуацией данной грамматики одно из ее правил, в правой части которого отмечена одна из позиций (до первой буквы, между первой и второй буквой, $$\ldots,$$ после последней буквы). Например, правило$${K}\,\to\,{L}\,{t}\,{M}\,{N}$$ ( K, L, M, N - нетерминалы, t - терминал) порождает пять ситуаций$${K}\to\_\,{L}\,{t}\,{M}\,{N} \quad\ {K}\to{L}\,\_\,{t}\,{M}\,{N} \quad\ {K}\to{L}\,{t}\,\_\,{M}\,{N} \quad\ {K}\to{L}\,{t}\,{M}\,\_\,{N} \quad\ {K}\to{L}\,{t}\,{M}\,{N}\,\_$$ (позиция указывается знаком подчеркивания).

Будем говорить, что слово S согласовано с ситуацией $${K}\to{U}\,\_{V}$$, если S кончается на U, то есть $${S}={T}{U}$$ при некотором T, и, кроме того, T принадлежит $${Лев}({K})$$. (Смысл этого определения примерно таков: в стеке S подготовлена часть U для будущей свертки UV в K.) В этих терминах $${ЛевКонт}({K}\to{X})$$ - это множество всех слов, согласованных с ситуацией $${K}\to{X}\,\_\$$,, а $${Лев}({K})$$ - это множество всех слов, согласованных с ситуацией $${K}\to\_\,{X}$$ (где $${K}\to\,{X}$$ - любое правило для нетерминала K ).

Эквивалентное определение в терминах LR-процесса: S согласовано с ситуацией $${K}\to{U}\,\_\,{V}$$, если существует успешный LR-процесс, в котором события развиваются так:

16.1.9. Доказать эквивалентность этих определений.

Указание. Если $${S} ={TU}$$ и T принадлежит $${Лев}({K})$$, то можно получить в стеке сначала T, потом U, потом V, потом свернуть UV в K и затем успешно завершить процесс. (Мы используем несколько раз тот факт, что из любого нетерминала что-то да выводится: благодаря этому мы можем добавить в стек любое слово.)

Наша цель - построение алгоритма, распознающего принадлежность произвольного слова к $${Лев}({K})$$. Рассмотрим функцию, сопоставляющую с каждым словом S (из терминалов и нетерминалов) множество всех согласованных с ним ситуаций. Это множество назовем состоянием, соответствующим слову S }. Будем обозначать его $${Сост}({S})$$. Достаточно показать, что функция $${Сост}({S})$$ индуктивна, то есть что значение $${Сост}({SJ})$$, где J - терминал или нетерминал, может быть вычислено, если известно $${Сост}({S})$$ и символ J. (Мы видели ранее, как принадлежность к $${Лев}({K})$$ выражается в терминах этой функции.) Значение $${Сост}({SJ})$$ вычисляется по таким правилам:

(1) Если слово S согласовано с ситуацией K->U_V, причем слово V начинается на букву J, то есть V=JW, то SJ согласовано с ситуацией K->UJ_W.

Это правило полностью определяет все ситуации с непустой левой половиной (то есть не начинающиеся с подчеркивания), согласованные с SJ. Осталось определить, для каких нетерминалов K слово SJ принадлежит $${Лев}({K})$$. Это делается по двум правилам:

(2) Если ситуация L->U_V согласована с SJ (согласно правилу (1)), а V начинается на нетерминал K, то SJ принадлежит Лев(K).

(3) Если SJ входит в Лев(L) для некоторого L, причем L->V - правило грамматики и V начинается на нетерминал K, то SJ принадлежит Лев(K).

Заметим, что правило (3) можно рассматривать как аналог правила (2): в указанных в (3) предположениях ситуация $${L}\to\_{V}$$ согласована с SJ, а V начинается на нетерминал K.

Корректность этих правил в общем-то очевидна, если хорошенько подумать. Единственное, что требует некоторых пояснений - это то, почему с помощью правил (2) и (3) обнаружатся $$\textsl{все}$$ терминалы K, для которых SJ принадлежит $${Лев}({K})$$. Попытаемся это объяснить. Рассмотрим правый вывод, в котором SJ стоит слева от K. Откуда мог взяться в нем нетерминал K? Если правило, которое его породило, породило также и конец слова SJ, то принадлежность SJ к $${Лев}({K})$$ будет обнаружена по правилу (2). Если же K было первой буквой слова, порожденного каким-то другим нетерминалом L, то - благодаря правилу (3) - достаточно установить принадлежность SJ к $${Лев}({L})$$. Осталось применить те же рассуждения к L и так далее.

В терминах LR-процесса то же самое можно сказать так. Сначала нетерминал K может участвовать в нескольких свертках, не затрагивающих SJ (они соответствуют применению правила (3)), но затем он обязан подвергнуться свертке, затрагивающей SJ (что соответствует применению правила (2)).

Осталось выяснить, какие ситуации согласованы с пустым словом, то есть для каких нетерминалов K пустое слово принадлежит $${Лев}({K})$$. Это определяется по следующим правилам:

16.1.10. Проделать описанный анализ для грамматики$$\begin{align*} {E}\to {E}\;{+}\;{T}\\ {E}\to {T}\\ {T}\to {T}\;{*}\;{F}\\ {T}\to {F}\\ {F}\to {x}\\ {F}\to {(}\;{E}\;{)} \end{align*}$$ (задающей тот же язык, что и грамматика примера 3, см. пункт 15.1.).

Решение. Множества Сост(S) для различных S приведены в таблице (см. ниже).

E->_E+T E->_T T->_T*F
   T->_F F->_x F->_(E)

F->(_E) E->_E+T E->_T
  T->_T*F T->_F F->_x F->_(E)

E->E+_T T->_T*F T->_F
  F->_x F->_(E)

Знак равенства означает, что множества ситуаций, являющиеся значениями функции $${Сост}({S})$$ на словах, стоящих слева и справа от знака равенства, одинаковы.

Правило определения $${Сост}({SJ})$$, если известны $${Сост}({S})$$ и J (здесь S - слово из терминалов и нетерминалов, J - терминал или нетерминал), таково:

надо найти Сост(S) в правой колонке, взять соответствующее ему слово T в левой колонке, приписать к нему J и взять множество, стоящее напротив слова TJ (если слово TJ в таблице отсутствует, то Сост(SJ) пусто).

16.2. LR(0)-грамматики

Напомним, что наша основная цель - это поиск вывода заданного слова, или, другими словами, поиск успешного LR-процесса над ним. Во всех рассматриваемых нами грамматиках успешный LR-процесс (над данным словом) единствен. Искать этот единственный успешный процесс мы будем постепенно: в каждый момент мы смотрим, какой шаг возможен следующим. Для этого на грамматику надо наложить дополнительные требования, и сейчас мы рассмотрим простейший случай так называемых LR(0)-грамматик. Мы уже знаем:

(1) В успешном LR-процессе возможна свертка по правилу K->U при содержимом стека S тогда и только тогда, когда S принадлежит ЛевКонт(K->U) или, другими словами, когда слово S согласовано с ситуацией K->U_.

Аналогичное утверждение про сдвиг гласит:

(2) В успешном LR-процессе при содержимом стека S возможен сдвиг с очередным символом a тогда и только тогда, когда S согласовано с некоторой ситуацией K->U_aV.

16.2.1. Доказать это.

Указание. Пусть произошел сдвиг и к стеку S добавилась буква a. Рассмотрите первую свертку, затрагивающую эту букву.

Рассмотрим некоторую грамматику и произвольное слово S из терминалов и нетерминалов. Если множество $${Сост}({S})$$ содержит ситуацию, в которой справа от подчеркивания стоит терминал, то говорят, что для слова S возможен сдвиг. Если в $${Сост}({S})$$ есть ситуация, в которой справа от подчеркивания ничего нет, то говорят, что для слова S возможна свертка (по соответствующему правилу). Говорят, что для слова S возникает конфликт типа сдвиг/свертка, если возможны и сдвиг, и свертка. Говорят, что для слова S возникает конфликт типа свертка/свертка, если есть несколько правил, по которым возможна свертка.

Грамматика называется LR(0)-грамматикой, если в ней нет конфликтов типа сдвиг/свертка и свертка/свертка ни для одного слова S.

16.2.2. Является ли приведенная выше грамматика LR(0)-грамматикой?

Решение. Нет, не является. Для слов T и E+T имеются конфликты типа сдвиг/свертка.

16.2.3. Являются ли LR(0)-грамматиками такие:$$\begin{aligned} \text{(а)}\quad {T}\to{0}\\ {T} \to{T1}\\ {T} \to{TT2}\\ {T} \to{TTT3} \end{aligned}\qquad\qquad \begin{aligned} \text{(б)}\quad {T}\to{0}\\ {T} \to{1T}\\ {T} \to{2TT}\\ {T} \to{3TTT} \end{aligned}$$

Решение. Являются, см. таблицы ниже (конфликтов нет).

T->T_1 T->T_T2 T->T_TT3 
T->_0 T->_T1 T->_TT2 T->_TT3

T->TT_2 T->TT_T3
T->T_1 T->T_T2 T->T_TT3 
T->_0 T->_T1 T->_TT2 T->_TTT3

T->TTT_3 T->TT_2 T->TT_T3
T->T_1 T->T_T2 T->T_TT3
T->_0 T->_T1 T->)TT2 T->_TTT3

T->1_T
T->_0 T->_1T T->_2TT T->_3TTT

T->2_TT
T->_0 T->_1T T->_2TT T->_3TTT

T->3_TTT
T->_0 T->_1T T->_2TT T->_3TTT

T->2T_T
T->_0 T->_1T T->_2TT T->_3TTT

T->3T_TT
T->_0 T->_1T T->_2TT T->_3TTT

T->3TT_T
T->_0 T->_1T T->_2TT T->_3TTT

Эта задача показывает, что LR(0)-грамматики могут быть как леворекурсивными, так и праворекурсивными.

16.2.4. Пусть дана LR(0)-грамматика. Доказать, что у любого слова существует не более одного правого вывода. Построить алгоритм проверки выводимости в LR(0)-грамматике.

Решение. Пусть дано произвольное слово. Будем строить LR-процесс над ним по шагам. Пусть текущее состояние стека LR-процесса равно S. Нам надо решить, делать сдвиг или свертку (и если свертку, то по какому правилу). Согласно определению LR(0)-грамматики, в нашем состоянии S возможен либо только сдвиг, либо только свертка (причем лишь по одному правилу). Таким образом, поиск возможных продолжений LR-процесса происходит детерминированно (на каждом шаге можно определить, какое действие только и возможно).

16.2.5. Что произойдет, если анализируемое слово не имеет вывода в данной грамматике?

Ответ. Либо на некотором шаге не будет возможен ни сдвиг, ни свертка, либо все возможные сдвиги будет иметь неподходящий очередной символ.

Замечания. 1. При реализации этого алгоритма нет необходимости каждый раз заново вычислять множество $${Сост}({S})$$ для текущего значения S. Эти множества можно также хранить в стеке (в каждый момент хранятся множества $${Сост}({T})$$ для всех начал T текущего слова S ).

2. На самом деле само слово S можно не хранить - достаточно хранить множества ситуаций $${Сост}({T})$$ для всех его начал T (включая само S ).

В алгоритме проверки выводимости в LR(0)-грамматике мы используем не всю информацию, которую могли бы. В этом алгоритме для каждого состояния известно заранее, что в нем возможен только сдвиг или только свертка (причем в последнем случае известно, по какому правилу). Более изощренный алгоритм мог бы принимать решение о выборе между сдвигом и сверткой, посмотрев на очередной символ ( Next ). Глядя на состояние, можно сказать, при каких значениях Next возможен сдвиг (это те терминалы, которые в ситуациях этого состояния стоят непосредственно за подчеркиванием). Сложнее воспользоваться информацией о символе Next для решения вопроса о том, возможна ли свертка. Для этого есть упрощенный метод (грамматики, к которым он применим, называют SLR(1)-грамматиками [сокращение от Simple LR(1)]) и полный метод (более сложный, но использующий всю возможную информацию; грамматики, к которым он применим, называют LR(1)-грамматиками). Есть и промежуточный класс грамматик, называемый LALR(1).

16.3. SLR(1)-грамматики

Напомним, что для любого нетерминала K мы определяли (см. пункт 15.3.) множество $${Послед}({K})$$ тех терминалов, которые могут стоять непосредственно за $${K}$$ в выводимом (из начального нетерминала) слове; в это множество добавляют также символ EOI, если нетерминал K может стоять в конце выводимого слова.

16.3.1. Доказать, что если в данный момент LR-процесса последний символ стека S равен K, причем процесс этот может в дальнейшем успешно завершиться, то Next принадлежит $${Послед}({K})$$.

Решение. Этот факт является непосредственным следствием определения (вспомним соответствие между правыми выводами и LR-процессами).

Рассмотрим некоторую грамматику, произвольное слово S из терминалов и нетерминалов и терминал x. Если множество $${Сост}({S})$$ содержит ситуацию, в которой справа от подчеркивания стоит терминал x, то говорят, что для пары $$\langle{S},{x}\rangle$$ возможен сдвиг. Если в $${Сост}({S})$$ есть ситуация $${K}\to{U}\_\$$,, причем x принадлежит $${Послед}({K})$$, то говорят, что для пары $$\langle{S},{x}\rangle$$ SLR(1)-возможна свертка (по правилу $${K}\to{U}$$ ). Говорят, что для пары $$\langle{S},{x}\rangle$$ возникает SLR(1)-конфликт типа сдвиг/свертка, если возможны и сдвиг, и свертка. Говорят, что для пары $$\langle{S},{x}\rangle$$ возникает SLR(1)-конфликт типа свертка/свертка, если есть несколько правил, по которым возможна свертка.

Грамматика называется SLR(1)-грамматикой, если в ней нет SLR(1)-конфликтов типа сдвиг/свертка и свертка/свертка ни для одной пары $$\langle{S},{x}\rangle$$.

16.3.2. Пусть дана SLR(1)-грамматика. Доказать, что у любого слова существует не более одного правого вывода. Построить алгоритм проверки выводимости в SLR(1)-грамматике.

Решение. Аналогично случаю LR(0)-грамматик, только при выборе между сдвигом и сверткой учитывается очередной символ ( Next ).

16.3.3. Проверить, является ли приведенная выше в задаче 16.1.10. грамматика (с нетерминалами E, T и F ) SLR(1)-грамматикой.

Решение. Да, является, так как оба конфликта, мешающие ей быть LR(0)-грамматикой, разрешаются с учетом очередного символа: и для слова T, и для слова E+T сдвиг возможен только при $${Next}={*}$$, а символ * не принадлежит ни $${Послед}({E}) = \{{EOI},{+},{)}\}$$, ни $${Послед}({T}) = \{{EOI},{+},{*},{)}\}$$, и поэтому при $${Next}={*}$$ свертка невозможна.

16.4. LR(1)-грамматики, LALR(1)-грамматики

Описанный выше SLR(1)-подход используют не всю возможную информацию при выяснении того, возможна ли свертка. Именно, он отдельно проверяет, возможна ли свертка при данном состоянии стека S и отдельно - возможна ли свертка по данному правилу при данном символе Next. Между тем эти проверки не являются независимыми: обе могут дать положительный ответ, но тем не менее свертка при стеке S и очередном символе Next невозможна. В LR(1)-подходе этот недостаток устраняется.

LR(1)-подход состоит вот в чем: все наши определения и утверждения модифицируются так, чтобы учесть, какой символ стоит справа от разворачиваемого нетерминала (другими словами, чему равен Next при свертке).

Пусть $${K}\to{U}$$ - одно из правил грамматики, а t - некоторый терминал или спецсимвол EOI (который мы домысливаем в конце входного слова). Определим множество $${ЛевКонт}({K}\to{U},{t})$$ как множество всех слов, которые являются содержимым стека непосредственно перед сверткой U в K в ходе успешного LR-процесса, при условии $${Next} = {t}$$ (в момент свертки).

Если отбросить у всех слов из $${ЛевКонт}({K}\to{U})$$ их конец U, то получится множество всех слов, которые могут появиться в правых выводах перед нетерминалом K, за которым стоит символ t. Это множество (не зависящее от того, какое из правил $${K}\to{U}$$ для нетерминала K выбрано) мы будем обозначать $${Лев}({K},{t})$$.

16.4.1. Написать грамматику для порождения множеств $${Лев}({K},{t})$$.

Решение. Ее нетерминалами будут символы $$\langle{ЛевK}\:{t}\rangle$$ для каждого нетерминала K и для каждого терминала t (а также для $${t}={EOI}$$ ). Ее правила таковы. Пусть P - начальный нетерминал исходной грамматики. Тогда в новой грамматике будет правило$$\langle {ЛевP}\:{EOI}\rangle\to \qquad \hbox{(пустое слово).}$$ Каждое правило исходной грамматики порождает несколько правил новой. Например, для правила$${K}\to{L}\,{u}\,{M}\,{N}$$ ( L, M, N - нетерминалы, u - терминал) в новую грамматику мы добавим правила$$\langle{ЛевL}\:{u}\rangle \to \langle{ЛевK}\:{x}\rangle$$ (для всех терминалов x );$$\langle{ЛевM}\:{s}\rangle \to \langle{ЛевK}\:{y}\rangle\,{L}\,{u}$$ (для всех s, которые могут начинать слова, выводимые из N, и для всех y, а также для всех пар $${s} = {y}$$, если из N выводимо пустое слово);$$\langle{ЛевN}\:{s}\rangle \to \langle{ЛевK}\:{s}\rangle\,{L}\,{u}\,{M}$$ (для всех терминалов s ).

16.4.2. Как меняется определение ситуации?

Решение. Ситуацией называется пара$$[ \text{ситуация в старом смысле}, \text{терминал или {EOI}} ]$$