69
правок
Изменения
Нет описания правки
|definition =
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 ... w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>. , где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
}}
{{Определение
|definition =
Ситуации хранятся в множествах <tex>D_0,...,D_{n-1}</tex>, называемых спиками '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что <tex>\exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})</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>
<font color=green>// Вычисление ситуаций </font>
'''for''' <tex>j = 0 </tex> '''to''' <tex>len(w) - 1</tex>
<tex>\mathtt{scan}(D, j, G, w)</tex>
'''while''' <tex>D_j</tex> изменяется
<font color=green>// Результат </font>
'''if''' <tex>[S' \rightarrow S \cdot, 0] \in D_{len(w)} </tex>
'''return''' ''Truetrue''
'''else'''
'''return''' ''Falsefalse''
<font color=green>// Первое правило </font>
=====<tex>\Longrightarrow</tex>=====
Докажем индукцией по исполнению алгоритма.<br/>
<u> ''База {{---}} индукции:'' </u><br/><tex>[S' \rightarrow \cdot S, 0] \in D_0</tex>. Осталось разобраться<br/><u> ''Индукционный переход:'' </u> <br/>Пусть предположение верно для всех списков ситуаций с номерами меньше <tex> j </tex>. Разберемся, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
1. Включаем по правилу <tex> \mathtt{scan}</tex>.<br/>
2. <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha ' \Rightarrow^* w_i...w_{i'-1} \wedge B ' \Rightarrow^* w_{i'}...w_{j-1}</tex>.<br/>
Тогда имеем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>. Также можно записать <tex>S' \Rightarrow^* w_0...w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0...w_{i-1} w_i...w_{i'-1}B \beta \delta</tex>,
а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'}...w_{j-1}</tex>.<br/>
Применяя индукцию по второму параметру получим <tex>[B \rightarrow \eta \cdot, i'] \in D_j</tex>, откуда по правилу <tex> \mathtt{complete}</tex> получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}</tex>.
==Пример==
Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
* <tex>S \rightarrow T + S</tex>;* <tex>S \rightarrow T </tex>;* <tex>T \rightarrow F * T</tex>;* <tex>T \rightarrow F</tex>;* <tex>F \rightarrow ( S )</tex>;* <tex>F \rightarrow a</tex>.
{|
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>w \in L(G) </tex>.<br>
==См. также==
* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
==Источники информации==
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
