69
правок
Изменения
Нет описания правки
=== Псевдокод ===
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
<texfont color=green>I_0// Инициализация </texfont> D[0] = <tex>\lbrace [S' \rightarrow \cdot S, 0] \rbrace</tex> # Правило (0) — инициализация useful_loop'''for''' i = 1 '''to''' len(0w) for j = - 1..n for <tex> D[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex> <tex>I_j</tex> ∪= <tex>\{ [A \rightarrow \alpha a_{j} \cdot \beta, i] \}varnothing </tex> # Правило (1) useful_loop(j) function useful_loop(j): do for <texfont color=green>[B \rightarrow \eta \cdot , k] \in I_j// Основная часть </texfont> '''for <tex>[A \rightarrow \alpha \cdot B \beta, ''' i] \in I_{k}</tex>= 0 '''to''' len(w) -1 <tex>I_j</tex> ∪= <tex>\lbrace [A \rightarrow \alpha B \cdot \beta scan(D, i] \rbrace</tex> # Правило (2) for <tex> '''while''' D[B \rightarrow \alpha \cdot A \eta, ki] \in I_j</tex>изменяется for <tex>\beta : complete(A \rightarrow \betaD, i) \in P</tex> <tex>I_j</tex> ∪= <tex>\lbrace [A \rightarrow \cdot \beta predict(D, j] \rbrace</tex> # Правило (3i) while на данной итерации какое-то множество изменилось
==Корректность алгоритма==
{{Теорема
