Изменения

Пусть <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>\omegaw</tex>. , называется '''ситуацией''', относящейся к цепочке <tex>\cdotw</tex> является метасимволом, не принадлежащим ни где '''<tex>N\cdot </tex>''' {{---}} вспомогательный символ, ни который не явлется терминалом или нетерминалом ( <tex>\cdot \notin \Sigma\cup 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>\omegaw</tex>.

==Алгоритм Эрли==Построим список разбора для Чтобы воспользоваться леммой, необходимо найти <tex>\omegaD_n</tex>Строим для <tex>I_0w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <brtex><i>Шаг 1.D_j</itex> Если используются <tex>S D_0, \rightarrow \alpha \in Pldots, D_{j}</tex>(то есть элементы списков с меньшими номерами и ситуации, включить содержащиеся в текущем списке на данный момент). Алгоритм основывается на следующих трёх правилах:# Если <tex>[S A \rightarrow \alpha \cdot w_{j} \alphabeta, 0i]\in D_{j-1}</tex> в (где <tex>I_0w_j</tex>.<br>Пока можно включить новые ситуации в — <tex>I_0j</tex> повторяем шаги 2 и 3.-ый символ строки), то <brtex><[A \rightarrow \alpha w_{j} \cdot \beta, i>Шаг 2.] \in D_j</itex> .# Если <tex>[B \rightarrow \gamma eta \ \cdot, 0i] \in I_0D_j</tex>, включить в и <tex>I_0[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex> ситуацию , то <tex>[A \rightarrow \alpha B \cdot \beta, 0k]\in D_j</tex> для всех .# Если <tex>[A \rightarrow \alpha \ \cdot B \beta, 0i]\in D_{j} </tex> из и <tex>I_0(B \rightarrow \eta) \in P </tex>.<br><i>Шаг 3.</i> Для всех , то <tex>[A B \rightarrow \alpha cdot \cdot B \betaeta, 0j] \in I_0D_{j}</tex>, для всех . === Псевдокод ===Для простоты добавим новый стартовый вспомогательный нетерминал <tex>\gammaS'</tex> таких, что и правило <tex>B (S' \rightarrow S)</tex>. '''function''' <tex>\gamma \in Pmathtt{earley}(G, w)</tex> включить : <font color=green>// Инициализация </font> <tex>D_{0} = \lbrace [B S' \rightarrow \cdot \gammaS, 0]\rbrace </tex> в '''for''' <tex>i = 1</tex> '''to''' <tex>len(w)</tex> <tex>D_i</tex> = <tex>I_0\varnothing </tex>. <font color=green>// Вычисление ситуаций <br/font>Построение '''for''' <tex>j = 0</tex>I_j'''to''' <tex>len(w)</tex> по <tex>I_0\mathtt{scan}(D, I_1j, ...G, I_w)</tex> '''while''' <tex>D_j</tex> изменяется <tex>\mathtt{complete}(D, j-1}, G, w)</tex>. <tex>\mathtt{predict}(D, j, G, w)<br/tex> <ifont color=green>Шаг 4.// Результат </ifont> Для каждой ситуации '''if''' <tex>[B S' \rightarrow S \alpha \cdot a_{j} \beta, i0] \in I_D_{j-1len(w)}</tex> '''return''' ''true'' '''else''' '''return''' ''false''    '''function''' <tex>\mathtt{scan}(D, j, G, w)</tex>a_j: '''if''' <tex>j</tex>— j-й символ в == <tex>\omega0</tex> включить '''return''' '''for''' <tex>[B A \rightarrow \alpha a \cdot a \beta, i] \in D_{j - 1} </tex> в '''if''' <tex>I_ja</tex>.== <tex>w_{j - 1}<br/tex>Пока можно включить новые ситуации в <tex>I_jD_{j}</tex> повторяем шаги 5 и 6.<brtex><i>Шаг 5.\cup</itex> Если = <tex>[A \rightarrow \alpha a \cdot \beta, i] </tex>  '''function''' <tex>\in I_jmathtt{complete}(D, j, G, w)</tex>, то для каждой ситуации : '''for''' <tex>[B \rightarrow \gamma eta \ \cdot A \beta, ki] \in I_D_{ij}</tex> включить '''for''' <tex>[B A \rightarrow \gamma A alpha \cdot B \beta, kj]\in D_{i} </tex> в <tex>I_jD_{j}</tex>.<brtex><i>Шаг 6.\cup</itex> Для всех = <tex>[A \rightarrow \alpha B \cdot B \beta, ij] \in I_j</tex>, для всех   '''function''' <tex>\gammamathtt{predict}(D, j, G, w)</tex> таких, что : '''for''' <tex>B [A \rightarrow \gamma alpha \cdot B \beta, i] \in PD_{j} </tex> включить '''for''' <tex>[(B \rightarrow \cdot eta) \gamma, j]in P </tex> в <tex>I_jD_{j}</tex>.<br>Если <tex>[S \rightarrow \alpha \cdot, 0] \in I_ncup</tex>, то = <tex>[B \omega rightarrow \in L(G) cdot \ \eta, j]</tex>.<br>

|statement = Приведенный алгоритм правильно строит все списки ситуаций. То есть алгоритм поддерживает инвариант <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_D_{j} \Leftrightarrow Longleftrightarrow \alpha exists \Rightarrow^* a_{i+1}...a_{j}</tex> и <tex> delta \mathcal {9} in \gamma </tex> и <tex> Sigma \delta</tex> такие, что <tex>cup N : ((S ' \Rightarrow^* w_0 \gamma ldots w_{i-1} A \delta</tex> и <tex> ) \gamma wedge A \Rightarrow^* a_1...a_w_i \ldots w_{ij-1})</tex>

*Необходимость  <b><tex>\Longrightarrow</tex></b><br/>Докажем индукцией по индукцииисполнению алгоритма.<br/><u> ''База индукции: для любой ситуации из '' <tex/u>I_0<br/tex> <tex>[S' \rightarrow \alpha cdot S, 0] \Rightarrow^* in D_0 \varepsilon </tex> и .<br/><texu> ''Индукционный переход:'' </u>S \Rightarrow^* \gamma A \delta <br/tex> при Пусть предположение верно для всех списков ситуаций с номерами меньше <tex>\gamma = \varepsilon j </tex>.<br>Индукционный переход (и.п.): пусть верно для всех ситуаций из списков Разберемся, в результате применения какого правила ситуация <tex> I_{i}, i [A \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>I_D_{j}</tex>. Рассмотрим три случая:<br/>*Пусть включаем 1. Включаем по правилу 4<brtex>Тогда \mathtt{scan} \ </tex>.<br/>Это произошло, если <tex>\alpha = \alpha' a_a</tex>, <tex>a = w_{j-1} , [A </tex> и <tex> [A \rightarrow \alpha' \cdot a_{j} a \beta, i] \in I_D_{j-1}</tex>. <br/>По и.п. предположению индукции <tex>\alphaS' \Rightarrow^* a_w_0 \ldots w_{i+1}...a_{j-1} A \delta</tex>и существуют <tex>\gammaalpha'\Rightarrow^* w_i \ldots w_{j-2}</tex> и ,<br/> тогда в силу <tex>\delta' a = w_{j-1}</tex> такие, что получаем <tex>S \alpha = \alpha ' a \Rightarrow^* w_i \gamma' A \delta', \gamma' = a_1...a_ldots w_{ij-2} </w_{j-1} = w_i \ldots w_{j-1} \ </tex>. Значит <br/>Таким образом условия: <tex> \alpha = \alphaS' a_{j} \Rightarrow^* a_w_0 \ldots w_{i+-1}...a_{j}A \delta</tex> и при <tex>\gamma = alpha \gamma', Rightarrow^* w_i \delta = \delta' ldots w_{j-1}</tex> для <texвыполняются. 2. Включаем по правилу <tex>[A \rightarrow \alpha \cdot mathtt{predict} \beta, i]</tex> утверждение верно.*Пусть включаем по правилу 5<br/>Тогда По построению: <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \in I_{i}varepsilon </tex> и <tex> [B \rightarrow \eta \cdot, i] \in I_{=j} </tex>, что автоматически влечет второй пункт утверждения. По и.п. <br/>Кроме того <tex>\alphaexists i' \Rightarrow^* a_{k+1}...a_{le i}, \eta \Rightarrow^* a_{i+1}...a_{j} </tex>, откуда и ситуация <tex>[A' \alpha = rightarrow \alpha' B \Rightarrow^*a_{k+1}...a_{j} cdot A \delta ', i'] \in D_i</tex>. Также , из чего по и.п. существуют предположению индукции следует <tex>S' \gamma'Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex> и <tex>\deltaalpha ' </tex> такие, что <tex>S \Rightarrow^* \gammaw_{i' A \delta', } \gamma' = a_1...a_ldots w_{ki-1} </tex>. Значит при <br/>Получаем, что <tex>S' \gamma = Rightarrow^* w_0 \gammaldots w_{i'-1} A', \delta = \delta'' </tex> для , значит <tex>[A S \Rightarrow^* w_0 \rightarrow ldots w_{i'-1} \alpha ' A \cdot delta' \beta, i]delta '' </tex> утверждение верно.*Пусть включаем по правилу 6<br>Тогда , следовательно <tex>S' \alpha = Rightarrow^* w_0 \varepsilon, ldots w_{i'-1} w_{i = j, [B \rightarrow \alpha' } \cdot ldots w_{i-1} A \beta, k] delta' \in I_{j}delta ''</tex>. По и.п. , в итоге <tex>\alphaS' \Rightarrow^* a_w_0 \ldots w_{k+i-1}...a_{i}A \delta</tex> , что нам и существуют <требовалось. 3. Включаем по правилу <tex>\gamma'mathtt{complete} \ </tex> и .<br/>По построению: <tex>\deltaalpha = \alpha ' A' </tex> такие, что и <tex>S \Rightarrow^* exists i', \delta : [A \rightarrow \gammaalpha ' B \deltacdot A'\beta, i] \gammain D_{i' = a_1...a_{k} <\wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>. Значит при <br/>Cледовательно <tex>\gamma alpha = \gammaalpha ' \alphaA', \delta = Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \beta ldots w_{j} = w_i \delta' ldots w_{j-1}</tex> выполнено <tex, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. <b><tex> S \Rightarrow^* \gamma A \deltaLongleftarrow</tex>, значит для <tex/b>[A \rightarrow <br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0 \alpha ldots w_{i-1} A \cdot delta \beta, i]</tex> утверждение верно.*ДостаточностьДля всех наборов из <tex>\tau = {\alpha, \beta, \gamma, \delta, A, i , j} S'</tex> нужно доказать, что если и <tex> S w_i \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{ildots w_{j-1}, A \rightarrow </tex> из <tex>\alpha </tex>. После чего примениминдукцию по длине вывода <tex>w_i \beta \in P, \alpha \Rightarrow^* a_ldots w_{i+j-1}...a{j}</tex>, то из <tex> [A \rightarrow \alpha \cdot B \beta, i] \in I_{j}</tex>.<br/>*Рангом набора Рассмотрим три случая последнего символа <tex> \tau alpha</tex> называется : 1. <tex> \tau_{1}(alpha = \tau) + 2(j + \tau_{2}(\tau) + \tau_{3}(\tau))alpha ' a</tex>, где тогда <tex>\tau_a = w_{j-1}(\tau)</tex> — длина кратчайшего вывода и <tex>S \alpha ' \Rightarrow^* w_i \gamma A \delta </tex>, <tex>\tau_ldots w_{j-2}(\tau)</tex> — длина кратчайшего вывода .<texbr/>\gamma \Rightarrow^* a_1...a_{i}</tex>, По предположению индукции: <tex>[A \tau_{3}(rightarrow \tau)</tex> — длина кратчайшего вывода <tex>alpha ' \alpha cdot a \Rightarrow^* a_{beta, i+1}...a_] \in D_{j-1}</tex>.Докажем утверждение , а отсюда по индукции:<br>База: если ранг правилу <tex>\taumathtt{scan}</tex> равен 0, то получаем <tex>[A \tau_{1} = rightarrow \tau_{2} = alpha ' a \tau_{3cdot \beta, i] \in D_{j} = j = i = 0</tex>. Значит  2. <tex>\alpha = \gamma = \delta = \varepsilon alpha ' B</tex>, тогда <tex>A = S</tex>, следовательно <tex>S \rightarrow exists i' : \alpha ' \beta Rightarrow^* w_i \in P</ldots w_{i'-1} \wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}</tex>. Значит по правилу 1 <br/>Тогда имеем <tex>[S A \rightarrow \alpha ' a \cdot \beta, 0i] \in I_0D_{j}</tex>Индукционный переход:<br>Пусть ранг . Также можно записать <tex>S' \tau</tex> равен <tex>r > 0Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора как <tex>S' \tau</tex>. Для этого рассмотрим три случая:*<tex>Rightarrow^* w_0 \ldots w_{i-1} w_i \ldots w_{i'-1}B \beta \alphadelta</tex> оканчивается терминалом<br>,а также <tex>B \rightarrow \alpha = eta \alpha' a</tex>. <tex>wedge \alpha eta \Rightarrow^*a_rightarrow w_{i+1'}...a_\ldots w_{j-1}</tex>, значит <tex>a = a_{j}.<br/tex>. Рассмотрим набор Применяя индукцию по второму параметру получим <tex>[B \tau' = rightarrow \mathcal {f} eta \alphacdot, i', a_{j} ] \beta, in D_j \gamma</tex>, откуда по правилу <tex> \delta, A, i, j-1 \mathcal mathtt{gcomplete} </tex>. получаем <tex>[A \rightarrow \alpha' a_{j} B \cdot \beta , i] \in PD_{j}</tex>, следовательно ранг . 3. <tex>\tau'alpha = \varepsilon </tex> равен , тогда <tex>r - 2i=j</tex>, так как .<br/> Тогда либо <tex>i = 0 \tau_{1}(\tau) wedge A = S \tau_1(wedge \tau'), \tau_2(\tau) delta = \tau_2(\tau')varepsilon</tex>, что доказывает базу индукции, \tau_{3}(\tau) = \tau_3(\tau')<br/tex>. Значит по и.п. либо вывод можно записать в виде <tex>[A S' \rightarrow Rightarrow^* w_0 \alphaldots w{i' \cdot a_-1}w_{ji'} \beta, ldots w{i] \in I_{j-1}</A \delta ' \delta '' = w_0 \ldots w_{i-1} A \delta \ </tex>, по правилу 4 получаем, что для некоторого правила <tex>[(A ' \rightarrow w_{i'} \ldots w_{i-1} A \alpha \cdot delta ') \beta, i] in P</tex> будет добавлена в . <br/>Отсюда по предположению индукции <tex>I_{j[A' \rightarrow \cdot w_{i'}</tex>.*<tex>\alpha</tex> оканчивается нетерминалом<brldots w_{i-1} A \delta ', i'] \in D_{i'} \ </tex>, что после нескольких применений правила <tex>\alpha = \alpha' Bmathtt{scan}</tex>. приводит к <tex>[A' \alpha rightarrow w_{i'} \Rightarrow^*a_ldots w_{i+-1}...a_\cdot A \delta ', i'] \in D_{ji}\ </tex>, значит после чего по правилу <tex>\mathcal mathtt{9predict} k\ </tex> такое, что получим <tex>[A \rightarrow \alpha' cdot \Rightarrow^*a_{beta, i+1}...a_] \in D_{k}, B \Rightarrow^* a_{k+1}...a_{j}</tex>.<br> Рассмотрим набор <tex>\tau' = \mathcal {f} \alpha', B \beta, \gamma, \delta, A, i, k \mathcal {g} </tex>, его ранг меньше <tex>r</tex>. По и.п. <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex>. <br>Пусть <tex>B \Rightarrow \eta</tex> — первый шаг в кратчайшем выводе <tex>B \Rightarrow^* a_{k+1}...a_{j}</tex>. Рассмотрим набор <tex>\tau'' = \mathcal {f} \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \mathcal {g} </tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_1(\tau'') \leqslant \tau_1(\tau) + 1</tex>.<br> Обозначим длину кратчайшего вывода <tex>\alpha' \Rightarrow^*a_{i+1}...a_{k}</tex> за <tex>n_1</tex>, а длину кратчайшего вывода <tex> B \Rightarrow^* a_{k+1}...a_{j}</tex> за <tex>n_2</tex>. Тогда <tex>\tau_3(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_3(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_2(\tau'') = \tau_2(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\tau_1(\tau'') + 2(\tau_2(\tau'') + \tau_3(\tau'') + j) \leqslant \tau_1(\tau) + 1 + 2(\tau_2(\tau) + n_1 + n_2 - 1 + j) = \tau_1(\tau) - 1 + 2(\tau_2(\tau) + \tau_3(\tau) + j) < r</tex>. Значит по и.п. для <tex>\tau''</tex>, <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex>. Из того, что <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}</tex> и <tex>[B \rightarrow \eta \cdot, k] \in I_{j}</tex> по правилу 4 или 5 <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.*<tex>\alpha</tex> является пустой<br><tex>\alpha = \varepsilon</tex>, значит <tex>i = j, \tau_3(\tau) = 0</tex>.<br> Если <tex> \tau_1(\tau) = 0</tex>, то <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_2(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, а по и.п. <tex>r > 0</tex>. Значит <tex> \tau_1(\tau) \neq 0</tex>. Тогда <tex> \mathcal {9} B, \gamma', \gamma'', \delta', \delta''</tex> такие, что <tex>S \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>B = \gamma'' A \delta'' \in P</tex>.Рассмотрим набор <tex>\tau' = \mathcal {f} \gamma'', A \delta'', \gamma', \delta', B, k, j \mathcal {g} </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_1(\tau') = \tau_1(\tau) - 1, \tau_2(\tau') = n_1, \tau_3(\tau') = n_2, \tau_3(\tau) = 0, \tau_2(\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>, следовательно по правилу 6 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{jj}\ </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> ==См. также==* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] ==Источники информации==*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]* Ахо А.Ахо, Дж. УльманД. {{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический Синтаксический анализ.Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364. [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Алгоритмы разбора]]