LR(1)-разбор

В некоторых случаях SLR-разбор может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и LALR-разбор. Рассмотрим первый из них.

Отличия от SLR-разбора

Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра (англ. lookahead) символов.

Приведём пример, при котором SLR-разбор не справится с задачей:

Рассмотрим грамматику вида: $ S \to L=R \mid R \\ L \to *R \mid id \\ R \to L $

Покажем её канонический LR(0)-набор:

$I_0$	$I_1$	$I_2$	$I_3$	$I_4$	$I_5$	$I_6$	$I_7$	$I_8$	$I_9$
$S' \to \cdot S \\ S \to \cdot L = R \\ S \to \cdot R \\ L \to \cdot * R \\ L \to \cdot id \\ R \to \cdot L$	$S' \to S \cdot$	$S \to L \cdot = R \\ R \to L \cdot$	$S \to R \cdot$	$L \to * \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$	$L \to id \cdot$	$S \to L = \cdot R \\ R \to \cdot L \\ L \to \cdot * R \\ L \to \cdot id$	$L \to * R \cdot$	$R \to L \cdot$	$S \to L = R \cdot$

Рассмотрим состояние $I_2$. Если SLR-парсер находится в $I_2$ и очередной входной символ равен $=$, то парсер выполняет свёртку в соответствии с ситуацией $R \to L$, что неверно, т.к. в этой грамматике не выводится выражение $R=\ldots$ и парсер должен был выполнить перенос, а не свёртку.

Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.

Канонические LR(1)-ситуации

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

Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:

$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть — продукция, а вторая — терминал или маркер конца входной строки $\$$. Здесь $a$ называется предпросмотром ситуации, а число $1$ в LR(1) означает его длину. Теперь мы будем выполнять свёртку в соответствии с продукцией $A\rightarrow\alpha$, только в том случае, если находимся в ситуации $[A\rightarrow\alpha\cdot\beta, a]$, и $a$ — входной символ.

Определение:

Назовём LR(1)-ситуацию $[A\rightarrow\alpha\cdot\beta, a]$ допустимой (англ. valid) для активного префикса $\gamma$, если существует правое порождение $S\Rightarrow^{*}\delta A w\Rightarrow\delta\alpha\beta w$, где верно одно из трёх: либо $\gamma=\delta\alpha$, либо $a$ является первым символом $w$, либо$w=\varepsilon$ и $a=\$$.

Построение множеств LR(1)-ситуаций

Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ — замыкание множества ситуаций, и $goto(X,I)$ — функция переходов в автомате по символу $X$.

Лемма:

$$\forall{b} \mid b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in closure(I)$$ Другими словами, при построении замыкания вторая часть добавленных ситуаций должна принадлежать $FIRST(\beta\alpha)$

Доказательство:

[math]\triangleright[/math]

Рассмотрим ситуацию вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве ситуаций, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\varepsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$ Значит, $b\in FIRST(\beta a)$.

[math]\triangleleft[/math]

Псевдокод

Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики $\Gamma' =\langle\Sigma, N, S, P\rangle$:

 item[] closure(item[] [math]I[/math]):
     bool changed
     item[] [math]J = I[/math]
     repeat
         changed = false
         for [math][A\rightarrow\alpha\cdot B\beta, a]\in I[/math]
             for [math](B\rightarrow\gamma)\in \Gamma'.P[/math]
                 for [math]b\in FIRST(\beta\alpha)[/math]
                     [math]J[/math].add([math][B\rightarrow\cdot\gamma,b][/math])
                     changed = true
     until not changed
     return [math]J[/math]

 item[] goto(item[] [math]I[/math], char [math]X[/math]):
     item[] [math]J=\varnothing[/math]
     for [math][A\rightarrow\alpha\cdot X\beta, a]\in I[/math]
         [math]J[/math].add([math][A\rightarrow\alpha X\cdot\beta, a][/math])
     return [math]closure(J)[/math]

 item[][] items([math]\Gamma'[/math]):
     bool changed
     item[][] [math]C[/math]
     [math]C[/math].add([math]closure(\{[S'\rightarrow\cdot S,\$]\})[/math])
     repeat
         changed = false
         for item[] [math]I\subset C[/math]
             for [math]X \in \Gamma'.\Sigma[/math]
                 if [math]goto(I,X)\neq\varnothing[/math] and [math]goto(I,X)\not\subset C[/math]
                     [math]C[/math].add([math]goto(I,X)[/math])
                     changed = true
     until not changed
     return [math]C[/math]

Пример

Рассмотрим следующую грамматику $\Gamma'$:

• $S'\rightarrow S$
• $S\rightarrow CC$
• $C\rightarrow cC\mid d$

Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\$$.

Т.к. в таком случае $FIRST(\beta\alpha) = {\$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\$]$.

Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$. Поскольку ни одна из новых ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех ситуациях терминалы), то функция $closure()$ завершает свою работу.

Начальное множество ситуаций в данном случае равно:

Рис. 1 Множества ситуаций и переходы между ними

• $$I_0: \{[S'\rightarrow \cdot S, \$],[S\rightarrow\cdot CC,\$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$

Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$:

1. При $X=S$:

   $$closure({[S'\rightarrow S\cdot,\$]}) = \varnothing$$

   Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом,

   • $$I_1: \{[S'\rightarrow S\cdot,\$]\}$$

2. При $X=C$:

   $$I_2 = closure(\{[S\rightarrow C\cdot C,\$]\})$$

   • $$I_2 = \{[S\rightarrow C\cdot C,\$],[C\rightarrow\cdot cC,\$],[C\rightarrow\cdot d,\$]\}$$

3. При $X=c$:

   $$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$

   • $$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$

4. При $X=d$:

   $$I_4 = closure(\{[C\rightarrow d\cdot ,c/d]\})$$

   • $$I_4 = \{[C\rightarrow d\cdot,c/d]\}$$

На этом завершается выполнение цикла из процедуры $items$ для $I_0$. $$goto(I_1, *)=\varnothing$$

• $$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\$]\})=\{[S\rightarrow CC\cdot,\$]\}$$

$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\$]\})$$

• $$I_6=\{[C\rightarrow c\cdot C,\$],[C\rightarrow \cdot cC,\$],[C\rightarrow \cdot d,\$]\}$$

NB: Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.

• $$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\$]\}) = \{[C\rightarrow d\cdot ,\$]\}$$

На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$:

• $$I_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$

В множествах $I_4$ и $I_5$ все ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$: $$goto(I_6, c) = I_6$$ $$goto(I_6, d) = I_7$$

• $$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\$]\}$$

Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу.

Канонические LR(1)-таблицы

В алгоритме будут использоваться структуры, описанные в конспекте про про LR(k)-грамматики

Алгоритм

// вход: [math]\Gamma'[/math] — расширенная грамматика
// выход: таблица [math]T[/math] канонического [math]LR(1)[/math]-анализа
function [math]\mathtt{getLR1CanonicalTable}(\Gamma'):[/math]
   [math] C'(\Gamma') \leftarrow \{I_0,I_1..I_n\}[/math] // множество канонических ситуаций для [math]\Gamma'[/math]
   [math]\mathtt{fillArray}(T,[/math] Error[math] ):[/math]
   foreach [math]I_i \in (E(G))\[/math]
       if [math][A\rightarrow \alpha\cdot a\beta, b] \in I_i[/math] and [math]goto(I_i,a) = I_j[/math] // здесь [math]a[/math] — терминал
           [math]T[i,a] = [/math] Shift([math]j[/math])
       if [math][A\rightarrow \alpha\cdot, a] \in I_i[/math] and [math]A\neq S'[/math] 
           [math]T[i,a] = [/math] Reduce([math]A  \to a[/math])
       if [math][S'\rightarrow S\cdot, \$] \in I_i[/math]
           [math]T[i,\$] = [/math] Accept
       if [math]goto(I_i,A) = I_j[/math]
           [math]goto[i,A]\leftarrow j[/math]

Если в процессе построения обнаружатся конфликтующие действия — это значит, что грамматика не принадлежит классу LR(1)

Таблица, построенная в результате применения алгоритм называется канонической таблицей LR(1)-анализа.

Пример

Рассмотрим следующую грамматику $\Gamma$:

1. $S\rightarrow CC$
2. $C\rightarrow cC$
3. $C\rightarrow d$

Приведем каноническую таблицу синтаксического анализа [math]T[/math] для этой грамматики:

	$S$	$C$	$c$	$d$	$\$$
$0$	$1$	$2$	$s(3)$	$s(4)$
$1$					Accept
$2$		$5$	$s(6)$	$s(7)$
$3$		$8$	$s(3)$	$s(4)$
$4$			$r(1)$	$r(3)$
$5$					$r(1)$
$6$		$9$	$s(6)$	$s(7)$
$7$					$r(3)$
$8$			$r(2)$	$r(2)$
$9$					$r(2)$

См. также

• LL(k)-грамматики, множества FIRST и FOLLOW
• LR(k)-грамматики
• LR(0)-разбор
• SLR(1)-разбор
• LALR-разбор

Источники информации

• Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. Издательство Вильямс, 2003. Стр. 331-338.
• Б.К.Мартыненко. Языки и трансляции. Стр. 198-223
• Лекции по теории формальных языков, LR(0)-, SLR(1)-, LR(1)- и LALR(1)-анализ