262
правки
Изменения
→Построение множеств LR(1)-пунктов
Set<Set<Item>> items($G'$):
'''bool''' changed;
Set<Set<Item>> $C$ = $\{CLOSURE({S'\rightarrow\cdot S,\char36})\}$;
'''repeat'''
changed = '''false''';
'''for''' Set<Item> $I\subset C$
'''for''' $X \in terminalssymbols(G')$<font color="green">//по всем символам грамматики</font>
'''if''' $GOTO(I,X)\neq\varnothing$ and $GOTO(I,X)\not\subset C$
C.add($GOTO(I,X)$);
Запустим процедуру $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$ завершает свою работу и начальное множество пунктов в данном случае равно:$$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)$ для всех терминалов символов $I_0X$ грамматики $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]\}$$
</wikitex>
