Изменения

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

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

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

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

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

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

Назовём 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=\char36$.

}}

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

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

{{Лемма

Значит, $b\in FIRST(\beta a)$.

}}

====Псевдокод====

Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики

====Пример====

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

* $S'\rightarrow S$

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

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

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

==== Пример ====

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

# $S\rightarrow CC$

|}

<br clear="left">

== См. также ==