69
правок
Изменения
Нет описания правки
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
<font color=green> // Инициализация </font>
D[0] = {<tex>[S' <tex>\rightarrow</tex> <tex>\cdotS, 0]</tex>S, 0]}
'''for''' i = 1 '''to''' len(w) - 1
D[i] = <tex>\varnothing </tex>
'''if''' j = 0
'''return'''
'''for''' [A <tex>[A \rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>a<tex>\beta, i]</tex>, i] <tex>\in</tex> D[j - 1]
'''if''' a = w[j - 1]
D[j] ∪= {[A <tex>\rightarrowcup</tex> = {<tex>[A \rightarrow \alpha</tex>a<tex>\cdot</tex><tex>a \beta, i]</tex>, i]}
<font color=green> // Второе правило </font>
'''function''' predict(D, j)
'''for''' [A <tex>[A \rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>B<tex>\beta, i]</tex>, i] <tex>\in</tex> D[j] '''for''' [B <tex>[B \rightarrow\eta]</tex> η] <tex>\in</tex> P D[j] ∪= {[B <tex>\rightarrowcup</tex> = {<tex>[B \rightarrow \cdoteta]</tex>η]}
<font color=green> // Третье правило </font>
'''function''' complete(D, j)
'''for''' [B <tex>[B \rightarrow</tex> &\eta;<tex>\cdot, i]</tex>, i] <tex>\in</tex> D[j] '''for''' [A <tex>[A \rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>B<tex>\beta, k]</tex>, k] <tex>\in</tex> D[i] D[j] ∪= {[A <tex>\rightarrowcup</tex> = {<tex>[A \rightarrow \alpha</tex><tex>\cdot</tex>B<tex>\beta, k]</tex>, k]}
==Корректность алгоритма==
