Изменения

Рассмотрим следующую грамматику $G'$:* # $S'\rightarrow SCC$* # $SC\rightarrow CCcC$* # $SC\rightarrow cC|d$Запустим процедуру $items(G')$. Она начинается с вычисления $CLOSURE([S\rightarrow S', \char36])$. Это правило вида $[A\rightarrow\alpha\cdot B\beta, a]$, где $AПриведем каноническую таблицу синтаксического анализа для этой грамматики:{| cellspacing="0" cellpadding=S';\alpha"10" align=\epsilon;B"center" border=S;\beta"1"! rowspan=\epsilon;a"2" | Состояние! colspan=\char36"3" | $. Т.к. в таком случае ACTION$FIRST(\beta\alpha) ! colspan= {\char36}"2" |$, то мы добавим только правило $[S\rightarrow\cdot CC,\char36]GOTO$.|-Продолжив вычислять замыкание таким образом, мы добавим во множество пунктов |$[C\rightarrow\cdot C, c]$, |$C\rightarrow\cdot C, d]$, |$C\rightarrow\cdot d, c]char36$, и |$C\rightarrow\cdot d, d]S$. Т.к. ни один из новых пунктов не имеет вид |$[A\rightarrow\alpha\cdot B\beta, a]C$ (справа от точки во всех пунктах терминалы), то функция $CLOSURE$ завершает свою работу и начальное множество пунктов в данном случае равно:|-[[Файл:lr1_sets.png|400px|thumb|Рис. 1 Множества пунктов и их переходы]]$0$I_0: \{[S'\rightarrow \cdot S, \char36],[S\rightarrow\cdot CC,\char36],[C\rightarrow\cdot C, c/d],[C\rightarrow\cdot d, c/d]\}|$s3$Следующим шагом процедуры |$itemss4$ будет вычисление функции переходов автомата ||$GOTO(I_0,X)1$ для всех символов |$X2$ грамматики |-|$G'1$:||При $X| style=S$"font-style:italic;color:green;" | ok$$CLOSURE({[S'\rightarrow S\cdot,\char36]}) = \varnothing$$||Мы не добавили ни одного пункта, т.к. точка является крайней справа. Таким образом, |-|$2$I_1: \{[S'\rightarrow S\cdot,\char36]\}|$s6$При |$X=Cs7$:|||$5$I_2 = CLOSURE(\{[S\rightarrow C\cdot C,\char36]\})|-|$3$|$s3$I_2 = \{[S\rightarrow C\cdot C,\char36],[C\rightarrow\cdot cC,\char36],[C\rightarrow\cdot d,\char36]\}|$s4$При |||$X=c8$:|-|$4$I_3 = CLOSURE(\{[C\rightarrow c\cdot C,c/d]\})|$r1$|$r3$I_3 = \{[C\rightarrow c\cdot C,c/d],[C\rightarrow\cdot cC,c/d],[C\rightarrow\cdot d,c/d]\}||||-|$5$При |||$X=dr1$:$$I_4 = CLOSURE(\{[C\rightarrow d\cdot ,c/d]\})$$||-|$$I_4 = \{[C\rightarrow d\cdot,c/d]\}$6$На этом завершается выполнение цикла из процедуры |$itemss6$ для $I_0$. |$$GOTO(I_1, *)=\varnothing$s7$$$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]\}$9$Обратим внимание, что $I_6$ отличается от $I_3$ только правыми частями пунктов. Такое явление является частым в $LR(1)$|-анализе, из-за него результирующая таблица будет неоправданно большой. |$LALR7$-анализ борется с этим явлением.Продолжим:|||$r3$I_7 = GOTO(I_2, d) = CLOSURE(\{[C\rightarrow d\cdot ,\char36]\}) = \{[C\rightarrow d\cdot ,\char36]\}|||-|$8$На этом рассмотрение |$GOTO(I_2)r2$ завершено, переходим к |$GOTO(I_3)r2$:||||-|$9$I_8 = GOTO(I_3, C) = CLOSURE(\{[C\rightarrow cC\cdot ,c/d]\}) = \{[C\rightarrow cC\cdot ,c/d]\}$$В множествах |||$I_4$ и $I_5$ все пункты имеют точки в крайнем положении справа, следовательно эти множества не имеют $GOTOr2$ $$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$ завершает работу.