262
правки
Изменения
→Псевдокод
====Псевдокод====
<wikitex>
Псевдокод построения множеств <tex>$CLOSURE</tex> $ и <tex>$GOTO</tex>$, а также множества пунктов <tex>$items</tex>$:
<code>
Set<Item> CLOSURE(Set<Item> I):
'''return''' C;
</code>
</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$ завершает свою работу и начальное множество пунктов в данном случае равно:
$$I_0: \{[S\rightarrow 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_0$.
</wikitex>
