Изменения

Пусть <tex>G = (\langle N, \Sigma, P, S)\rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно -свободная ]] грамматика и <tex>w = w_0 w_1 \omega = a_1 a_2 ... a_nldots w_{n-1}</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \alpha \cdot X_{k+1} ... X_m\beta, i]</tex> назовем <b>ситуацией</b>, относящейся к цепочке <tex>\omega</tex>, если где <tex>A \rightarrow X_1 ... X_m \alpha \beta </tex> {{---}} — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. — позиция в <tex>\cdotw</tex> является метасимволом, не принадлежащим ни называется '''ситуацией''', относящейся к цепочке <tex>Nw</tex>, ни где '''<tex>\Sigmacdot </tex>. ''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex>k \in cdot \mathbb{N}, 0 notin \leqslant k Sigma \leqslant mcup N</tex>).

Для каждого Ситуации хранятся в множествах <tex>0 D_0, \leqslant j \leqslant ldots ,D_{n-1}</tex> построим <b>список , называемых '''списками ситуаций</b> <tex>I_j</tex> такой, что '''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i] \in I_j</tex> для в <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых -м списке ситуаций <tex>\gammaD_j</tex> и равносильно тому, что <tex>\exists \delta</tex> существуют выводы <tex>\in \Sigma \cup N : ((S ' \Rightarrow^* w_0 \gamma ldots w_{i-1} A \delta, ) \gamma wedge A \Rightarrow^* a_1...a_i</tex> и <tex>\alpha w_i \Rightarrow^* a_ldots w_{i+j-1} ... a_j)</tex>.

Последовательность списков ситуаций <tex>I_0D_0, I_1D_1, ...\ldots, I_nD_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.}} == Алгоритм Эрли ==Чтобы воспользоваться леммой, необходимо найти <tex>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>D_j</tex> используются <tex>D_0, \ldots, D_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент). Алгоритм основывается на следующих трёх правилах:# Если <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>. === Псевдокод ===Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \omegarightarrow S)</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)</tex> <tex>D_i</tex> = <tex>\varnothing </tex> <font color=green>// Вычисление ситуаций </font> '''for''' <tex>j = 0</tex> '''to''' <tex>len(w)</tex> <tex>\mathtt{scan}(D, j, G, w)</tex> '''while''' <tex>D_j</tex> изменяется <tex>\mathtt{complete}(D, j, G, w)</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''' '''return''' ''false''    '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>: '''if''' <tex>j</tex> == <tex>0</tex> '''return''' '''for''' <tex>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex> '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex> <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha a \cdot \beta, i]</tex>  '''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, j] \in D_{i} </tex> <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, j]</tex>  '''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> ==Корректность алгоритма=={{Теорема|statement = Приведенный алгоритм правильно строит все списки ситуаций. То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in D_{j} \Longleftrightarrow \exists \delta \in \Sigma \cup N : ((S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta) \wedge A \Rightarrow^* w_i \ldots w_{j-1})</tex>|proof =  <b><tex>\Longrightarrow</tex></b><br/>Докажем индукцией по исполнению алгоритма.<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/>Это произошло, если <tex> \alpha = \alpha ' a</tex>, <tex>a = w_{j-1}</tex> и <tex> [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>.<br/>По предположению индукции <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex> и <tex>\alpha' \Rightarrow^* w_i \ldots w_{j-2}</tex>,<br/> тогда в силу <tex>a = w_{j-1}</tex> получаем <tex>\alpha = \alpha ' a \Rightarrow^* w_i \ldots w_{j-2}w_{j-1} = w_i \ldots w_{j-1} \ </tex>.<br/>Таким образом условия: <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex> и <tex>\alpha \Rightarrow^* w_i \ldots w_{j-1}</tex> выполняются. 2. Включаем по правилу <tex> \mathtt{predict} \ </tex>.<br/>По построению: <tex> \alpha = \varepsilon </tex> и <tex>i=j</tex>, что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\exists i' \le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i</tex>, из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex> и <tex> \alpha ' \Rightarrow^* w_{i'} \ldots w_{i-1}</tex>.<br/>Получаем, что <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0 \ldots w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \ldots w_{i-1} A \delta' \delta ''</tex>, в итоге <tex> S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, что нам и требовалось. 3. Включаем по правилу <tex> \mathtt{complete} \ </tex>.<br/>По построению: <tex> \alpha = \alpha ' A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>.<br/>Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. <b><tex>\Longleftarrow</tex></b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0 \ldots w_{i-1} A \delta \ </tex> из <tex>S'</tex> и <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>. После чего примениминдукцию по длине вывода <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>.<br/>Рассмотрим три случая последнего символа <tex>\alpha</tex>: 1. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i \ldots w_{j-2}</tex>.<br/>По предположению индукции: <tex>[A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>, а отсюда по правилу <tex> \mathtt{scan}</tex> получаем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>. 2. <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha ' \Rightarrow^* w_i \ldots w_{i'-1} \wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}</tex>.<br/>Тогда имеем <tex>[A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}</tex>. Также можно записать <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, как <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} w_i \ldots w_{i'-1}B \beta \delta</tex>,а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i'} \ldots 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>. 3. <tex>\alpha = \varepsilon </tex>, тогда <tex>i=j</tex>.<br/> Тогда либо <tex>i = 0 \wedge A = S \wedge \delta = \varepsilon</tex>, что доказывает базу индукции,<br/>либо вывод можно записать в виде <tex>S' \Rightarrow^* w_0 \ldots w{i'-1}w_{i'} \ldots w{i-1} A \delta ' \delta '' = w_0 \ldots w_{i-1} A \delta \ </tex> для некоторого правила <tex>(A' \rightarrow w_{i'} \ldots w_{i-1} A \delta ') \in P</tex>. <br/>Отсюда по предположению индукции <tex>[A' \rightarrow \cdot w_{i'} \ldots w_{i-1} A \delta ', i'] \in D_{i'} \ </tex>, что после нескольких применений правила <tex> \mathtt{scan}</tex> приводит к <tex>[A' \rightarrow w_{i'} \ldots w_{i-1} \cdot A \delta ', i'] \in D_{i} \ </tex>,после чего по правилу <tex> \mathtt{predict} \ </tex> получим <tex>[A \rightarrow \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> {||-| {| class="wikitable"|-!<tex>D_0</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[S' \rightarrow \cdot S, 0]</tex> || 0|-|<tex>[S \rightarrow \cdot T + S, 0]</tex> || 3|-|<tex>[S \rightarrow \cdot T, 0]</tex> || 3|-|<tex>[T \rightarrow \cdot F * T, 0]</tex> || 3|-|<tex>[T \rightarrow \cdot F, 0]</tex> || 3|-|<tex>[F \rightarrow \cdot ( S ), 0]</tex> || 3|-|<tex>[F \rightarrow \cdot a, 0]</tex> || 3|}|} || {| class="wikitable"|-!<tex>D_1</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow ( \cdot S ), 0]</tex> || 1|-|<tex>[S \rightarrow \cdot T + S, 1]</tex> || 3|-|<tex>[S \rightarrow \cdot T, 1]</tex> || 3|-|<tex>[T \rightarrow \cdot F * T, 1]</tex> || 3|-|<tex>[T \rightarrow \cdot F, 1]</tex> || 3|-|<tex>[F \rightarrow \cdot ( S ), 1]</tex> || 3|-|<tex>[F \rightarrow \cdot a, 1]</tex> || 3|}|} || {| class="wikitable"|-!<tex>D_2</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow a \cdot, 1]</tex> || 1|-|<tex>[T \rightarrow F \cdot * T, 1]</tex> || 2|-|<tex>[T \rightarrow F \cdot , 1]</tex> || 2|-|<tex>[S \rightarrow T \cdot , 1]</tex> || 2|-|<tex>[S \rightarrow T \cdot + S, 1]</tex> || 2|-|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2|}|} |-| {| class="wikitable"|-!<tex>D_3</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[S \rightarrow T + \cdot S, 1]</tex> || 1|-|<tex>[S \rightarrow \cdot T + S, 3]</tex> || 3|-|<tex>[S \rightarrow \cdot T, 3]</tex> || 3|-|<tex>[T \rightarrow \cdot F * T, 3]</tex> || 3|-|<tex>[T \rightarrow \cdot F, 3]</tex> || 3|-|<tex>[F \rightarrow \cdot ( S ), 3]</tex> || 3|-|<tex>[F \rightarrow \cdot a, 3]</tex> || 3|}|} || {| class="wikitable"|-!<tex>D_4</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow a \cdot , 3]</tex> || 1|-|<tex>[T \rightarrow F \cdot * T, 3]</tex> || 2|-|<tex>[T \rightarrow F \cdot , 3]</tex> || 2|-|<tex>[S \rightarrow T \cdot + S, 3]</tex> || 2|-|<tex>[S \rightarrow T \cdot , 3]</tex> || 2|-|<tex>[S \rightarrow T + S \cdot , 1]</tex> || 2|-|<tex>[F \rightarrow ( S \cdot ), 0]</tex> || 2|}|} || {| class="wikitable"|-!<tex>D_5</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow ( S )\cdot , 0]</tex> || 1|-|<tex>[T \rightarrow F \cdot * T, 0]</tex> || 2|-|<tex>[T \rightarrow F \cdot , 0]</tex> || 2|-|<tex>[S \rightarrow T \cdot + S, 0]</tex> || 2|-|<tex>[S \rightarrow T \cdot , 0]</tex> || 2|-|<tex>[S' \rightarrow S \cdot , 0]</tex> || 2|}|} |} Так как <tex>[S' \rightarrow S \cdot , 0] \in D_5</tex>, то <tex>w \in L(G) </tex>.<br> ==См. также==* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]

<b>Вход.</b> контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n<Источники информации==*[http:/tex>.<br><b>Выход.</b> Список разбора <tex>I_0, I_1, lpcs.math.msu. I_n<su/tex> для цепочки <tex>\omega<~sk/tex>.<br><b>Метод.<lehre/b><br>Строим <tex>I_0<fivt2013/tex><br><i>Шаг 1Earley.</i> Если <tex>S \rightarrow \alpha</tex> pdf Алексей Сорокин {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>.<br>Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>.<br><i>Шаг 2.</i> Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0Алгоритм Эрли]</tex>, уже принадлежащих <tex>I_0</tex>.<br><i>Шаг 3* Ахо А.</i> Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>Ульман Д. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там).<br>Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j{---1}</tex>. <br><i>Шаг 4.</i> Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \betaТеория синтакcического анализа, i] </tex>.<br>Выполняем шаги 5 перевода и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>компиляции.<br><i>Шаг 5Том 1.</i> Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>Синтаксический анализ. Ищем ситуации вида <tex>[B \rightarrow \gamma \cdot A \delta, k]</tex>Пер. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \gamma A \cdot \delta, k]</tex>с англ.<br><i>Шаг 6{{---}} М.</i> Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma:«Мир», j]</tex>.<br>Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>.<br><tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>.<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 4.'''&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 51978.'''&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 6.'''<br>[[Файл:Эрли2.png]] [[Файл:Эрли1С.png]] [[Файл:Эрли3358 — 364.png]]