LR(1)-разбор

Материал из Викиконспекты
Версия от 13:47, 24 июня 2015; 188.227.78.184 (обсуждение) (Канонические LR(1)-состояния)
Перейти к: навигация, поиск

Отличия от 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> Основная идея заключается в том, чтобы хранить в состояниях больше информации, чтобы не производить некорректных свёрток. Добавим в состояния второй компонент: терминальный символ. Таким образом, состояния будут выглядеть следующим образом: $[A\rightarrow\alpha\cdot\beta, a]$, где первая часть - продукция, а вторая - терминал или маркер конца входной строки $\char36$. Здесь </wikitex>