LR(1)-разбор

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

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

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

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

Рассмотрим грамматику вида: $ S \to L=R | R \\ L \to *R | 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=...$ и парсер должен был выполнить перенос, а не свёртку.

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

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

<wikitex> Основная идея заключается в том, чтобы хранить в пунктах больше информации, чтобы не производить некорректных свёрток. Добавим в пункт второй компонент: терминальный символ. Таким образом, $LR(1)$ -пункты будут выглядеть следующим образом:

$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть - продукция, а вторая - терминал или маркер конца входной строки $\char36$. Здесь $a$ называется предпросмотром (англ. lookahead) пункта, а цифра $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=\epsilon$ и $a=\char36$

</wikitex>

Построение множеств LR(1)-пунктов

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

Лемма:

$$\forall{b}

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

[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$ порождает $\epsilon$ слева: $\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$:

 function constructFOLLOW():
     for [math]( A  \in N )[/math]
         [math]\mathrm{FOLLOW}[A] =  \varnothing [/math]
     [math]\mathrm{FOLLOW}[S] =  \{\$\} [/math]   // в стартовый терминал помещается символ конца строки 
     changed = true
     while changed
         changed = false
         for [math]( A \to \alpha \in P )[/math]
             for [math]( B : \alpha = \beta B \gamma)[/math]
                 [math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FIRST}(\gamma) \setminus \{\varepsilon\} [/math]
                 if [math] \varepsilon \in \mathrm{FIRST}(\gamma) [/math]
                     [math] \mathrm{FOLLOW}[B]\ \cup =\ \mathrm{FOLLOW}[A][/math]
                 changed = true if [math] \mathrm{FOLLOW}[B] [/math] изменился

</wikitex>