1632
правки
Изменения
м
useful_looprulesLoop(0)
useful_looprulesLoop(j)
rollbackEdits.php mass rollback
==Алгоритм==
Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. Главным отличием от базовой версии алгоритма является функция <tex>\mathtt{rulesLoop}</tex>, внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении <tex>D_j</tex> мы просматривали весь список <tex>D_j</tex> и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри <tex>\mathtt{rulesLoop}</tex>, просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathtt{while}</tex>.
Будем рассматривать грамматику [[Удаление eps-правил из грамматики|без ε-правил]] и [[Удаление бесполезных символов из грамматики|бесполезных символов]].
'''function''' <tex>\mathtt{earley_modearleyMod}(G, w)</tex>:
<font color=green>// Инициализация </font>
<tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex>
'''for''' j = 1 .. n
'''for''' <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in D_{j-1}</tex>
<tex>D_j</tex> <tex> \cup</tex> = <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> <font color=green>// Первое правило </font>
'''function''' useful_loop<tex>\mathtt{rulesLoop(j)}</tex>:
<tex>D_j'' = D_j</tex>
'''while''' <tex>D_j'' \ne \varnothing</tex>
== Доказательство эквивалентности ==
В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex>, просматривается не весь список <tex>D_j</tex>, а только те ситуации, которые были добавлены на предыдущей итерации цикла <codetex>\mathrm{while}</codetex>. Данная модификация является корректной.
# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S', \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S'</tex> не встречается в правых частях правил.
# Теперь рассмотрим цикл <tex>(**)</tex>. Так как для каждой ситуации <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex> в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex>.
|about=1
|statement=
<tex>\forall\,j: 1 \le leqslant j \le leqslant n</tex> в списке <tex>D_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше некоторой константы. Таким образом, поскольку в <tex>D_j</tex> находятся ситуации, у которых <tex>0 \le leqslant i \le leqslant j</tex>, всего в <tex>D_j</tex> будет <tex>O(j)</tex> ситуаций.
}}
== Источники информации==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.Издательство "Мир", Москва, 1978г., стр. 364-366
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Алгоритмы разбора]]
