Бюрократы, editor, Администраторы
422
правки
Изменения
→Алгоритм Эрли
== Алгоритм Эрли ==
Чтобы воспользоваться леммой, необходимо найти <tex>I_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>I_kI_j</tex> используются <tex>I_0 \ldots I_{kj}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).<br/>
Алгоритм основывается на следующих трёх правилах:
# Если <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex> (где <tex>a_j</tex> — <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i] \in I_j</tex>.
# Если <tex>[B \rightarrow \eta \cdot , k] \in I_j</tex> и <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_{k}</tex>, то <tex>[A \rightarrow \alpha B \cdot \beta, i] \in I_j</tex>.
# Если <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex> и <tex>(A \rightarrow \beta) \in P</tex>, то <tex>[A \rightarrow \cdot \beta, j] \in I_j</tex>.
=== Псевдокод ===
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
for j = 1..n
for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>
<tex>I_j</tex> ∪= <tex>\lbrace [A \rightarrow \alpha a_{j} \cdot \beta, i] \rbrace</tex> # Правило (1)
useful_loop(j)
