Изменения

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

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

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

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

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

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

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

Основная идея заключается в том, чтобы хранить в пунктах ситуациях больше информации, чтобы не производить некорректных свёрток. Добавим в пункт второй компонент: терминальный символ. Таким образом, $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$, где верно одно из трёх:

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