LR(1)-анализ

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

Модифицируются определения:

Замыкание

Пусть \(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 \to α\).

Пример

Рассмотрим расширенную грамматику \[\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}\]

\( \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} \\ \)

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

ACTION c d $ GOTO S C
0 s3 s4 0 1 2
1 acc 1
2 s6 s7 2 5
3 s3 s4 3 8
4 r3 r3 4
5 r1 5
6 s6 s7 6 9
7 r3 7
8 r2 r2 8
9 r2 9

LALR(1)

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

Способ построения:

  • построить LR(1)
  • отождествить состояния с одинаковыми первыми компонентами LR(1)-пунктов

Пример

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

ACTION c d $ GOTO S C
0 s36 s47 0 1 2
1 acc 1
2 s36 s47 2 5
36 s36 s47 36 89
47 r3 r3 r3 47
5 r1 5
89 r2 r2 r2 89