Изменения
→Канонические LR(1)-пункты
</wikitex>
====Пример====
<wikitex>
Рассмотрим следующую грамматику $G'$:
* $S'\rightarrow S$
* $S\rightarrow CC$
* $S\rightarrow cC|d$
Запустим процедуру $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_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]\})$$
$$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}$$
При $X=d$:
$$I_4 = CLOSURE(\{[C\rightarrow d\cdot ,c/d]\})$$
$$I_4 = \{[C\rightarrow d\cdot,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]\}$$
Обратим внимание, что $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)-таблицы ===
<wikitex>
Рассмотрим следующую грамматику $G'$:
