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

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

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

Два типа конфликтов:

1. Конфликт перенос/свёртка – анализатор не может выбрать между переносом и свёрткой
2. Конфликт свёртка/свёртка – анализатор не может выбрать между свёрткой по различным продукциям

• соответствует автомату с магазинной памятью, реализующему перенос/свёртку,
• программа автомата управляется детерминированным конечным автоматом
• на каждом шаге из входной строки читается \(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(1)-языков.
• LR(0)-язык должен обладать свойством префиксного кода, т.е. никакое предложение языка не должно быть префиксом другого предложения.
• \(LL \subsetneq LR\)
• В LR-анализе распознаётся правая часть продукции на вершине стека с дополнительным предпросмотром k входных символов
• гораздо более мягкое требование, чем угадывание продукции по первым k символам некого порождения её правой части в случае LL(k)

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

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

Пункты

• анализатор принимает решение о действии, отслеживая, в каком месте тела продукции находится анализ.
• реализуется при помощи состояний, называемых “пунктами”
• 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
• Переход однозначно определяется текущим состоянием (множеством пунктов 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-анализатор управляется:

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

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:

Таблица \(\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\), если \((A \to \alpha .) \in I_s,\) \(I_s \in C\).

• 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}\]

Построим 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}\]