Изменения

Перейти к: навигация, поиск

Участник:Shovkoplyas Grigory

259 байт добавлено, 20:31, 16 января 2016
Нет описания правки
Алгоритм основывается на следующих трёх правилах:
# Если <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 , ki] \in I_jD_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, ik] \in I_{k}D_i</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, ik] \in I_jD_j</tex>.# Если <tex>[B A \rightarrow \alpha \cdot A B \etabeta, ki] \in I_jD_{j} </tex> и <tex>(A B \rightarrow \betaeta) \in P</tex>, то <tex>[A B \rightarrow \cdot \betaeta, j] \in I_jD_{j}</tex>.
=== Псевдокод ===
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
'''function''' <tex>\mathtt{earley}(G, w)</tex>: <font color=green> // Инициализация </font> D[0] = { <tex>D_{0} = \lbrace [S' \rightarrow \cdot S, 0]\rbrace </tex>} '''for''' i = 1 '''to''' len(w) - 1 D[i] = <tex>\varnothing </tex> <font color=green> // Основная часть </font> '''for''' j = 0 '''to''' len(w) - 1 <tex>\mathtt{scan}(D, j, G, w)</tex> '''while''' D[j] <tex>D_j</tex> изменяется <tex>\mathtt{complete}(D, j, G, w)</tex> <tex>\mathtt{predict}(D, j, G, w)</tex>
<font color=green> // Первое правило </font> '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>:
'''if''' j = 0
'''return'''
'''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i]</tex> <tex>\inD_{j - 1} </tex> D[j - 1] '''if''' a = w[= <tex>w_{j - 1]}</tex> D[<tex>D_{j] }</tex> <tex>\cup</tex>= {<tex>[A \rightarrow \alpha \cdot a \beta, i]</tex>} <font color=green> // Второе правило </font> '''function''' predict(D, j) '''for''' <tex>[A \rightarrow \alpha \cdot B \betamathtt{complete}(D, i]</tex> <tex>\in</tex> D[j] '''for''' <tex>[B \rightarrow \eta]</tex> <tex>\in</tex> P D[j] <tex>\cup</tex>= {<tex>[B \rightarrow \cdot \eta, j]G, w)</tex>} <font color=green> // Третье правило </font> '''function''' complete(D, j): '''for''' <tex>[B \rightarrow \eta \cdot, i]</tex> <tex>\inD_{j} </tex> D[j] '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k]\in D_{i} </tex> <tex>\inD_{j}</tex> D[i] D[j] <tex>\cup</tex>= {<tex>[A \rightarrow \alpha B \cdot \beta, k]</tex>}
<font color=green>// Третье правило </font>
'''function''' <tex>\mathtt{predict}(D, j, G, w)</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>
==Корректность алгоритма==
{{Теорема
69
правок

Навигация