3
правки
Изменения
м
Замена \char36 на \$
Добавим в ситуацию второй компонент: терминальный символ. Таким образом, 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$$.
}}
=== Построение множеств LR(1)-ситуаций ===
* $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()$ завершает работу.
'''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>
!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$
