390
правок
Изменения
→Алгоритм Эрли
Алгоритм основывается на следующих трёх правилах:
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
# Если <tex>[B \rightarrow \eta \ \cdot, i] \in D_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, k] \in D_j</tex>.# Если <tex>[A \rightarrow \alpha \ \cdot B \beta, i] \in D_{j} </tex> и <tex>(B \rightarrow \eta) \in P </tex>, то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}</tex>.
=== Псевдокод ===
'''function''' <tex>\mathtt{earley}(G, w)</tex>:
<font color=green>// Инициализация </font>
<tex> D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0] \rbrace </tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>len(w) - 1</tex>
<tex>D_i</tex> = <tex>\varnothing </tex>
<tex>\mathtt{predict}(D, j, G, w)</tex>
<font color=green>// Результат </font>
'''if''' <tex>[S' \rightarrow S \ \cdot, 0] \in D_{len(w)} </tex>
'''return''' ''true''
'''else'''
<font color=green>// Второе правило </font>
'''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
'''for''' <tex>[B \rightarrow \eta \ \cdot, i] \in D_{j} </tex>
'''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i} </tex>
<tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>
'''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex>
'''for''' <tex>(B \rightarrow \eta) \in P </tex>
<tex>D_{j}</tex> <tex>\cup</tex>= <tex>[B \rightarrow \cdot \ \eta, j]</tex>
==Корректность алгоритма==
