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

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

(1) В успешном LR-процессе возможна свертка по правилу ${\hbox{\tt K}}\to{\hbox{\tt U}}$ при содержимом стека S тогда и только тогда, когда S принадлежит ${\hbox{\rm ЛевКонт}}({\hbox{\tt K}}\to{\hbox{\tt U}})$ или, другими словами, когда слово S согласовано с ситуацией ${\hbox{\tt K}}\to{\hbox{\tt U}}\_$ .

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

(2) В успешном LR-процессе при содержимом стека S возможен сдвиг с очередным символом a тогда и только тогда, когда S согласовано с некоторой ситуацией ${\hbox{\tt K}}\to{\hbox{\tt U}}\_{\hbox{\tt aV}}$ .

$\scriptstyle{\blacktriangleright}$ 14.2.1. Докажите это.

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

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

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

$\scriptstyle{\blacktriangleright}$ 14.2.2. Является ли приведенная выше грамматика LR(0)-грамматикой?

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

$\scriptstyle{\blacktriangleright}$ 14.2.3. Являются ли LR(0)-грамматиками такие:

$\begin{displaymath} \begin{tabular} {ll} \begin{tabular} {rrcl} (а)&{\hbox{\tt... ...box{\tt T}}&$\to$&{\hbox{\tt 3TTT}} \end{tabular}\end{tabular}\end{displaymath}$

Решение. Являются, см. соответствующие таблицы (конфликтов нет). $\scriptstyle\blacktriangleleft$

$\begin{figure} \begin{displaymath} \begin{tabular} {\vert l\vert l\vert} \hline ... ...\ \hline\end{tabular}\end{displaymath}\begin{center} (а)\end{center}\end{figure}$

$\begin{figure} \begin{displaymath} \begin{tabular} {\vert l\vert l\vert} \hline ... ...\end{tabular}\end{displaymath}\begin{center} (б), начало\end{center}\end{figure}$

$\begin{figure} \begin{displaymath} \begin{tabular} {\vert l\vert l\vert} \hline ... ...d{tabular}\end{displaymath}\begin{center} (б), окончание\end{center}\end{figure}$

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

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

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

$\scriptstyle{\blacktriangleright}$ 14.2.5. Что произойдет, если анализируемое слово не имеет вывода в данной грамматике?

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

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

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

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

pvv
1/8/1999