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

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

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

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

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

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


$\scriptstyle{\blacktriangleright}$ 14.4.1. Написать грамматику для порождения множеств \begin{displaymath} {\hbox{\rm Лев}}({\hbox{\tt K}},{\hbox{\tt t}}).\end{displaymath}

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


$\scriptstyle{\blacktriangleright}$ 14.4.2. Как меняется определение ситуации?

Решение. Ситуацией называется пара \begin{displaymath}[ \hbox{\rm ситуация в старом смысле}, \hbox{\rm терминал или {\hbox{\tt EOI}}} ]\end{displaymath}$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.3. Как изменится определение согласованности?

Решение. лово S из терминалов и нетерминалов согласованo с ситуацией $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},\,{\hbox{\tt t}}]$ (здесь t -- терминал или EOI), если S кончается на U, то есть ${\hbox{\tt S}} ={\hbox{\tt TU}}$, и, кроме того, T принадлежит ${\hbox{\rm Лев}}({\hbox{\tt K}},{\hbox{\tt t}})$.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.4. Каковы правила для индуктивного вычисления множества ${\hbox{\rm Сост}}({\hbox{\tt S}})$ ситуаций, согласованных с данным словом S?

Ответ:

(1) Если слово S согласовано с ситуацией $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},\,{\hbox{\tt t}}]$, причем слово V начинается на букву J, то есть ${\hbox{\tt V}}={\hbox{\tt JW}}$, то слово SJ согласовано с ситуацией $[{\hbox{\tt K}}\to{\hbox{\tt UJ}}\_{\hbox{\tt W}},\,{\hbox{\tt t}}]$.

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

(2) Если ситуация $[{\hbox{\tt L}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},{\hbox{\tt t}}]$ согласована с SJ (согласно правилу (1)), а V начинается на нетерминал К, то SJ принадлежит ${\hbox{\rm Лев}}({\hbox{\tt K}},{\hbox{\tt s}})$ для всех терминалов s, которые могут начинать слова, выводимые из слова ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ (слово V без первой буквы K), а также для ${\hbox{\tt s}}={\hbox{\tt t}}$, если из ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ выводится пустое слово.

(3) Если SJ входит в ${\hbox{\rm Лев}}({\hbox{\tt L}},{\hbox{\tt t}})$ для некоторых L и t, причем ${\hbox{\tt L}}\to{\hbox{\tt V}}$ -- правило грамматики и V начинается на нетерминал K, то SJ принадлежит ${\hbox{\rm Лев}}({\hbox{\tt K}},{\hbox{\tt s}})$для всех терминалов s, которые могут начинать слова, выводимые из ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$, а также для ${\hbox{\tt s}}={\hbox{\tt t}}$, если из ${\hbox{\tt V}}\setminus{\hbox{\tt K}}$ выводится пустое слово.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.5. Дать определения конфликтов сдвиг/свертка и свертка/свертка по аналогии с данными выше.

Решение. Пусть дана некоторая грамматика. Пусть S -- произвольное слово из терминалов и нетерминалов. Если множество ${\hbox{\rm Сост}}({\hbox{\tt S}})$ содержит ситуацию, в которой справа от подчеркивания стоит терминал t, то говорят, что для пары $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$ возможен сдвиг. (Это определение не изменилось по сравнению с SLR(1)-случаем -- вторые компоненты пар из ${\hbox{\rm Сост}}({\hbox{\tt S}})$ не учитываются.)

Если в ${\hbox{\rm Сост}}({\hbox{\tt S}})$ есть ситуация, в которой справа от подчеркивания ничего нет, а вторым членом пары является терминал t, то говорят, что для пары $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$LR(1)-возможна свертка (по соответствующему правилу). Говорят, что для пары $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$возникает LR(1)-конфликт типа сдвиг/свертка, если возможны и сдвиг, и свертка. Говорят,     что для пары $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$возникает LR(1)-конфликт типа свертка/свертка, если есть несколько правил, по которым возможна свертка.$\scriptstyle\blacktriangleleft$

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


$\scriptstyle{\blacktriangleright}$ 14.4.6. Построить алгоритм проверки выводимости слова в LR(1)-грамматике.

Решение. Как и раньше, на каждом шаге LR-процесса можно однозначно определить, какой шаг только и может быть следующим.$\scriptstyle\blacktriangleleft$


Полезно (в частности, для LALR(1)-разбора, смотри ниже) понять, как связаны понятия LR(0) и LR(1)-согласованности.


$\scriptstyle{\blacktriangleright}$ 14.4.7. Сформулировать и доказать соответствующее утверждение.

Ответ. Пусть фиксирована некоторая грамматика. Слово S из терминалов и нетерминалов является LR(0)-согласованным с ситуацией ${\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}}$ тогда и только тогда, когда оно LR(1)-согласовано с парой $[{\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt V}},{\hbox{\tt t}}]$для некоторого терминала t (или для ${\hbox{\tt t}}={\hbox{\tt EOI}}$). То же самое другими словами: ${\hbox{\rm Лев}}({\hbox{\tt K}})$ есть объединение ${\hbox{\rm Лев}}({\hbox{\tt K}},{\hbox{\tt t}})$ по всем t. В последней форме это совсем ясно.$\scriptstyle\blacktriangleleft$

Замечание. Таким образом, функция ${\hbox{\rm Сост}}({\hbox{\tt S}})$ в LR(1)-смысле является расширением функции ${\hbox{\rm Сост}}({\hbox{\tt S}})$ в LR(0)-смысле: \begin{displaymath} {\hbox{\rm Сост}}_{\rm LR(0)}({\hbox{\tt S}})\qquad\hbox{получается из}\qquad{\hbox{\rm Сост}}_{\rm LR(1)}({\hbox{\tt S}}),\end{displaymath}если во всех парах выбросить вторые члены.

Теперь мы можем дать определение LALR(1)-грамматики. Пусть фиксирована некоторая грамматика, S -- слово из нетерминалов и терминалов, t -- некоторый терминал (или EOI). Будем говорить, что для пары $\langle {\hbox{\tt S}},{\hbox{\tt t}}\rangle$ LALR(1)-возможна свертка по некоторому правилу, если существует другое слово ${\hbox{\tt S}}_1$ с ${\hbox{\rm Сост}}_{\rm LR(0)}({\hbox{\tt S}}_0) = {\hbox{\rm Сост}}_{\rm LR(0)}({\hbox{\tt S}}_1)$, причем для пары $\langle{\hbox{\tt S}}_1,{\hbox{\tt t}}\rangle$LR(1)-возможна свертка по рассматриваемому правилу. Далее определяются конфликты (естественным образом), и грамматика     называется LALR(1)-грамматикой, если конфликтов нет.


$\scriptstyle{\blacktriangleright}$ 14.4.8. Доказать, что всякая SLR(1)-грамматика является
LALR(1)-грамматикой, а всякая LALR(1)-грамматика является LR(1)-грамматикой.

[Указание. Это -- простое следствие определений.]$\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.9. Построить алгоритм проверки выводимости в LALR(1)-грамматике, который хранит в стеке меньше информации, чем соответствующий LR(1)-алгоритм.

[Указание. Достаточно хранить в стеке множества \begin{displaymath} {\hbox{\rm Сост}}_{\rm LR(0)}({\hbox{\tt S}}),\end{displaymath}поскольку согласно определению LALR(1)-возможность свертки ими определяется. (Так что сам алгоритм ничем не отличается от SLR(1)-случая, кроме таблицы возможных сверток.)]$\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.10. Привести пример LALR(1)-грамматики, не являющейся SLR(1)-грамматикой.$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.4.11. Привести пример LR(1)-грамматики, не являющейся LALR(1)-грамматикой.$\scriptstyle\blacktriangleleft$

Общие замечания о разных методах разбора     width0pt

pvv
1/8/1999