1632
правки
Изменения
м
==Определения==
'''Ситуации хранятся в множествах <tex>jD_0, \ldots ,D_{n-1}</tex>-м списком , называемых '''списками ситуаций''' <tex>I_j</tex> для входной цепочки <tex>\omega = a_1 a_2 ... a_n</tex>, где Причем наличие ситуации <tex>0 \leqslant j \leqslant n</tex>, называется множество ситуаций <tex>\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* a_{i+1} ... a_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i \rbrace</tex>. То есть в <tex>\gamma \alpha j</tex> выводит часть -м списке ситуаций <tex>\omegaD_j</tex> c первого по <tex>j</tex>-й символ.}} {{Леммаравносильно тому, что |statement = <tex>(\exists \alpha : [S \rightarrow \alpha \cdot, 0] delta \in I_n) \Leftrightarrow Sigma \omega \in Lcup N : ((G)</tex>.|proof = Поскольку <tex>S ' \Rightarrow^* w_0 \gamma S \delta</tex> (при <tex>\gamma = ldots w_{i-1} A \delta = \varepsilon</tex>), из определения <tex>I_n</tex> получаем, что <tex>([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha wedge A \Rightarrow^* a_1 ... a_n = w_i \omegaldots w_{j-1})</tex>.
Построим Чтобы воспользоваться леммой, необходимо найти <tex>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора для , причём при построении <tex>D_j</tex> используются <tex>D_0, \omegaldots, D_{j}</tex> (то есть элементы списков с помощью данного алгоритма меньшими номерами и воспользуемся леммойситуации, доказанной вышесодержащиеся в текущем списке на данный момент).<br>
Для простоты добавим новый стартовый вспомогательный нетерминал Алгоритм основывается на следующих трёх правилах:# Если <tex>S'[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>S' (B \rightarrow S\eta) \in P </tex>, то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}</tex>.
=== Псевдокод ===Для простоты добавим новый стартовый вспомогательный нетерминал <tex>I_0S'</tex> ∪= и правило <tex>[(S' \rightarrow \cdot S, 0])</tex> # Правило (0) — инициализация useful_loop(0).
=====Алгоритм не добавит в список ситуацию, которая ему не принадлежит:=====<b><tex>\Longrightarrow</tex></b><br/>
21. Включаем по правилу 2<tex> \mathtt{scan} \ </tex>.<br/>Тогда Это произошло, если <tex>\alpha = \alpha' B a</tex>, [A \rightarrow \alpha' \cdot B \beta, k] \in I_<tex>a = w_{ij-1}</tex> и <tex> [B A \rightarrow \eta alpha ' \cdota \beta, i] \in I_D_{j-1} </tex>. <br/>По предположению, индукции <tex>\alphaS' \Rightarrow^* a_{k+1}...a_{i}, w_0 \eta \Rightarrow^* a_ldots w_{i+-1}...a_{j} A \delta</tex>, откуда и <tex>\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_w_i \ldots w_{j-2} </tex>. Кроме того, существуют <tex>\gamma'<br/tex> и тогда в силу <tex>\delta' a = w_{j-1}</tex> такие, что получаем <tex>S\alpha = \alpha ' a \Rightarrow^* w_i \gamma' A \delta', ldots w_{j-2}w_{j-1} = w_i \gamma' = a_1...a_ldots w_{kj-1} \ </tex>. Значит, при <br/>Таким образом условия: <tex>S' \gamma = Rightarrow^* w_0 \gamma', ldots w_{i-1} A \delta = \delta'</tex> и <tex>[A \rightarrow \alpha \cdot Rightarrow^* w_i \beta, i] \in I_jldots w_{j-1}</tex>выполняются.
32. Включаем по правилу 3<tex> \mathtt{predict} \ </tex>.<br/>Тогда По построению: <tex>\alpha = \varepsilon, </tex> и <tex>i = j</tex>, что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\exists i' \le i</tex> и ситуация <tex>[B A' \rightarrow \alpha' \cdot A \etadelta ', ki'] \in I_{j}, A \Rightarrow \betaD_i</tex>. По , из чего по предположению индукции следует <tex>\alphaS' \Rightarrow^* a_w_0 \ldots w_{k+i'-1}...a_{i}A' \delta ''</tex> и существуют <tex>\gammaalpha ' \Rightarrow^* w_{i'} \ldots w_{i-1}</tex> и <tex>\delta' .<br/tex> такиеПолучаем, что <tex>S' \Rightarrow^* w_0 \gammaldots w_{i'-1} A' B \delta', \gamma' \Rightarrow^* a_1...a_{k} </tex>. Значит, при значит <tex>S \gamma = Rightarrow^* w_0 \gammaldots w_{i' -1} \alpha', A \delta = \eta ' \delta'' </tex> выполнено , следовательно <tex> S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \gamma ldots w_{i-1} A \delta' \delta ''</tex>, следовательно в итоге <tex>[A S' \rightarrow Rightarrow^* w_0 \alpha \cdot \beta, ldots w_{i] -1} A \in I_jdelta</tex>, что нам и требовалось.
=====В каждый список попадут все ситуации, которые ему принадлежат3. Включаем по правилу <tex> \mathtt{complete} \ </tex>.<br/>По построению:=====Для всех наборов <tex>\tau alpha = \langle \alpha, \beta, \gamma, \delta, ' A, i , j \rangle' </tex> нужно доказать, что, если и <tex> S\exists i' \Rightarrow^* \gamma A , \delta, \gamma \Rightarrow^* a_1...a_{i}, (: [A \rightarrow \alpha ' \cdot A' \beta) , i] \in P, \alpha \Rightarrow^* a_D_{i+1'}...a_{j}</tex>, то алгоритм добавит <tex> \wedge [A ' \rightarrow \alpha eta \cdot \beta, i']\in D_j</tex> в .<br/>Cледовательно <tex> I_\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
''Рангом набора'' <b><tex> \tau Longleftarrow</tex> называется </b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex> w_0 \tau_ldots w_{S'i-1}(A \tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(delta \tau))</tex>, где из <tex>\tau_{S'}(\tau)</tex> — длина кратчайшего вывода и <tex>S' w_i \Rightarrow^* \gamma A \delta ldots w_{j-1}</tex>, из <tex>\tau_{\gamma}(\tau)alpha</tex> — длина кратчайшего . После чего примениминдукцию по длине вывода <tex>w_i \gamma \Rightarrow^* a_1...a_ldots w_{ij-1}</tex>, из <tex>\tau_{\alpha}(\tau)</tex> — длина кратчайшего вывода .<br/>Рассмотрим три случая последнего символа <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.:
Докажем утверждение индукцией по рангу набора1.<br/>База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{S'} alpha = \tau_{\gamma} = \tau_{\alpha} = j = i = 0' a</tex>. Значит, тогда <tex>A a = S'w_{j-1}</tex>, и <tex>\alpha = ' \gamma = Rightarrow^* w_i \delta = \varepsilon ldots w_{j-2}</tex>, <tex>\beta = S .<br/tex>. При инициализации такая ситуация По предположению индукции: <tex>[S' A \rightarrow \alpha ' \cdot Sa \beta, 0i]\in D_{j-1}</tex> будет добавлена в , а отсюда по правилу <tex>I_0\mathtt{scan}</tex>.<br/>Индукционный переход:пусть ранг получаем <tex>[A \tau</tex> равен <tex>r > 0</tex>rightarrow \alpha ' a \cdot \beta, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>i] \tauin D_{j}</tex>. Для этого рассмотрим три случая:
12. <tex>\alpha</tex> оканчивается терминалом.<br/><tex>\alpha = \alpha' cB</tex>. , тогда <tex>\exists i' : \alpha ' \Rightarrow^*a_w_i \ldots w_{i+'-1}...a_\wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}</tex>, значит <tex>c = a_{j}.<br/tex>. Рассмотрим набор Тогда имеем <tex>[A \tau' = \langle rightarrow \alpha', a_{j} a \cdot \beta, i] \gamma, \delta, A, i, in D_{j-1 \rangle }</tex>. Также можно записать <tex>(A S' \rightarrow Rightarrow^* w_0 \alpha' a_ldots w_{ji-1} A \beta) \in Pdelta</tex>, следовательно ранг как <tex>S' \Rightarrow^* w_0 \ldots w_{i-1} w_i \tauldots w_{i'</tex> равен <tex>r - 21}B \beta \delta</tex>, так как а также <tex>B \tau_{S'}(rightarrow \tau) = eta \tau_{S'}(wedge \tau'), eta \tau_rightarrow w_{\gamma}(\tau) = \tau_{\gamma}(\taui'), \tau_{\alpha}(\tau) = \tau_ldots w_{\alphaj-1}(\tau')</tex>. Значит, <br/>Применяя индукцию по предположению второму параметру получим <tex>[A B \rightarrow \alpha' eta \cdot a_{j} \beta, i'] \in I_D_j \ </tex>, откуда по правилу <tex> \mathtt{j-1complete}</tex> и получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i] </tex> будет добавлена в <tex>I_\in D_{j}</tex> по правилу 1.
23. <tex>\alpha</tex> оканчивается нетерминалом.<br/> <tex>\alpha = \alpha' B</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>\mathcal {9} kvarepsilon </tex> такое, что тогда <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{=j}</tex>.<br/>Рассмотрим набор Тогда либо <tex>i = 0 \tau' wedge A = S \langle \alpha', B \beta, \gamma, wedge \delta, A, i, k = \ranglevarepsilon</tex>, его ранг меньше <tex>r</tex>, следовательно <tex>[A \rightarrow \alpha' \cdot B \betaчто доказывает базу индукции, i] \in I_{k}</tex> по предположению.<br/>Пусть <tex>B \Rightarrow \eta</tex> — первый шаг либо вывод можно записать в кратчайшем выводе виде <tex>B S' \Rightarrow^* a_w_0 \ldots w{k+i'-1}...a_w_{ji'}</tex>. Рассмотрим набор <tex>\tau'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle</tex>. <tex>S \Rightarrow^* \gamma ldots w{i-1} A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_{S'}(\tau'') = w_0 \leqslant \tau_{S'}(\tau) + 1</tex>.<br> Пусть длина кратчайшего вывода <tex>\alpha' \Rightarrow^*a_ldots w_{i+-1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> B A \delta \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>. Тогда для некоторого правила <tex>\tau_{\alpha}(A' \tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_rightarrow w_{k+1}...a_{ji'}</tex>, то <tex>\tau_ldots w_{\alpha}(\tau'') = n_2 i- 1</tex>. Очевидно, что <tex>\tau_{\gamma}(A \tau'delta ') = \tau_{\gamma}(\tau) + n_1in P</tex>. Тогда ранг <tex>\tau''<br/tex> равен Отсюда по предположению индукции <tex>\tau_{S[A'}(\tau'') + 2(rightarrow \tau_cdot w_{\gammai'}(\tau'') + \tau_ldots w_{\alphai-1}(A \taudelta ', i') + j) ] \leqslant \tau_in D_{Si'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)</tex> , что после нескольких применений правила <tex>= \tau_{S'}(\tau) - 1 + 2(\tau_mathtt{\gamma}(\tau) + \tau_{\alphascan}(\tau) + j) < r</tex>. Значит, по предположению для <tex>\tau''</tex>, приводит к <tex>[B A' \rightarrow w_{i'} \eta ldots w_{i-1} \cdot, k] \in I_{j}</tex>. Из того, что <tex>[ A \rightarrow \alphadelta ' \cdot B \beta, i'] \in I_D_{ki}\ </tex> и ,после чего по правилу <tex>[B \rightarrow \eta \cdot, k] \in I_mathtt{jpredict}\ </tex>, по правилу 2 получим <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_\in D_{j}\ </tex>, что и требовалось.
3. <tex>\alpha = \varepsilon</tex>.<br/>
В этом случае <tex>i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P</tex>.<br/>
<tex>\tau_{S'}(\tau) \neq 0</tex> т.к. иначе <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_{\gamma}(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, но <tex>r > 0</tex>.
Т.к. <tex>\tau_{S'}(\tau) > 0</tex>, <tex> \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>(B \rightarrow \gamma'' A \delta'') \in P</tex>. Рассмотрим набор <tex>\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle</tex>, где <tex>k</tex> такое, что <tex>\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex>.
Пусть длина кратчайшего вывода <tex>\gamma' \Rightarrow^*a_{1}...a_{k}</tex> равна <tex>n_1</tex>, а длина кратчайшего вывода <tex> \gamma'' \Rightarrow^* a_{k+1}...a_{j}</tex> равна <tex>n_2</tex>.<br/>
Найдем ранг <tex>\tau'</tex>. <tex>\tau_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2</tex>. <tex>\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\tau) = n_1 + n_2</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 1</tex>. Значит, по предположению <tex>[B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}</tex>, следовательно по правилу 3 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
==Литература==[[Категория: Теория формальных языков]]''Ахо А., Ульман Д.'' Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.[[Категория: Контекстно-свободные грамматики]][[Категория:«Мир», 1978. С. 358 — 364.Алгоритмы разбора]]
rollbackEdits.php mass rollback
__TOC__'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>\omegaw</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>\omegaw</tex>.<br/>'''Выход:''' <tex>true</tex>, если <tex>\omegaw</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
{{Определение
|definition =
Пусть <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 \alpha \cdot \beta, i]</tex>, где <tex>A \rightarrow \alpha \beta </tex> — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>\omegaw</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex>\omegacdot \notin \Sigma \cup N</tex>).
}}
{{Определение
|definition =
}}
{{Определение
|definition =
Последовательность списков ситуаций <tex>I_0D_0, I_1D_1, ..\ldots, I_nD_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>\omegaw</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..n</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_{j} a \beta, i] \in I_D_{j-1}</tex> '''if''' <tex>I_ja</tex> &== <tex>w_{j - 1}</tex> <tex>D_{j}</tex> <tex> \cup;</tex>= <tex>[A \rightarrow \alpha a_{j} a \cdot \beta, i]</tex> # Правило '''function''' <tex>\mathtt{complete}(1D, j, G, w)</tex>: '''for''' <tex>[B \rightarrow \eta \ \cdot, i] \in D_{j} </tex> useful_loop('''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 useful_loop(j): do for ''' <tex>[B \rightarrow \eta \cdot mathtt{predict}(D, j, G, i] \in I_jw)</tex>: '''for ''' <tex>[A \rightarrow \alpha \cdot B \beta, ki] \in I_D_{ij}</tex> <tex>I_j</tex> ∪= '''for''' <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex> # Правило (2) for <tex>[B \rightarrow \alpha \cdot A \eta, k] ) \in I_jP </tex> for <tex>\beta : (A \rightarrow \beta) \in PD_{j}</tex> <tex>I_j\cup</tex> ∪= <tex>[A B \rightarrow \cdot \beta\eta, j]</tex> # Правило (3) while на данной итерации какое-то множество изменилось
==Корректность алгоритма==
{{Теорема
|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 =
Докажем индукцией по исполнению алгоритма.<br/>
<u> ''База (инициализация) индукции: '' <tex/u>\alpha = \varepsilon \Rightarrow^* \varepsilon <br/tex> и <tex>[S' \Rightarrow^* rightarrow \gamma cdot S , 0] \delta </tex> при <tex>\gamma = \delta = in D_0 \varepsilon </tex>.<br/><u> ''Индукционный переход: пусть в '' <tex/u> I_{0},...,I_{j} <br/tex> нет лишних Пусть предположение верно для всех списков ситуаций. Пусть включаем с номерами меньше <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая: 1. Включаем по правилу 1.<br/>Тогда Разберемся, в результате применения какого правила ситуация <tex>\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>. По предположению, <tex>\alpha' \Rightarrow^* a_{i+1}...a_{j-1} </tex> и существуют <tex>\gamma'</tex> и <tex>\delta' попала в </tex> такие, что <tex>S' \Rightarrow^* \gamma' A \delta', \gamma' \Rightarrow^* a_1...a_{i} </tex>. Значит, <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_D_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta'</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_j<br/tex>.
}}
==Пример==
Построим список разбора для строки <tex>\omega w = (a + a)</tex> в грамматике со следующими правилами:
* <tex>S \rightarrow T + S</tex>
* <tex>S \rightarrow T </tex>
{| class="wikitable"
|-
!<tex>I_0D_0</tex>
|-
|
{| class="wikitable"
|-
!<tex>I_1D_1</tex>
|-
|
{| class="wikitable"
|-
!<tex>I_2D_2</tex>
|-
|
{| class="wikitable"
|-
!<tex>I_3D_3</tex>
|-
|
{| class="wikitable"
|-
!<tex>I_4D_4</tex>
|-
|
{| class="wikitable"
|-
!<tex>I_5D_5</tex>
|-
|
|}
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5D_5</tex>, то <tex>\omega w \in L(G) </tex>.<br> ==См. также==* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] ==Источники информации==*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
