Восходящий синтаксический анализ соответствует построению дерева разбора начиная с листьев. Аналогично, это соответствует построению правого порождения для входной строки в обратном порядке.

В качестве типового метода восходящего синтаксического анализа будем рассматривать метод перенос/свёртка.

Метод перенос-свёртка

При использовании метода перенос-свёртка (далее ПС-анализ), для хранения символов грамматики используется, аналогично LL(1)-анализу, стек, а для входной строки – входной буфер. Из соображений удобства, при рассмотрении ПС-анализа, вершину стека будем располагать справа.

На каждом шаге анализа, принимается решение о том, какое действие должен совершить анализатор. Возможные действия – это перенос, свёртка, принятие и ошибка.

Перенос – это чтение символа из входной строки, помещение его на вершину стека, и переход к следующему символу входной строки. Иными словами, “перенос” очередного символа из входной строки на вершину стека.

Свёртка – это замена нескольких символов на вершине стека, совпадающих с телом какой-то продукции, на её заголовок. Иными словами, “свёртка” тела продукции в её заголовок.

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

Использование стека обусловлено тем, что при рассмотрении правого порождения (в обратном порядке), тело очередной продукции, которая может быть свёрнута, будет всегда находиться в самой правой позиции, что соответствует вершине стека.

Конфликты при ПС-анализе

При ПС-анализе, на очередном шаге анализа возможны два типа конфликтов:

1. Конфликт перенос/свёртка – соответствует ситуации, когда анализатор не может на основе имеющейся у него информации принять решение о том, следует ли на данном шаге произвести свёртку или перенос.
2. Конфликт свёртка/свёртка – соответствует ситуации, когда анализатор не может на основе имеющейся у него информации принять решение о том, следует ли на данном шаге произвести свёртку, соответствующую одной или другой продукции.

Чаще всего, конфликты свидетельствуют о неоднозначности грамматики. Реже – о том, что конкретный анализатор (использующий \(k\) символов предпросмотра) недостаточно мощный для данной грамматики.

LR-анализ

Наиболее распространённый тип анализаторов типа перенос-свёртка основан на принципе LR-анализа, разработанном Д. Кнутом в 1965 году¹.

LR-анализ соответствует автомату с магазинной памятью, реализующему, собственно, перенос/свёртку, программа которого управляется детерминированным конечным автоматом. При этом, на каждом шаге из входной строки читается \(k\) символов, где \(k \in \mathbb N\) – константа. Собственно, любой LR-анализатор для какого-то \(k\) называется LR(k)-анализатором, а множество грамматик, которые может разбирать LR(k)-анализатор называется LR(k)-грамматиками.

Так же доказано², что для любого фиксированного \(k \ge 1\), язык имеет LR(k) грамматику тогда и только тогда, когда он является детерминистическим контекстно-свободным языком, т.е. языком, который может быть разобран детерминированным автоматом с магазинной памятью. Следует, правда, отметить, что множество всех детерминистических контекстно-свободных языков является строгим подмножеством всех однозначных контекстно-свободных языков (т.е. языков для которых существует однозначная грамматика), поэтому не все однозначные языки могут быть разобраны при помощи LR-анализа. Впрочем, для большинства языков возможно написать LR-анализатор (используя таблицу символов для разрешения неоднозначностей), одно из известных исключений – C++, который является LR(∞)-языком.

Как следствие, для любого LR(k)-языка существует LR(1)-грамматика, соответственно множество всех LR-языков (т.е. порождаемых LR(k)-грамматиками для любых конечных k) есть множество LR(1)-языков. Отметим так же, что LR(0)-язык должен дополнительно обладать свойством префиксного кода, т.е. никакое предложение языка не должно быть префиксом другого предложения.

Множество LR-грамматик есть истинное надмножество LL-грамматик. В LR-анализе мы должны распознать правую часть продукции на вершине стека с дополнительным предпросмотром k входных символов. Это требование гораздо более мягкое, чем для LL(k) грамматик где необходимо “угадать” продукцию по первым k символам некого порождения её правой части.

Основной недостаток LR-анализа в относительной сложности построения анализатора, однако он “исправляется” использованием автоматических генераторов. По большому счёту, “хороших” (т.е. формально обоснованных) причин для того, чтобы использовать LL-анализатор или рекурсивный спуск вместо LR-анализатора нет. Однако, для простых, “одноразовых” языков, проще бывает написать LL-грамматику или даже написать рекурсивный анализатор “на коленке”.

Мы рассмотрим несколько подходов к LR-анализу. Сначала мы рассмотрим LR(0)-анализ, который практически не слишком значителен, однако сравнительно прост. Затем, рассмотрим как LR(0) анализ может быть улучшен эвристическими методами (т.н. SLR-анализ). Наконец, мы рассмотрим LR(1)-анализ и кратко обсудим упрощение LR(1), называемое LALR.

LR(0)

LR-анализатор принимает решение о выборе между переносом и свёрткой, отслеживая, в каком месте тела продукции находится анализ.

Это реализуется при помощи состояний, называемых “пунктами”. LR(0)-пункты описываются в виде продукций с точкой в “текущем” месте. Так, продукция \(A \to X Y Z\) имеет 4 пункта \[\begin{align} A & \to . X Y Z \\ A & \to X . Y Z \\ A & \to X Y . Z \\ A & \to X Y Z . \\ \end{align}\]

Продукция с пустым телом \(A \to ε\) имеет единственный пункт \(A \to .\)

Замыкание множества пунктов

Пусть \(I\) – множество пунктов грамматики \(G\). Тогда \(I^+\) – замыкание множества пунктов, соответствующее правилу:

Если \((A \to α . B β) \in I^+,\) и \(\exists (B \to γ),\) то \((B \to . γ) \in I^+\).

Интуитивно, если в замыкании присутствует \(A \to α . B β,\) то мы ожидаем во входной строке порождения из \(B\), и поэтому мы добавляем первые пункты всех продукций B в замыкание.

Вторая часть, определяющая LR(0)-автомат – функция переходов GOTO. Переход в LR(0)-анализе однозначно определяется текущим состоянием (множеством пунктов I) и текущим грамматическим символом X. \[\mathrm{GOTO}(I,X) = \{ A → α X . β | A → α . X β ∈ I \}^+\]

Один набор пунктов LR(0), называемый каноническим, служит для построения ДКА, называемого LR(0)-автоматом, который используется в процессе анализа. Каждое состояние такого автомата представляет множество LR(0)-пунктов.

Для упрощения построения автомата, грамматики обычно расширяют правилом \(S' \to S\), где \(S\) – стартовый символ исходной грамматики, \(S'\) – стартовый символ новой грамматики. Будем называть это новое правило продукции стартовым правилом (или стартовой продукцией).

Канонический набор \(C\) строится на основе функции переходов начиная с замыкания первого пункта стартовой продукции:

\[\begin{align} & \{S' \to .S\}^+ \in C \\ & \forall I \in C, \forall X \in N \cup T: \mathrm{GOTO}(I, X) \in C \\ \end{align}\]

По сути, \(C\) представляет собой замыкание \(\{\{S' \to S\}^+\}\) по функции \(\mathrm{GOTO}\) для всех символов грамматики.

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

“Чистый” LR(0)-анализ

Пронумеруем все элементы канонического набора \(C\) таким образом, чтобы множеству пунктов, содержащему первый пункт стартовой продукции, соответствовал \(0\). Построим LR(0)-автомат, использующий эти номера в качестве номеров состояний. Переходы между состояниями определяются функцией \(\mathrm{GOTO}\).

Будем использовать LR(0)-автомат для принятия решения о действии, совершаемом на очередном шаге анализа. Сам анализ будем производить при помощи автомата с магазинной памятью.

На стеке будем хранить номера состояний LR(0)-автомата. Символы грамматики могут быть однозначно восстановлены по номерам состояний, исходя из того, какой символ находится слева от точки в соответствующем пункте состояния.

Анализатор управляется стеком состояний \(s\), текущим входным символом \(a\) и двумя таблицами, таблицей действий \(\mathrm{ACTION}[s, a]\) и таблицей переходов \(\mathrm{GOTO}[s, X]\). Последняя строится по функции переходов, первая же может отличаться в зависимости от типа анализа.

Программу LR-анализа можно записать в виде псевдокода

a = getNextToken();
while(true) {
  s = stack.top();
  if(ACTION[s, a] = перенос) {
    stack.push(GOTO[s, a]);
    a = getNextToken();
  } else if (ACTION[s, a] = свёртка A -> β) {
    for (i in 1…|β|) stack.pop();
    t = stack.top();
    stack.push(GOTO[t, A]);
    print("A -> β");
  } else if (ACTION[s, a] = принятие) {
    break;
  } else { // ACTION[s, a] = ошибка
    reportError();
  }
}

В рамках некоторой оптимизации, обычно оставляют только часть таблицы GOTO, содержащую переходы по нетерминалам, а информацию о новом состоянии GOTO[s, a] при переносе помещают прямо в таблицу ACTION:

// ...
if(ACTION[s, a] = перенос j) {
  stack.push(j); // j = GOTO[s, a]
  a = getNextToken();
} // ...

Таблица \(\mathrm{ACTION}[s, t]\) для “чистого” LR(0)-анализа строится тривиально:

1. \(\mathrm{ACTION}[s, t] =\) перенос \(j,\) если \(GOTO[s, t] = j\) и \(j\) не соответствует “тупиковому” состоянию.
2. \(\mathrm{ACTION}[s, t] =\) свёртка по продукции \(A \to \alpha\), такой, что последний пункт этой продукции входит в \(s\)-тый элемент канонического набора пунктов \(C\): \((A \to \alpha .) \in I_s,\) \(I_s \in C\).

Отметим, что \(\mathrm{ACTION}[s, t]\) для свёртки не зависит от \(t\). Как следствие, если состояние соответствует последним пунктам нескольких продукций, неизбежно возникает конфликт свёртка/свёртка.

Более того, во многих случаях возникнет конфликт перенос/свёртка.

SLR

Конфликты свёртка/свёртка и перенос/свёртка, возникающие при LR(0)-анализе, можно устранить на основе простых эвристик. В частности, в случае конфликтов пернос/свёртка, можно детерминировано делать выбор в пользу переноса или свёртки. Немного более сложная эвристика – алгоритм SLR.

Алгоритм SLR дополнительно ограничивает случаи, когда возможна свёртка, на основе функции \(\mathrm{FOLLOW}\). Конкретно, второе правило для LR(0) модифицируется следующим образом:

2. \(\mathrm{ACTION}[s, t] =\) свёртка по продукции \(A \to \alpha\), такой, что \((A \to \alpha .) \in I_s,\) \(I_s \in C\), и (здесь изменение) \(t \in \mathrm{FOLLOW}(A)\).

Это небольшое изменение позволяет устранить большой класс “очевидных” конфликтов типа перенос/свёртка и свёртка/свёртка.

Пример

Рассмотрим грамматику \[\begin{align} E & \to E + T | T \\ T & \to T * F | F \\ F & \to ( E ) | val \\ \end{align}\]

Расширим эту грамматику стартовым правилом: \[\begin{align} S & \to E \\ E & \to E + T | T \\ T & \to T * F | F \\ F & \to ( E ) | val \\ \end{align}\]

Построим LR(0)-автомат для этой грамматики. Начальное состояние: \[\begin{array}{rll} I_0 = \{S \to .E\}^+ = \{ & S\to .E, \\ & E\to .E+T, \\ & E\to .T, \\ & T \to .T*F, \\ & T \to .F, \\ & F \to .(E), \\ & F \to .val \} \end{array}\]

Функция переходов: \[\begin{align} \mathrm{GOTO}(I_{0}, E) = & I_{1} \\ = & \{\\ & \begin{array}{l} S\to E. \\ E\to E.+T \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, T) = & I_{2} \\ = & \{\\ & \begin{array}{l} E\to T. \\ T\to T.*F \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, F) = & I_{3} \\ = & \{\\ & \begin{array}{l} T \to F. \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, () = & I_{4} \\ = & \{\\ & \begin{array}{l} F \to (.E) \\ \hline E\to .E+T \\ E\to .T \\ T \to .T*F \\ T \to .F \\ F \to .(E) \\ F \to .val \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, val) = & I_{5} \\ = & \{\\ & \begin{array}{l} F \to val. \\ \hline \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{1}, +) = & I_{6} \\ = & \{\\ & \begin{array}{l} E \to E+.T \\ \hline T \to .T*F \\ T \to .F \\ F \to .(E) \\ F \to .val \\ \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{2}, *) = & I_{7} \\ = & \{\\ & \begin{array}{l} T\to T*.F \\ \hline F \to .(E) \\ F \to .val \\ \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{4}, E) = & I_{8} \\ = & \{\\ & \begin{array}{l} F \to (E.) \\ E\to E.+T \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{4}, T) = & I_{2} \\ \mathrm{GOTO}(I_{4}, F) = & I_{3} \\ \mathrm{GOTO}(I_{4}, () = & I_{4} \\ \mathrm{GOTO}(I_{4}, val) = & I_{5} \\ \hline \mathrm{GOTO}(I_{6}, T) = & I_{9} \\ = & \{\\ & \begin{array}{l} E \to E+T. \\ T \to T.*F \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{6}, F) = & I_{3} \\ \mathrm{GOTO}(I_{6}, () = & I_{4} \\ \mathrm{GOTO}(I_{6}, val) = & I_{5} \\ \hline \mathrm{GOTO}(I_{7}, F) = & I_{10} \\ = & \{\\ & \begin{array}{l} T \to T*F. \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{7}, () = & I_{4} \\ \mathrm{GOTO}(I_{7}, val) = & I_{5} \\ \hline \mathrm{GOTO}(I_{8}, )) = & I_{11} \\ = & \{\\ & \begin{array}{l} F \to (E). \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{8}, +) = & I_{6} \\ \hline \mathrm{GOTO}(I_{9}, *) = & I_{7} \\ \end{align}\]

Здесь начальные пункты отделены от пунктов, получаемых при построении замыкания, горизонтальной чертой. Не указанные комбинации аргументов дают пустое множество – тупиковое состояние \(I_\varnothing\).

Диаграмма переходов:

Вычислим FOLLOW для всех нетерминальных символов грамматики:

\[\begin{align} \mathrm{FOLLOW}(E) & = \{+, ), $\} \\ \mathrm{FOLLOW}(T) & = \{*, +, ), $\} \\ \mathrm{FOLLOW}(F) & = \{*, +, ), $\} \\ \end{align}\]

Пронумеруем продукции следующим образом: \[\begin{align} E & \to E + T & (1) \\ E & \to T & (2)\\ T & \to T * F & (3)\\ T & \to F & (4)\\ F & \to ( E ) & (5) \\ F & \to val & (6)\\ \end{align}\]

Тогда пусть si обозначает перенос и переход в состояние i, rj обозначает свёртку по j-той продукции.

Теперь построим таблицы ACTION и GOTO:

Следует отметить, что при LR(0)-анализе, в строках 2 и 9 для символа * возник бы конфликт перенос-свёртка (эти места в таблице выделены полужирным), поскольку LR(0) полагает свёртку для всех символов. В то же время, r1 и r2 (свёртки в символ \(E\)) невозможны для входного символа *, поскольку \(* \notin \mathrm{FOLLOW}(E)\).

Отметим также, что в случае варианта LR(0), всегда предпочитающего перенос, эта грамматика тоже разбирается.

Рассмотрим теперь, как будет разбираться строка val+val*val.

LR(1)

LR(1) аналогичен SLR, с одним ключевым отличием: дабы исключить часть конфликтов перенос/свёртка, LR(1)-пункты дополнительно включают один символ предпросмотра, то есть LR(1)-пункт может иметь вид, скажем \([A \to α . B β, a]\). Здесь \(a\) – это символ, который следует после \(β\).

Соответственно модифицируются определения замыканий LR(1)-пунктов и функция переходов.

Замыкание

Пусть I – множество пунктов грамматики G. Тогда I⁺ – замыкание множества пунктов, соответствующее правилу:

Если \([A \to α . B β, a] \in I^+,\) и \(\exists (B \to γ),\) то \(\forall b \in \mathrm{FIRST}(β a), [B \to . γ, b] \in I^+\).

Это определение интуитивно понятно: после строки \(α B β\) мы ожидаем терминал \(a\); тогда после \(B\) разумно ожидать терминалы, входящие в \(\mathrm{FIRST}(β a)\) (полагая, что возможно \(β \overset{*}\Rightarrow ε\)).

Определение \(\mathrm{GOTO}\) практически не меняется, так как переход не влияет на символ предпросмотра: \[\mathrm{GOTO}(I,X) = \{ [A \to α X . β, a] | [A \to α . X β, a] ∈ I \}^+\]

Таблица действий строится как

1. Если \(\mathrm{GOTO}(i, a) = j,\) то \(\mathrm{ACTION}[i, a] =\) перенос. a – терминал.
2. Если \([A \to α ., a] \in I_i\), то \(\mathrm{ACTION}[i, a] =\) свёртка A → α.

Пример

Рассмотрим расширенную грамматику \[\begin{align} S' & \to S \\ S & \to C C \\ C & \to c C | d \\ \end{align}\]

Нетерминалы: \(\{S', S, C\}\)
Терминалы: \(\{c, d\}\)
Стартовый символ: \(S'\)

Построим LR(1)-автомат для этой грамматики. Вычислим \(\mathrm{FIRST}\) для всех нетерминалов: \[\begin{align} \mathrm{FIRST}(S') & = \mathrm{FIRST}(S) \\ \mathrm{FIRST}(S) & = \mathrm{FIRST}(C) \\ \mathrm{FIRST}(C) & = \{c, d\} \\ \end{align}\]

Начальное состояние: \[\begin{array}{rll} I_0 = \{[S' \to .S, $]\}^+ = \{ & [S' \to .S, $], \\ & [S\to .C C, $], \\ & [C\to .c C, c/d], \\ & [C\to .d, c/d] \} \end{array}\]

Функция переходов: \[\begin{align} \mathrm{GOTO}(I_{0}, S) = & I_{1} \\ = & \{\\ & \begin{array}{l} [S' \to S., $] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, C) = & I_{2} \\ = & \{\\ & \begin{array}{l} [S\to C .C, $] \\ \hline [C\to .c C, $] \\ [C\to .d, $] \\ \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, c) = & I_{3} \\ = & \{\\ & \begin{array}{l} [C\to c .C, c/d] \\ \hline [C\to .c C, c/d], \\ [C\to .d, c/d] \\ \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, d) = & I_{4} \\ = & \{\\ & \begin{array}{l} [C\to d., c/d] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, C) = & I_{5} \\ = & \{\\ & \begin{array}{l} [S\to C C., $] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, c) = & I_{6} \\ = & \{\\ & \begin{array}{l} [C\to c .C, $] \\ \hline [C\to .c C, $], \\ [C\to .d, $] \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, d) = & I_{7} \\ = & \{\\ & \begin{array}{l} [C\to d., $] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{3}, C) = & I_{8} \\ = & \{\\ & \begin{array}{l} [C\to c C., c/d] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{3}, c) = & I_{3} \\ \mathrm{GOTO}(I_{3}, d) = & I_{4} \\ \mathrm{GOTO}(I_{6}, C) = & I_{9} \\ = & \{\\ & \begin{array}{l} [C\to c C., $] \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{6}, c) = & I_{6} \\ \mathrm{GOTO}(I_{6}, d) = & I_{7} \\ \end{align}\]

Диаграмма переходов:

Пронумеруем правила грамматики \[\begin{align} S & \to C C & (1)\\ C & \to c C & (2)\\ C & \to d & (3)\\ \end{align}\]

LALR(1)

LALR(1) – это упрощение LR(1), в котором используется множество пунктов LR(0), но каждый из них расширен множеством допустимых символов предпросмотра из соответствующих LR(1)-пунктов. При этом, количество состояний совпадает с количеством состояний в SLR, но вероятность возникновения конфликтов перенос/свёртка ниже – хотя и выше чем в полноценном LR(1) анализе.

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

Пример

Рассмотрим пример для LR(1). Состояния 4 и 7 содержат первой частью пункта \(C \to d .\); состояния 3 и 6 – \(C\to c.C\); состояния 8 и 9 – \(C\to cC.\); Объединим эти пары состояний в новые состояния 47, 36 и 89 соответственно.

Использование приоритета и ассоциативности для разрешения неоднозначности

Рассмотрим неоднозначную грамматику выражений \[E \to E + E | E * E | (E) | val.\]

Она очевидно является неоднозначной, поскольку не определяет ни ассоциативность, ни приоритет операторов \(+\) и \(*\). Ранее мы рассматривали однозначную грамматику, порождающую тот же язык, которая включала приоритет и ассоциативность операторов непосредственно в определение. С другой стороны, определение той грамматики достаточно объёмное по сравнению с неоднозначным. Возникает вопрос: нельзя ли разрешить конфликты, возникающие в силу неоднозначности грамматики, используя информацию о приоритете и ассоциативности операторов? Попробуем построить SLR-анализатор для этой неоднозначной грамматики.

Введём правило расширенной грамматики \[S\to E\]

Построим LR(0)-автомат. Начальное состояние: \[\begin{array}{rll} I_0 = \{S \to .E\}^+ = \{ & S \to .E \\ & E \to .E + E \\ & E \to .E * E \\ & E \to .(E) \\ & E \to .val \\ \} \end{array}\]

Функция переходов: \[\begin{align} \mathrm{GOTO}(I_{0}, E) = & I_{1} \\ = & \{\\ & \begin{array}{l} S \to E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, () = & I_{2} \\ = & \{\\ & \begin{array}{l} E \to (.E) \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, val) = & I_{3} \\ = & \{\\ & \begin{array}{l} E \to val. \\ \hline \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{1}, +) = & I_{4} \\ = & \{\\ & \begin{array}{l} E \to E + . E \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \mathrm{GOTO}(I_{1}, *) = & I_{5} \\ = & \{\\ & \begin{array}{l} E \to E * . E \\ \hline E \to .E + E \\ E \to .E * E \\ E \to .(E) \\ E \to .val \\ \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{2}, E) = & I_{6} \\ = & \{\\ & \begin{array}{l} E \to (E.) \\ E \to E .+ E \\ E \to E .* E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, () = & I_{2} \\ \mathrm{GOTO}(I_{2}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{4}, E) = & I_{7} \\ = & \{\\ & \begin{array}{l} E \to E + E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{4}, () = & I_{2} \\ \mathrm{GOTO}(I_{4}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{5}, E) = & I_{8} \\ = & \{\\ & \begin{array}{l} E \to E * E . \\ E \to E . + E \\ E \to E . * E \\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{5}, () = & I_{2} \\ \mathrm{GOTO}(I_{5}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{6}, +) = & I_{4} \\ \mathrm{GOTO}(I_{6}, *) = & I_{5} \\ \mathrm{GOTO}(I_{6}, )) = & I_{9} \\ = & \{\\ & \begin{array}{l} E \to (E). \\ \hline \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{7}, +) = & I_{4} \\ \mathrm{GOTO}(I_{7}, *) = & I_{5} \\ \hline \mathrm{GOTO}(I_{8}, +) = & I_{4} \\ \mathrm{GOTO}(I_{8}, *) = & I_{5} \\ \end{align}\]

Здесь начальные пункты отделены от пунктов, получаемых при построении замыкания, горизонтальной чертой. Не указанные комбинации аргументов дают пустое множество – тупиковое состояние \(I_\varnothing\).

Диаграмма переходов:

Вычислим FOLLOW для всех нетерминальных символов грамматики:

\[\begin{align} \mathrm{FOLLOW}(S) & = \{$\} \\ \mathrm{FOLLOW}(E) & = \{*, +, ), $\} \\ \end{align}\]

Пронумеруем продукции следующим образом: \[\begin{align} E & \to E + E & (1)\\ E & \to E * E & (2)\\ E & \to (E) & (3)\\ E & \to val & (4)\\ \end{align}\]

Теперь построим таблицу ACTION:

Мы видим, что ожидаемо возникают конфликты перенос/свёртка для символов \(+\) и \(*\).

В состояние 7 анализатор попадает, разобрав строку \(E+E\). Конфликт для символа \(+\) связан с отсутствием в грамматике информации об ассоциативности оператора \(+\). Если оператор левоассоциативен, то приоритетной должна быть свёртка (поскольку выражение \(E+E+E\) должно быть интерпретировано как \((E+E)+E\), и мы должны свернуть первый прочитанный \(E+E\) как если бы он был в скобках). Если правоассоциативен – то перенос (соображения аналогичные).

Конфликт в состоянии 7 для символа \(*\) связан с отсутствием информации об относительном приоритете операторов \(+\) и \(*\). Если \(+\) имеет меньший приоритет, то выбор должен быть сделан в пользу переноса (действительно, выражение \(E+E*E\) должно быть разобрано как \(E+(E*E)\), и тогда, прочитав в нём \(E+E\) мы должны прочитать \(*\), чтобы можно было произвести свёртку \(E*E\)). Если \(*\) имеет меньший приоритет, то выбор – в пользу свёртки. Если приоритет одинаковый, то выбор определяется ассоциативностью.

Аналогично можно рассуждать о конфликтах в состоянии 8, в которое анализатор приходит, прочитав строку \(E*E\).

Тогда для левоассоциативных операторов, и \(*\) имеющего более высокий приоритет, таблицу \(\mathrm{ACTION}\) можно записать:

Таблица GOTO (только значащие строки):

Здесь может показаться, что мы определяем приоритет и ассоциативность для токенов, однако на самом деле мы определяем их также и для правил грамматики, содержащих эти токены. Показательным будет пример для грамматики с унарным оператором \(-\): \[\begin{align} E & \to E - E | - E | val \end{align}\]

Начальное состояние \[\begin{align} I_0 = \{S\to .E\}^+ = \{ & S\to E\\ & E\to .E - E\\ & E\to . - E\\ & E\to . val\\ \} \end{align}\]

Здесь оператор \(-\) имеет разный приоритет (и ассоциативность) в разных продукциях.

Функция \(\mathrm{GOTO}\):

\[\begin{align} \mathrm{GOTO}(I_{0}, E) = & I_{1} \\ = & \{\\ & \begin{array}{l} S \to E . \\ E\to E. - E\\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, -) = & I_{2} \\ = & \{\\ & \begin{array}{l} E\to - . E\\ \hline E\to .E - E\\ E\to . - E\\ E\to . val\\ \end{array}\\ & \} \\ \mathrm{GOTO}(I_{0}, val) = & I_{3} \\ = & \{\\ & \begin{array}{l} E\to val .\\ \hline \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{1}, -) = & I_{4} \\ = & \{\\ & \begin{array}{l} E\to E - .E\\ \hline E\to .E - E\\ E\to . - E\\ E\to . val\\ \end{array}\\ & \} \\ \hline \mathrm{GOTO}(I_{2}, E) = & I_{5} \\ = & \{\\ & \begin{array}{l} E\to - E .\\ E\to E . - E\\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{2}, -) = & I_{2} \\ \mathrm{GOTO}(I_{2}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{4}, E) = & I_{6} \\ = & \{\\ & \begin{array}{l} E\to E - E .\\ E\to E . - E\\ \hline \end{array}\\ & \} \\ \mathrm{GOTO}(I_{4}, -) = & I_{2} \\ \mathrm{GOTO}(I_{4}, val) = & I_{3} \\ \hline \mathrm{GOTO}(I_{5}, -) = & I_{4} \\ \hline \mathrm{GOTO}(I_{6}, -) = & I_{4} \\ \end{align}\]

Номера продукций: \[\begin{align} E & \to E - E & (1) \\ E & \to - E & (2) \\ E & \to val & (3) \\ \end{align}\]

\[\mathrm{FOLLOW}(E) = \{-, \$\}\]

Таблица \(\mathrm{ACTION}\):

В состоянии 5 автомат оказывается, прочитав строку \(-E\). Обнаружив очередной \(-\), он должен произвести свёртку, так как унарный минус имеет более высокий приоритет, чем бинарный.

Таким образом, продукция \(E\to -E\) имеет более высокий приоритет, чем продукция \(E \to E - E\), и тогда, в случае конфликта, производится операция, связанная с этой продукцией.

Рассмотрим как автомат будет читать строку \(val--val-val\):