262
правки
Изменения
Нет описания правки
<wikitex>
Основная идея заключается в том, чтобы хранить в ситуациях больше информации, чтобы не производить некорректных свёрток.
Добавим в пункт ситуацию второй компонент: терминальный символ. Таким образом, LR(1)-ситуации будут выглядеть следующим образом:
$[A\rightarrow\alpha\cdot\beta, a]$, где первая часть {{---}} продукция, а вторая {{---}} терминал или маркер конца входной строки $\char36$. Здесь $a$ называется '''предпросмотром''' (англ. ''lookahead'') ситуации, а число 1 в LR(1) означает его длину.
|id=lemmaclosure
|statement= $$\forall{b} \mid b\in FIRST(\beta\alpha): [A\rightarrow\alpha\cdot B\beta, a]\in I\Rightarrow [B\rightarrow\cdot\gamma, b]\in closure(I)$$
Другими словами, при построении замыкания вторая часть добавленных пунктов ситуаций должна принадлежать $FIRST(\beta\alpha)$|proof= Рассмотрим пункт ситуацию вида $[A\rightarrow\alpha\cdot B\beta, a]$ в множестве пунктовситуаций, допустимых для некоторого активного префикса $\gamma$. Тогда существует правое порождение $S\Rightarrow^{*}\delta Aax\Rightarrow\delta\alpha B\beta ax$, где $\gamma=\delta\alpha$. Предположим, что $\beta ax$ порождает строку терминалов $by$. Тогда для каждой продукции вида $\forall{B\rightarrow\eta}\exists{\eta}$ мы имеем порождение $ S\Rightarrow^{*}\delta Bby\Rightarrow\delta\eta by$. Таким образом, $[B\rightarrow\cdot\eta,b]$ является допустимым для $\gamma$. Заметим, что $b$ может быть первым терминалом, порожденным из $\beta$, либо, возможно что $\beta$ порождает $\epsilon$ слева: $\beta ax\Rightarrow^{*}by$, следовательно $b=a$. Таким образом, $b\in FIRST(\beta ax)$. Поскольку $x$ не может содержать первый терминал из $by$, то $FIRST(\beta ax)=FIRST(\beta a)$
Значит, $b\in FIRST(\beta a)$.
}}
====Псевдокод====
<wikitex>
Псевдокод построения множеств $closure$ и $goto$, а также множества пунктов ситуаций $items$:
<code>
Set<Item> closure(Set<Item> I):
Запустим процедуру $items(G')$. Она начинается с вычисления $closure([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $A=S';\alpha=\epsilon;B=S;\beta=\epsilon;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]$. Т.к. ни один одна из новых пунктов ситуаций не имеет вид $[A\rightarrow\alpha\cdot B\beta, a]$ (справа от точки во всех пунктах ситуациях терминалы), то функция $closure$ завершает свою работу и начальное множество пунктов ситуаций в данном случае равно:
[[Файл: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$ грамматики $G'$:
При $X=S$:
$$closure({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$
Мы не добавили ни одного пунктаодной ситуации, т.к. точка является крайней справа. Таким образом,
$$I_1: \{[S'\rightarrow S\cdot,\char36]\}$$
При $X=C$:
$$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]\}$$
Обратим внимание, что $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]\}$$
В множествах $I_4$ и $I_5$ все пункты ситуации имеют точки в крайнем положении справа, следовательно эти множества не имеют $goto$
$$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)-таблицы ===
<font color=green>// выход: таблица канонического <tex>LR</tex>-анализа с функциями <tex>ACTION</tex> и <tex>goto</tex></font>
'''function''' <tex>\mathtt{getLR1LexTable}(G'):</tex>
<tex> C'(G') \leftarrow \{I_0,I_1..I_n\}</tex> <font color=green>// множество канонических пунктов ситуаций для <tex>G'</tex></font>
<tex>\mathtt{fillArray}(ACTION,</tex>"ошибка"<tex> ):</tex>
'''foreach''' <tex>I_i \in (E(G))\</tex>
