| | нетерминала) then begin
| | error := true;
| end;
end;
{входное слово выводимо <=> not error}
Алгоритм заканчивает работу, поскольку при появлении нетерминала
в начале слова S происходит чтение со входа или остановка, а
бесконечный цикл сменяющих друг друга терминалов в начале S оз-
начал бы, что грамматика леворекурсивна.
Замечания. 1. Приведенный алгоритм использует S как стек
(все действия производятся с левого конца).
2. Действия двух последних вариантов внутри цикла не приво-
дят к чтению очередного символа со входа, поэтому их можно зара-
нее предвычислить для каждого нетерминала и каждого символа
Next. После этого на каждом шаге цикла будет читаться очередной
символ входа.
3. При практической реализации удобно составить таблицу, в
которой записаны варианты действий в зависимости от входного
символа и первого символа S, и небольшую программу, выполняющую
действия в соответствии с этой таблицей.
Глава 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 (что со-
