Рассмотрим грамматику:

(1) (2) (3) (4) (5) (6)

S1T2else3F4;11 T1i6;8

F1E7

E(1,3)E(5,7) +9i10 E(1,3)i(6,12)

где добавлены номера состояний. Эти 12 состояний соответствуют следующим конфигурациям (в расширенном смысле этого термина):

состояние 1

состояние 2 состояние 3

состояние 4 состояние 5

состояние 6

состояние 7

состояние 8 состояние 9 состояние 10 состояние 11 состояние 12

(1, 0),{"1"} (2, 0),{else} (3, 0),{else} (5, 0),{else"+"} (6, 0),{else"+"}

(1, 2),{"1"} (4, 0),{ ";"} (5, 0),{ ";","+"} (6, 0),{ ";","+"}

(1, 3),{"1"}

(2, 1),{else}

(5, 1),{else"+"}

(3, 1),{else}

(6, 1),{else"+"}

(4, ";"}

(5, ";","+"}

(3, 2),{else}

(5, 2), {";",else",+"}

(5, 3), {";",else",+"}

(1, 4),{"1"} (6, ";","+"}

При определении множеств символов-следователей применяется ряд правил: В конфигурации (1, 0) множество символов-следователей состоит из {1}, так как левой частью порождающего правила служит начальный символ, не появляющийся в правой части ни одного из правил. (Для грамматики, в которой начальный символ не обладает этим свойством, желательно ввести с помощью дополнительного правила новый начальный символ S, обладающий указанным свойством, SS1.)

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

Таким образом,

(2, 0), {else} (3, 0), {else}

представляют собой конфигурации (в смысле LALR(l)) состояния 1. (5,0) и (6,0) также являются конфигурациями в состоянии 1. В случае (6,0) else находится в множестве символов-следователей, так как может следовать за Е, поэтому есть символ-следователь Т. Символ + также находится в множестве символов-следователей, поскольку Е можно "вызвать" из правила "5". Итак, конфигурация LALR(l) имеет вид

(6, 0),{else,

Аналогично

(5, 0),{else, ""+"}

находится в состоянии 1.

3. Выполнение операции нахождения символа-следователя для конфигурации не влияет на множество символов-следователей. Например, (1, 0) в состоянии 1 и (1, 1) в состоянии 2 имеют одно и то же множество символов-следователей ({ 1})- Однако в состоянии 9 (конфигурация (5, 2)) множества символов-следователей, соответствующие конфигурациям (5, 1), {else, "+"} (состояние 5) и (5, 1), {";", "+"} (состояние 7), слиты вместе, так как алгоритм LALR не допускает разных состояний для неразличимых множеств SLR (или LR(0)) конфигураций. Таблица разбора с включенными элементами сдвигов представлена табл 5.5.

Т а б л и ц а 5.5

Эта грамматика не обладает признаком LR(0), так как, например, мы не можем поместить элементы приведения в каждый столбец для состояния 5, что может соответствовать окончанию правила. Не обладает она также и признаком SLR(l), так как в противном случае из правила (6) мы могли бы взять элемент приведения в столбец ";" для состояния 6, поскольку ";" есть действительный символ-следователь E (раз он следует за F в смысле SLR(l)). Однако включение действия приведения в столбец ";" состояния 6 приведет к конфликту с уже имеющимся в этой позиции действием сдвига. Конфликт можно разрешить, если, как видно из дополненных конфигураций, соответствующих каждому состоянию, else и "+" служат единственными действительными символами-следователями в состоянии 6. Таким образом, алгоритм LALR только поместит действия R6 в столбцы else и "+" в состоянии 6. Продолжив этот процесс далее, мы построим полную таблицу LALR(l)-разбора (табл. 5.6).

Т а б л и ц а 5.6

Здесь относительно не много элементов приведения, и отсутствуют конфликты. Если бы алгоритм LALR(l) не смог разрешить какие-либо конфликты, на следующем шаге мы должны были бы попытаться применить алгоритм LR(1). Для этого нам понадобилось бы ввести дополнительные состояния. Например, состояние 10 пришлось бы разбить на два состояния, соответствующие

(5, 3), {";", "+"} и

(5, 3), {else, "+"}

причем каждое состояние соответствует одной и той же конфигурации (конфигурациям), но имеет различные символы-следователи. Таким образом, будет запоминаться больший объем левого контекста - в данном случае: должно ли E приводиться к F или Т. Анализатору фактически не нужна эта информация, так как состояния, в котортх Е приводится к Т и к F, различны. Потребность в алгоритме LR(1) возникает редко, но когда она возникает, число используемтх состояний обычно намного превышает, то, которое бывает в алгоритме LALR(l).

Описанный ранее алгоритм разбора остается постоянным независимо от того, какая разбирается грамматика: LR(0), SLR(l), LALR(l) или LR(1). Только алгоритм построения таблицы разбора становится сложнее по мере возрастания универсальности грамматики. Размер таблицы, т.е. число состояний, одинаков вне зависимости от используемого алгоритма - LR(0), SLR(l) или LALR(l). Лишь LR(1)-алгоритм создает большую таблицу. Метод, позволяющий решить, обладает ли грамматика признаком LR(1), заключается в попытке сформировать таблицу LR(0)-разбора. Если это можно осуществить без возникновения каких-либо конфликтов, грамматика оказывается LR(0)-грамматикой, а, следовательно, и LR(1)-грамматикой. Если же конфликты возникают, опробуется SLR(1)-алгоритм. При успешной попттке грамматика будет SLR(l)-грамматикой, а следовательно, и LR(l)-грамматикой. В ином случае пробуется алгоритм LALR(l), и если это разрешает все конфликты, то можно считать, что грамматика обладает признаком LALR(l), а значит, и признаком LR(l). И, наконец, если конфликты остаются, выполняется алгоритм LR(1), и грамматика является LR(1)-грамматикой или нет в зависимости от того, какие именно конфликты имеют место: сдвиг/приведение или приведение/приведение. Конечно, можно было