LR(1)-разбор — различия между версиями
(→Канонические LR(1)-состояния) |
Xottab (обсуждение | вклад) (→Канонические LR(1)-состояния) |
||
| Строка 62: | Строка 62: | ||
Чтобы решить эту проблему, необходимо хранить в состоянии больший объём информации, который позволит не делать таких ошибочных свёрток | Чтобы решить эту проблему, необходимо хранить в состоянии больший объём информации, который позволит не делать таких ошибочных свёрток | ||
</wikitex> | </wikitex> | ||
| − | ==Канонические LR(1)- | + | ==Канонические LR(1)-пункты== |
<wikitex> | <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$ - входной символ. | ||
| + | {{Определение | ||
| + | |id=defValid | ||
| + | |definition= | ||
| + | Назовём $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> | </wikitex> | ||
| + | ===Построение множеств LR(1)-пунктов=== | ||
Версия 14:23, 24 июня 2015
Отличия от 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$, где верно одно из трёх:
|
</wikitex>
