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