ла таковы. Пусть 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).
