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

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

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

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

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

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

     Нам  будет удобно смотреть на правый вывод "задом наперед".
Определим понятие LR-процесса над словом A. В этом процессе, по-
мимо A, будет участвовать и другое слово S, которое может содер-
жать как терминалы, так и нетерминалы. Вначале слово S пусто.  В
ходе LR-процесса разрешены два вида действий:
     (1)  можно  перенести  первый  символ слова А (его называют
очередным символом и обозначают Next) в конец  слова  S,  удалив
его из A (это действие называют сдвигом);
     (2) если правая часть одного из правил грамматики оказалась
концом  слова  S, то разрешается заменить ее на нетерминал, сто-
ящий в левой части этого правила; при этом слово A не  меняется.
(Это действие называют сверткой, или приведением.)
     Отметим,  что  LR-процесс  не является детерминированным: в
одной и той же ситуации могут быть разрешены разные действия.
     Говорят, что LR-процесс на слове A успешно завершается, ес-
ли слово A становится пустым, а в слове S остается  единственный
нетерминал - начальный нетерминал грамматики.

     14.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 -> U - одно из правил грамматики (K - нетерминал, U
- слово из терминалов и нетерминалов). Определим множество  слов
(из терминалов и нетерминалов), называемое левым контекстом пра-
вила K -> U. (Обозначение: ЛевКонт(K->U).) По определению в него
входят  все  слова,  которые  являются  содержимым  стека непос-
редственно перед сверткой U в K в ходе некоторого успешно завер-
шающегося LR-процесса.

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

     Решение. Рассмотрим все правые выводы вида
        <начальный нетерминал> --> XKA -> XUA,
где  A - слово из терминалов, X - слово из терминалов и нетерми-
налов. Все возникающие при этом слова XU и образуют  левый  кон-
текст  правила  K->U. Чтобы убедиться в этом, следует вспомнить,
что мы предполагаем, что из любого нетерминала можно вывести ка-
кое-то слово из терминалов (другие грамматики мы не рассматрива-
ем), так что правый вывод слова XUA может быть продолжен до пра-
вого вывода какого-то слова из терминалов.

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

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

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

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

     14.1.6. Построить грамматику, содержащую для каждого нетер-
минала K исходной граммaтики нетерминал <ЛевK>, причем следующее
свойство должно выполняться для любого  нетерминала  K  исходной
грамматики:  в  новой грамматике из <ЛевK> выводимы все элементы
Лев(K) и только они.

     Решение. Пусть P - начальный нетерминал грамматики. Тогда в
новой грамматике будет правило
     <ЛевP> ->       (пустое слово)
Для каждого правила исходной грамматики, например, правила

      K -> L t M N (L, M, N - нетерминалы, t - терминал),

в новую грамматику мы добавим правила
      <ЛевL> -> <ЛевK>
      <ЛевM> -> <ЛевК> L t
      <ЛевN> -> <ЛевK> L t M
и аналогично поступим с другими правилами.  Смысл  новых  правил
таков: пустое слово может появиться слева от P; если слово X мо-
жет  появиться  слева от K, то X может появиться слева от L, XLt
может появиться слева от M, XLtM - слева от N. Индукцией по дли-
не правого вывода легко проверить, что все, что может  появиться
слева от какого-то нетерминала, появляется в соответствии с эти-
ми правилами.

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

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

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

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

     Решение. Будем называть ситуацией данной грамматики одно из
ее  правил, в правой части которого отмечена одна из позиций (до
первой буквы, между первой и второй буквой,..., после  последней
буквы). Например, правило
     K -> L t M N   (K, L, M, N - нетерминалы, t - терминал)
порождает пять ситуаций
     К -> _LtMN, K-> L_tMN, K-> Lt_MN, K-> LtM_N, K -> LtMN_.
(позиция указывается знаком подчеркивания).
     Будем говорить, что слово S согласовано с ситуацией K->U_V,
если  S  кончается  на U, то есть S=TU при некотором T, и, кроме
того, T принадлежит Лев(K). (Смысл  этого  определения  примерно
таков:  в  стеке S подготовлена часть U для будущей свертки UV в
K.) В этих терминах ЛевКонт(K->X) -  это  множество  всех  слов,
согласованных  с  ситуацией K->X_, а Лев(К) - это множество всех
слов, согласованных с ситуацией K->_X (где K->_X - любое правило
для нетерминала K).
     Эквивалентное  определение в терминах LR-процесса: S согла-
совано с ситуацией K->U_V, если существует успешный  LR-процесс,
в котором события развиваются так:
     - в ходе процесса в стеке появляется слово S, и оно оканчи-
чивается на U;
     -  некоторое время S не затрагивается, а справа от него по-
является V;
     - UV сворачивается в K;
     - процесс продолжается и успешно завершается.

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

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

     Наша  цель - построение алгоритма, распознающего принадлеж-
ность произвольного слова к Лев(K). Рассмотрим  функцию,  сопос-
тавляющую  с каждым словом S (из терминалов и нетерминалов) мно-
жество всех согласованных с ним ситуаций. Это множество называют
состоянием,  соответствующим  слову  S.  Будем  обозначать   его
Сост(S).  Достаточно  показать,  что функция Сост(S) индуктивна,
т.е. что значение Сост(SJ), где J - терминал или нетерминал, мо-
жет быть вычислено, если известно Сост(S) и символ J. (Мы видели
ранее, как принадлежность к Лев(К) выражается  в  терминах  этой
функции.) Значение Сост(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 начинается на нетерминал К, то SJ принад-
лежит Лев(K).
     (3) Если уже выяснено, что SJ входит в Лев(L) для некоторо-
го L, L->V - правило грамматики и V начинается на нетерминал  K,
то SJ принадлежит Лев(K).
     Заметим,  что  правило  (3)  можно рассматривать как аналог
правила (2): в указанных в  (3)  предположениях  ситуация  L->_V
согласована с SJ, а V начинается на нетерминал K.
     Корректность  этих  правил  в общем-то очевидна, если хоро-
шенько подумать. Единственное, что требует некоторых пояснений -
это то, почему с помощью правил (2) и (3) обнаружатся ВСЕ терми-
налы K, для которых SJ принадлежит Лев(K). Попытаемся это объяс-
нить. Рассмотрим правый вывод, в котором SJ стоит  слева  от  K.
Откуда мог взяться в нем нетерминал K? Если правило, которое его
породило,  породило также и конец слова SJ, то принадлежность SJ
к Лев(K) будет обнаружена по правилу (2). Если же K было  первой
буквой  слова, порожденного каким-то другим нетерминалом L, то -
благодаря правилу (3) - достаточно установить принадлежность  SJ
к Лев(L). Осталось применить те же рассуждения к L и т.д.
     В  терминах LR-процесса то же самое можно сказать так. Сна-
чала нетерминал K может участвовать в  нескольких  свертках,  не
затрагивающих  SJ (они соответствуют применению правила (3)), но
затем он обязан подвергнуться свертке, затрагивающей SJ (что со-
ответствует применению правила (2)).
     Осталось выяснить, какие ситуации согласованы с пустым сло-
вом, то есть для каких нетерминалов K пустое  слово  принадлежит
Лев(K).  Это  определяется  по следующим правилам: (1) начальный
нетерминал таков; (2) если K таков и K -> V - правило  граммати-
ки, причем слово V начинается с нетерминала L, то и L таков.

     14.1.10. Проделать описанный анализ для грамматики

        E -> E + T
        E -> T
        T -> T * F
        T -> F
        F -> x
        F -> ( E )

     Решение.

Слово S                    Сост(S)
_________________________________________________

пустое   E->_E+T;E->_T;T->_T*F;T->_F;F->_x;F->_(E)
E        E->E_+T
T        E->T_; T->T_*F;
F        T->F_
x        F->x_
(        F->(_E);E->_E+T;E->_T;T->_T*F;T->_F;F->_x;F->_(E)
E+       E->E+_T;T->_T*F;T->_F;F->_x;F->_(E)
T*       T->T*_F;F->_x;F->_(E)
(E       F->(E_);E->E_+T;
(T       = T
(F       = F
(x       = x
((       = (
E+T      E->E+T_;T->T_*F
E+F      = F
E+x      = x
E+(      = (
T*F      T->T*F_;
T*x      = x
T*(      = (
(E)      F->(E)_
(E+      = E+
E+T*     = T*

Знак равенства означает, что множества ситуаций, являющиеся зна-
чениями  функции  Сост(S)  на  словах, стоящих слева и справа от
знака равенства, одинаковы.
     Правило определения Сост(SJ), если известны Сост(S) и J  (S
-  слово из терминалов и нетерминалов, J - терминал или нетерми-
нал), таково:
     надо найти Сост(S) в правой колонке, взять  соответствующее
ему  слово  T  в  левой колонке, приписать к нему J и взять мно-
жество, стоящее напротив слова ТJ (если слово ТJ в  таблице  от-
сутствует, то Сост(SJ) пусто).


     14.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.

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

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

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

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

     14.2.3. Являются ли LR(0)-грамматиками такие:

     (а) T->0
         T->T1
         T->TT2
         T->TTT3

     (б) T->0
         T->1T
         T->2TT
         T->3TTT

     Решение. (а)

Слово S                    Сост(S)
_________________________________________

пустое    Т->_0;T->_T1;T->_TT2;T->_TTT3
0         Т->0_
Т         Т->Т_1;T->T_T2;T->T_TT3;Т->_0;T->_T1;T->_TT2;T->_TTT3
T1        T->T1_
TT        T->TT_2;T->TT_T3;T->T_1;T->T_T2;T->T_TT3;
          T->_0;T->_T1;T->_TT2;T->_TTT3
TT2       T->TT2_
TTT       T->TTT_3;T->TT_2;T->TT_T3;T->T_1;T->T_T2;T->T_TT3
          Т->_0;T->_T1;T->_TT2;T->_TTT3
TT0       = 0
TTT3      T->TTT3_
TTT2      = TT2
TTTT      = TT
TTT0      = 0

Конфликтов нет, это LR(0)-грамматика.

     (б)

Слово S                    Сост(S)
_______________________________________________

пустое    T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
0         Т->0_
1         Т->1_T;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
2         T->2_TT;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
3         T->3_TTT;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
1T        T->1T_
10        = 0
11        = 1
12        = 2
13        = 3
2T        T->2T_T;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
20        = 0
21        = 1
22        = 2
23        = 3
3T        T->3T_TT;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
30        = 0
31        = 1
32        = 2
33        = 3
2TT       T->2TT_
2T0       = 0
2T1       = 1
2T2       = 2
2T3       = 3
3TT       T->3TT_T;T->_0;T->_1Т;T->_2ТТ;T->_3ТТТ
3T0       = 0
3T1       = 1
3T2       = 2
3T3       = 3
3TTT      T->3TTT_
3TT0      = 0
3TT1      = 1
3TT2      = 2
3TT3      = 3

Конфликтов нет, это LR(0)-грамматика.

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

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

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

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

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

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

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

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

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

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

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

     Определение. Рассмотрим некоторую грамматику,  произвольное
слово  S  из  терминалов  и нетерминалов и терминал x. Если мно-
жество Сост(S) содержит ситуацию, в которой справа от  подчерки-
вания  стоит терминал x, то говорят, что для пары (S,x) возможен
сдвиг. Если в Сост(S) есть ситуация K->U_, причем x  принадлежит
Послед(K),  то  говорят,  что  для  пары  (S,x)  SLR(1)-возможна
свертка (по правилу K->U). Говорят, что для пары (S,x) возникает
конфликт типа сдвиг/свертка, если возможен и сдвиг,  и  свертка.
Говорят,   что   для   пары   (S,x)   возникает   конфликт  типа
свертка/свертка, если есть несколько правил, по которым возможна
свертка.
     Грамматика называется SLR(1)-грамматикой, если  в  ней  нет
конфликтов типа сдвиг/свертка и свертка/свертка ни для одной па-
ры (S,x).

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

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

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

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

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

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

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

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

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

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

     Решение. Ее нетерминалами будут символы <ЛевKt> для каждого
нетерминала K и для каждого терминала t (и для t=EOI). Ее прави-
ла  таковы. Пусть P - начальный нетерминал исхолной проамматики.
Тогда в новой грамматике будет правило
     <ЛевP EOI> ->      (пустое слово)
Для каждого правила исходной грамматики, например, для правила
     K-> L u M N (L, M, N - нетерминалы, u - терминал)
в новую грамматику мы добавим правила
     <ЛевL u> -> <ЛевK x>  (для всех терминалов x)
     <ЛевM s> -> <ЛевK y> L u
(для всех s, которые могут начинать слова, выводимые из N, и для
всех y, а также для всех s = y, если из N выводимо пустое слово)
     <ЛевN s> -> <ЛевK s> L u M (для всех теминалов s).

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

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

     14.4.3. Как изменится определение согласованности?

     Решение. Cлово S из терминалов и нетерминалов согласованo с
ситуацией  [K->U_V, t] (здесь t - терминал или EOI), если S кон-
чается на  U,  то  есть  S=TU,  и,  кроме  того,  T  принадлежит
Лев(K,t).

     14.4.4. Каковы правила  для  индуктивного  вычисления  мно-
жества Сост(S) ситуаций, согласованных с данным словом S?

     Ответ.  (1)  Если  слово  S  было  согласовано  с ситуацией
[K->U_V, t], причем слово V начиналось на букву J, то есть V=JW,
то теперь слово SJ будет согласовано с ситуацией [K->UJ_W,t].
     Это правило полностью определяет все  ситуации  с  непустой
левой  половиной (то есть не начинающиеся с подчеркивания), сог-
ласованные с SJ. Осталось определить, для каких нетерминалов K и
терминалов t слово SJ принадлежит Лев(K,t). Это делается по двум
правилам:
     (2) Если уже выяснено, что ситуация [L->U_V,t]  согласована
с  SJ  (по  правилу  (1)), а V начинается на нетерминал К, то SJ
принадлежит Лев(K,s) для всех терминалов s, которые могут  начи-
нать слова, выводимые из слова V\K (слово V без первой буквы K),
а также для s=t, если из V\K выводится пустое слово.
    (3) Если уже выяснено, что SJ входит в Лев(L,t) для  некото-
рых L и t, причем L->V - правило грамматики и  V  начинается  на
нетерминал K, то SJ принадлежит Лев(K,s) для всех терминалов  s,
которые могут начинать слова, выводимые из V\K, а также для s=t,
если из V\K выводится пустое слово.

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

     Решение.  Пусть дана некоторая грамматика. Пусть S - произ-
вольное слово  из  терминалов  и  нетерминалов.  Если  множество
Сост(S)  содержит  ситуацию,  в  которой справа от подчеркивания
стоит терминал t , то  говорят,  что  для  пары  (S,t)  возможен
сдвиг. (Это определение не изменилось по сравнению с SLR(1)-слу-
чаем - вторые компоненты пар из Сост(S) не учитываются.)
     Если в Сост(S) есть ситуация, в которой справа от подчерки-
вания ничего нет, а вторым членом пары является терминал  t,  то
говорят,  что  для  пары  (S,t) LR(1)-возможна свертка (по соот-
ветствующему правилу). Говорят, что  для  пары  (S,t)  возникает
конфликт  типа  сдвиг/свертка, если возможен и сдвиг, и свертка.
Говорят,  что   для   пары   (S,t)   возникает   конфликт   типа
свертка/свертка, если есть несколько правил, по которым возможна
свертка.
     Грамматика  называется  LR(1)-грамматикой,  если  в ней нет
конфликтов типа сдвиг/свертка и свертка/свертка  ни  для  одной
пары (S,t).

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

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

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

     14.4.7. Сформулировать и доказать соответствующее утвержде-
ние.

     Ответ. Пусть фиксирована некоторая грамматика. Слово  S  из
терминалов  и  нетерминалов является LR(0)-согласованным с ситу-
ацией K->U_V тогда и только тогда, когда оно LR(1)-согласовано с
парой [K->U_V,t] для некоторого терминала t (или для t=EOI).  То
же  самое  другими  словами: Лев(K) есть объединение Лев(K,t) по
всем t. В последней форме это совсем ясно.

     Замечание. Таким образом, функция  Сост(S)  в  LR(1)-смысле
является  расширением  функции  Сост(S) в LR(0)-смысле: Сост1(S)
получается из Сост0(S), если во всех парах выбросить вторые чле-
ны.

    Теперь мы можем дать определение  LALR(1)-грамматики.  Пусть
фиксирована  некоторая  грамматика,  S - слово из нетерминалов и
терминалов, t - некоторый терминал (или  EOI).  Будем  говорить,
что для пары (S,t) LALR(1)-возможна свертка по некоторому прави-
лу, если существует другое слово S1 с Сост0(S)=Сост0(S1), причем
для  пары (S1,t) LR(1)-возможна свертка по рассматриваемому пра-
вилу. Далее определяются  конфликты  (естественным  образом),  и
грамматика называется LALR(1)-грамматикой, если конфликтов нет.

    14.4.8.  Доказать,  что  всякая  SLR(1)-грамматика  является
LALR(1)-грамматикой,  а   всякая   LALR(1)-грамматика   является
LR(1)-грамматикой.
    Указание. Это - простое следствие определений.

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

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

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

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

    Применение этих методов на практике имеет  свои  хитрости  и
тонкости,  которых  мы  не  касались. (Например, таблицы следует
хранить по возможности экономно.) Часто оказывается  также,  что
для  некоторого  входного языка наиболее естественная грамматика
не является LL(1)-грамматикой, но является LR(1)-грамматикой,  а
также может быть заменена на LL(1)-грамматику без изменения язы-
ка.  Какой  из  этих  вариантов  выбрать,  не всегда ясно. Диле-
тантский совет: если Вы сами проектируете входной  язык,  то  не
следует  выпендриваться  и  употреблять одни и те же символы для
разных целей - и тогда обычно несложно написать LL(1)-грамматику
или рекурсивный анализатор. Если же входной язык задан заранее с
помощью  LR(1)-грамматики,  не  являющейся LL(1)-грамматикой, то
лучше ее не трогать, а разбирать как есть. При этом  могут  ока-
заться  полезные  средства автоматического порождения анализато-
ров, наиболее известными из которых являются yacc (UNIX) и bison
(GNU).

     Большое  количество полезной и хорошо изложенной информации
о теории и практике синтаксического  разбора  имеется  в  книге:
Alfred  V.  Aho,  Ravi  Sethi,  Jeffrey  D.  Ullman.  Compilers:
principles, techniques and tools. Addison Wesley (1985).