LR(1)-разбор — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Отличия от SLR-разбора)
Строка 1: Строка 1:
 +
<wikitex>
 +
В некоторых случаях SLR-разбор может дать неправильный результат разбора. В таких случаях используют более сложные методы, такие как $LR(1)$ и $LALR$ - разбор. Рассмотрим первый из них.
 
==Отличия от SLR-разбора==
 
==Отличия от SLR-разбора==
<wikitex>
+
Основным отличием $LR(1)$ - разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов.
Основным отличием LR(1)-разбора от SLR-разбора является использование предпросмотра(англ. lookahead) символов.
 
  
 
Приведём пример, ситуации, в которой SLR-разбор не справится с задачей:
 
Приведём пример, ситуации, в которой SLR-разбор не справится с задачей:
Строка 61: Строка 62:
  
 
Чтобы решить эту проблему, необходимо хранить в пункте больший объём информации, который позволит не делать таких ошибочных свёрток
 
Чтобы решить эту проблему, необходимо хранить в пункте больший объём информации, который позволит не делать таких ошибочных свёрток
</wikitex>
+
 
  
 
==Канонические LR(1)-пункты==
 
==Канонические LR(1)-пункты==
<wikitex>
 
 
Основная идея заключается в том, чтобы хранить в пунктах больше информации, чтобы не производить некорректных свёрток.  
 
Основная идея заключается в том, чтобы хранить в пунктах больше информации, чтобы не производить некорректных свёрток.  
Добавим в пункт второй компонент: терминальный символ. Таким образом, $LR(1)$-пункты будут выглядеть следующим образом:  
+
Добавим в пункт второй компонент: терминальный символ. Таким образом, $LR(1)$ -пункты будут выглядеть следующим образом:  
  
 
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть - продукция, а вторая - терминал или маркер конца входной строки $\char36$. Здесь $a$ называется предпросмотром (англ. ''lookahead'') пункта, а цифра $1$ в $LR(1)$ означает его длину.
 
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть - продукция, а вторая - терминал или маркер конца входной строки $\char36$. Здесь $a$ называется предпросмотром (англ. ''lookahead'') пункта, а цифра $1$ в $LR(1)$ означает его длину.
Строка 78: Строка 78:
 
* $w=\epsilon$ и $a=\char36$
 
* $w=\epsilon$ и $a=\char36$
 
}}
 
}}
 +
===Построение множеств LR(1)-пунктов===
 
</wikitex>
 
</wikitex>
===Построение множеств LR(1)-пунктов===
 

Версия 14:30, 24 июня 2015

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

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

Основным отличием $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=...$ и парсер должен был выполнить перенос, а не свёртку.

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


Канонические 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$, где верно одно из трёх:
  • $\gamma=\delta\alpha$
  • $a$ является первым символом $w$
  • $w=\epsilon$ и $a=\char36$

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

</wikitex>