Изменения

Перейти к: навигация, поиск

LR(1)-разбор

97 байт убрано, 22:12, 4 декабря 2021
м
Замена \char36 на \$
<wikitex>
В некоторых случаях [[SLR(1)-разбор|SLR-разбор]] может выдать неправильный результат. В таких случаях используют более сложные методы, такие как LR(1) и [[LALR-разбор]]. Рассмотрим первый из них.
</wikitex>
== Отличия от SLR-разбора ==
<wikitex>
Основным отличием LR(1)-разбора от SLR-разбора является использование '''предпросмотра''' (англ. ''lookahead'') символов.
Чтобы решить эту проблему, необходимо хранить в ситуации больший объём информации, который позволит не делать таких ошибочных свёрток.
</wikitex>
== Канонические LR(1)-ситуации ==
<wikitex>
Основная идея заключается в том, чтобы хранить в ситуациях (англ. ''items'') больше информации, чтобы не производить некорректных свёрток.
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\char36$$. Здесь $a$ называется '''предпросмотром''' ситуации, а число $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=\varepsilon$ и $a=\char36$$.
}}
</wikitex>
=== Построение множеств LR(1)-ситуаций ===
<wikitex>
Метод построения похож на метод для $LR(0)$-разбора, с двумя изменёнными функциями: $closure(I)$ {{---}} замыкание множества ситуаций, и $goto(X,I)$ {{---}} функция переходов в автомате по символу $X$.
{{Лемма
Значит, $b\in FIRST(\beta a)$.
}}
</wikitex>
====Псевдокод====
<wikitex>
Псевдокод построения множеств $closure$ и $goto$, а также множества наборов ситуаций $items$ для грамматики
$\Gamma' =\langle\Sigma, N, S, P\rangle$:
<code> '''item'''[] closure('''item'''[] $<tex>I$</tex>):
'''bool''' changed
'''item'''[] $<tex>J$ = $I$ </tex>
'''repeat'''
changed = ''false''
'''for''' $<tex>[A\rightarrow\alpha\cdot B\beta, a]\in I$</tex> '''for''' $<tex>(B\rightarrow\gamma)\in \Gamma'.P$</tex> '''for''' $<tex>b\in FIRST(\beta\alpha)$</tex> $<tex>J$</tex>.add($<tex>[B\rightarrow\cdot\gamma,b]$</tex>)
changed = ''true''
'''until not''' changed
'''return''' $<tex>J$</codetex><code> '''item'''[] goto('''item'''[] $<tex>I$</tex>, '''char''' $<tex>X$</tex>): '''item'''[] $<tex>J=\varnothing$</tex> '''for''' $<tex>[A\rightarrow\alpha\cdot X\beta, a]\in I$</tex> $<tex>J$</tex>.add($<tex>[A\rightarrow\alpha X\cdot\beta, a]$</tex>) '''return''' $<tex>closure(J)$</codetex><code> '''item'''[][] items($<tex>\Gamma'$</tex>):
'''bool''' changed
'''item'''[][] $<tex>C$</tex> $<tex>C$</tex>.add($<tex>closure(\{[S'\rightarrow\cdot S,\char36$]\})\$</tex>)
'''repeat'''
changed = ''false''
'''for''' '''item'''[] $<tex>I\subset C$</tex> '''for''' $<tex>X \in \Gamma'.\Sigma$</tex> '''if''' $<tex>goto(I,X)\neq\varnothing$ </tex> '''and''' $<tex>goto(I,X)\not\subset C$</tex> $<tex>C$</tex>.add($<tex>goto(I,X)$</tex>)
changed = ''true''
'''until not''' changed
'''return''' $C$</codetex>C</wikitextex>
====Пример====
<wikitex>
Рассмотрим следующую грамматику $\Gamma'$:
* $S'\rightarrow S$
* $S\rightarrow CC$
* $C\rightarrow cC\mid d$
Запустим процедуру $items(\Gamma')$. Она начинается с вычисления $closure([S\rightarrow S', \char36$])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\varepsilon;B=S;\beta=\varepsilon;a=\char36$$.
Т.к. в таком случае $FIRST(\beta\alpha) = {\char36$}$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36$]$.
Продолжив вычислять замыкание таким образом, мы добавим во множество ситуаций $[C\rightarrow\cdot C, c]$, $[C\rightarrow\cdot C, d]$, $C\rightarrow\cdot d, c]$ и $[C\rightarrow\cdot d, d]$.
[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества ситуаций и переходы между ними]]
*$$I_0: \{[S'\rightarrow \cdot S, \char36$],[S\rightarrow\cdot CC,\char36$],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}$$
Следующим шагом процедуры $items()$ будет вычисление функции переходов автомата $goto(I_0,X)$ для всех символов $X$ грамматики $\Gamma'$:
#При $X=S$:
#:$$closure({[S'\rightarrow S\cdot,\char36$]}) = \varnothing$$
#:Мы не добавили ни одной ситуации, т.к. точка является крайней справа. Таким образом,
#:*$$I_1: \{[S'\rightarrow S\cdot,\char36$]\}$$
#При $X=C$:
#:$$I_2 = closure(\{[S\rightarrow C\cdot C,\char36$]\})$$#:*$$I_2 = \{[S\rightarrow C\cdot C,\char36$],[C\rightarrow\cdot cC,\char36$],[C\rightarrow\cdot d,\char36$]\}$$
#При $X=c$:
#:$$I_3 = closure(\{[C\rightarrow c\cdot C,c/d]\})$$
На этом завершается выполнение цикла из процедуры $items$ для $I_0$.
$$goto(I_1, *)=\varnothing$$
*$$I_5=goto(I_2, C) = closure(\{[S\rightarrow CC\cdot,\char36$]\})=\{[S\rightarrow CC\cdot,\char36$]\}$$:$$I_6=goto(I_2, c) = closure(\{[C\rightarrow c\cdot C,\char36$]\})$$*$$I_6=\{[C\rightarrow c\cdot C,\char36$],[C\rightarrow \cdot cC,\char36$],[C\rightarrow \cdot d,\char36$]\}$$
'''NB:''' Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями ситуаций. Такое явление является частым в LR(1)-анализе, из-за него результирующая таблица будет неоправданно большой. LALR-анализ борется с этим явлением.
*$$I_7 = goto(I_2, d) = closure(\{[C\rightarrow d\cdot ,\char36$]\}) = \{[C\rightarrow d\cdot ,\char36$]\}$$
На этом рассмотрение $goto(I_2)$ завершено, переходим к $goto(I_3)$:
*$$I_8 = goto(I_3, C) = closure(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$
$$goto(I_6, c) = I_6$$
$$goto(I_6, d) = I_7$$
*$$I_9 = goto(I_6, C) = \{[C\rightarrow cC\cdot,\char36$]\}$$
Остальные множества ситуаций не дают нам значений $goto$, процедура $items()$ завершает работу.
</wikitex>
=== Канонические LR(1)-таблицы ===
'''if''' <tex>[A\rightarrow \alpha\cdot, a] \in I_i</tex> '''and''' <tex>A\neq S'</tex>
<tex>T[i,a] = </tex> '''Reduce'''(<tex>A \to a</tex>)
'''if''' <tex>[S'\rightarrow S\cdot, \char36$] \in I_i</tex> <tex>T[i,\char36$] = </tex> '''Accept'''
'''if''' <tex>goto(I_i,A) = I_j</tex>
<tex>goto[i,A]\leftarrow j</tex>
==== Пример ====
<wikitex>
Рассмотрим следующую грамматику $\Gamma$:
# $S\rightarrow CC$
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$c$
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$d$
!style="background-color:#EEE;padding:2px 20px;text-align:center"|$\char36$$
|-
|style="background-color:#EEE;padding:2px 20px;text-align:center"|$0$
|}
<br clear="left">
</wikitex>
== См. также ==
3
правки

Навигация