Изменения

__TOC__'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>. '''Вход:''' КС грамматика <tex> G==Определения==\langle N,\Sigma, P, S \rangle</tex> и слово <tex>w</tex>.<br/>'''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе. 

Пусть <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>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \omegaSigma \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>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора для , причём при построении <tex>D_j</tex> используются <tex>D_0, \omegaldots, D_{j}</tex>(то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент). Строим Алгоритм основывается на следующих трёх правилах:# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex>I_0(где <tex>w_j</tex>— <brtex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>Шаг 1.# Если <tex>[B \rightarrow \eta \ \cdot, i] \in D_j</itex> Если и <tex>S [A \rightarrow \alpha \cdot B \beta, k] \in PD_i</tex>, включить то <tex>[S A \rightarrow \alpha B \cdot \beta, k] \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>., то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}<br/tex>. === Псевдокод ===Пока можно включить новые ситуации в Для простоты добавим новый стартовый вспомогательный нетерминал <tex>I_0S'</tex> повторяем шаги 2 и 3правило <tex>(S' \rightarrow S)</tex>. '''function''' <brtex>\mathtt{earley}(G, w)</tex>: <ifont color=green>Шаг 2.// Инициализация </ifont> Если <tex>D_{0} = \lbrace [B S' \rightarrow \gamma cdot \cdotS, 0] \in I_0rbrace </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>I_0 <tex>\mathtt{predict}(D, j, G, w)</tex> ситуацию <font color=green>// Результат </font> '''if''' <tex>[A S' \rightarrow S \alpha B \cdot , 0] \in D_{len(w)} </tex> '''return''' ''true'' '''else''' '''return''' ''false''    '''function''' <tex>\betamathtt{scan}(D, j, G, w)</tex>: '''if''' <tex>j</tex> == <tex>0]</tex> для всех '''return''' '''for''' <tex>[A \rightarrow \alpha \cdot B a \beta, 0i]\in D_{j - 1} </tex> из '''if''' <tex>I_0a</tex>.== <tex>w_{j - 1}<br/tex> <tex>D_{j}<i/tex> <tex>Шаг 3.\cup</itex> Для всех = <tex>[A \rightarrow \alpha a \cdot B \beta, 0i] \in I_0</tex>, для всех   '''function''' <tex>\gammamathtt{complete}(D, j, G, w)</tex> таких, что : '''for''' <tex>[B \rightarrow \gamma eta \ \cdot, i] \in PD_{j} </tex> включить '''for''' <tex>[B A \rightarrow \alpha \cdot B \gammabeta, 0j]\in D_{i} </tex> в <tex>I_0D_{j}</tex>.<brtex> \cup</tex>Построение = <tex>I_j[A \rightarrow \alpha B \cdot \beta, j]</tex> по   '''function''' <tex>I_0\mathtt{predict}(D, I_1j, G, ...w)</tex>: '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, I_i] \in D_{j-1}</tex>. '''for''' <tex>(B \rightarrow \eta) \in P <br/tex> <itex>D_{j}</tex> <tex>Шаг 4.\cup</itex> Для каждой ситуации = <tex>[B \rightarrow \cdot \ \eta, j]</tex> ==Корректность алгоритма=={{Теорема|statement = Приведенный алгоритм правильно строит все списки ситуаций. То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_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>a_j\Longrightarrow</tex> — j-й символ в </b><br/>Докажем индукцией по исполнению алгоритма.<br/><u> ''База индукции:'' </u><br/><tex>[S' \rightarrow \cdot S, 0] \omegain D_0 \ </tex>.<br/><u> ''Индукционный переход:'' </u> <br/>Пусть предположение верно для всех списков ситуаций с номерами меньше <tex> j </tex>. Разберемся, включить в результате применения какого правила ситуация <tex>[B A \rightarrow \alpha a_{j} \cdot \beta, i] </tex> попала в <tex>I_jD_{j}</tex>.<br/>Пока можно включить новые ситуации в 1. Включаем по правилу <tex>I_j\mathtt{scan} \ </tex> повторяем шаги 5 и 6.<br/>Это произошло, если <tex> \alpha = \alpha ' a</tex>, <itex>Шаг 5.a = w_{j-1}</itex> Если и <tex>[A \rightarrow \alpha ' \cdot a \beta, i] \in I_jD_{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>[B \rightarrow alpha = \gamma alpha ' a \cdot A Rightarrow^* w_i \beta, k] ldots w_{j-2}w_{j-1} = w_i \in I_ldots w_{ij-1}\ </tex> включить .<br/>Таким образом условия: <tex>[B S' \rightarrow Rightarrow^* w_0 \gamma ldots w_{i-1} A \cdot delta</tex> и <tex>\alpha \Rightarrow^* w_i \beta, k]ldots w_{j-1}</tex> в выполняются. 2. Включаем по правилу <tex>I_j\mathtt{predict} \ </tex>.<br/>По построению: <tex> \alpha = \varepsilon </tex> и <tex>i=j</tex>Шаг 6, что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\exists i' \le i</tex> Для всех и ситуация <tex>[A ' \rightarrow \alpha ' \cdot B A \betadelta ', i'] \in I_jD_i</tex>, для всех из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex> и <tex>\gammaalpha ' \Rightarrow^* w_{i'} \ldots w_{i-1}</tex> таких.<br/>Получаем, что <tex>B S' \rightarrow Rightarrow^* w_0 \gamma ldots w_{i'-1} A' \in Pdelta ''</tex> включить , значит <tex>[B S \Rightarrow^* w_0 \ldots w_{i'-1} \rightarrow alpha' A \cdot delta' \gammadelta '' </tex>, j]следовательно <tex> S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \ldots w_{i-1} A \delta' \delta ''</tex> , в итоге <tex>I_jS' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, что нам и требовалось.<br>

Если <b><tex>\Longleftarrow</tex></b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0 \ldots w_{i-1} A \delta \ </tex> из <tex>[S '</tex> и <tex>w_i \rightarrow ldots w_{j-1}</tex> из <tex>\alpha </tex>. После чего примениминдукцию по длине вывода <tex>w_i \cdot, 0] \in I_nldots w_{j-1}</tex>, то из <tex>\omega \in L(G) alpha</tex>.<br/>Рассмотрим три случая последнего символа <tex>\alpha</tex>:

1. <tex>\alpha =\alpha ' a</tex>, тогда <tex>a =Пример==Рассмотрим грамматику w_{j-1}</tex> и <tex>G\alpha ' \Rightarrow^* w_i \ldots w_{j-2}</tex> с правилами: .<br/>По предположению индукции: <tex>S [A \rightarrow T + S\alpha ' \cdot a \beta, i] \in D_{j-1}</tex> , а отсюда по правилу <brtex> \mathtt{scan}</tex>получаем <tex>S [A \rightarrow T \alpha ' a \cdot \beta, i] \in D_{j}</tex> . 2. <brtex>\alpha = \alpha ' B</tex>, тогда <tex>T \rightarrow F exists i' : \alpha ' \Rightarrow^* w_i \ldots w_{i'-1} \wedge B ' \Rightarrow^* Tw_{i'} \ldots w_{j-1}</tex> .<br/>Тогда имеем <tex>T [A \rightarrow F\alpha ' a \cdot \beta, i] \in D_{j}</tex> . Также можно записать <brtex>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>F B \rightarrow ( S )\eta \wedge \eta \rightarrow w_{i'} \ldots w_{j-1}</tex> .<br/>Применяя индукцию по второму параметру получим <tex>F [B \rightarrow a\eta \cdot, i'] \in D_j \ </tex> , откуда по правилу <brtex> \mathtt{complete}</tex>Построим для строки получаем <tex>[A \rightarrow \omega = (a + a)alpha ' B \cdot \beta, i] \in D_{j}</tex> список разбора.<br>

{| class==Корректность алгоритма=="wikitable"|-!<tex>D_5</tex>|-|{{Теорема||-!Ситуация !! Из правила|-|statement = <tex>[A F \rightarrow \alpha ( S )\cdot \beta, i0] </tex> || 1|-|<tex>[T \in I_{j} rightarrow F \Leftrightarrow \alpha \Rightarrow^cdot * a_{i+1}...a_{j}T, 0]</tex> и || 2|-|<tex> [T \mathcal {9} rightarrow F \gamma cdot , 0]</tex> и || 2|-|<tex> [S \rightarrow T \deltacdot + S, 0]</tex> такие, что || 2|-|<tex>[S \Rightarrow^* rightarrow T \gamma A \deltacdot , 0]</tex> и || 2|-|<tex> [S' \gamma rightarrow S \Rightarrow^* a_1...a_{i}cdot , 0]</tex>|| 2|proof =}|}

Так как <tex>\Rightarrow</tex> <br>Докажем по индукции.<br>База: для любой ситуации из <tex>I_0</tex> <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>[S \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br><br><b>1. Пусть включаем по правилу 4</b><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' = a_1...a_{i} </tex>. Значит <tex> \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} </tex> и при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно. <br><br><b>2. Пусть включаем по правилу 5</b><br>Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k0] \in I_{i}</tex> и <tex> [B \rightarrow \eta \cdot, i] \in I_{j} </tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}, \eta \Rightarrow^* a_{i+1}...a_{j} D_5</tex>, откуда <tex>\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} </tex>. Также по и.п. существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{k} </tex>. Значит при <tex>\gamma = \gamma', \delta = \delta' </tex> для <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> утверждение верно.<br><br><b>3. Пусть включаем по правилу 6</b><br>Тогда то <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] w \in I_{j}</tex>. По и.п. <tex>\alpha' \Rightarrow^* a_{k+1}...a_{i}</tex> и существуют <tex>\gamma'</tex> и <tex>\delta' </tex> такие, что <tex>S \Rightarrow^* \gamma' B \delta', \gamma' = a_1...a_{k} </tex>. Значит при <tex>\gamma = \gamma' \alpha', \delta = \beta \delta' </tex> выполнено <tex> S \Rightarrow^* \gamma A \delta</tex>, значит для <tex>[A \rightarrow \alpha \cdot \beta, i]L(G) </tex> утверждение верно. <br>

<tex>\Leftarrow</tex><br>Для всех наборов <tex>\tau = {\alpha, \beta, \gamma, \delta, A, i , j} </tex> нужно доказать, что если <tex> S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, A \rightarrow \alpha \beta \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}</tex>, то <tex> [A \rightarrow \alpha \cdot B \beta, i] \in I_{j}</tex>.<br>*<b>Рангом набора </b> <tex> \tau </tex> называется <tex> \tau_{1}(\tau) + 2(j + \tau_{2}(\tau) + \tau_{3}(\tau))</tex>, где <tex>\tau_{1}(\tau)</tex> — длина кратчайшего вывода <tex>S \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{2}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{3}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.Докажем утверждение по индукции:<br>База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{1} = \tau_{2} = \tau_{3} = j Источники информации= i = 0</tex>. Значит <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>A = S</tex>, следовательно <tex>S \rightarrow \beta \in P</tex>. Значит по правилу 1 <tex>*[S \rightarrow \cdot \beta, 0] \in I_0</tex>Индукционный переходhttp:Пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верноlpcs. Докажем для набора <tex>\tau</tex>math. Для этого рассмотрим три случая:<br> <br><b>1msu. <tex>\alpha<su/tex> оканчивается терминалом <~sk/b> <br><tex>\alpha = \alpha' a<lehre/tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>a = a_{j}<fivt2013/tex>Earley. Рассмотрим набор <tex>\tau' = \mathcal pdf Алексей Сорокин {f} \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \mathcal {g} </tex>. <tex>A \rightarrow \alpha' a_{j} \beta \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{1}(\tau) = \tau_1(\tau'), \tau_2(\tau) = \tau_2(\tau'), \tau_{3-}(\tau) = \tau_3(\tau')</tex>. Значит по и.п. <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, iАлгоритм Эрли] \in I_{j-1}</tex>, по правилу 4 получаем, что <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>. <br> <br><b> 2. <tex>\alpha</tex> оканчивается нетерминалом </b><br> <tex>\alpha = \alpha' B</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>\mathcal {9} k</tex> такое, что <tex>\alpha' \Rightarrow^*a_{i+1}..Ахо А.a_{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>Теория синтакcического анализа, его ранг меньше <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)</tex> <tex>= \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>М. <br> <br><b>3. <tex>\alpha</tex> является пустой </b><br><tex>\alpha = \varepsilon</tex>, значит <tex>i = j:«Мир», \tau_3(\tau) = 0</tex>1978.<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_{j}</tex>358 — 364.}}

==Литература==[[Категория: Теория формальных языков]]Ахо А., Ульман Д. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.[[Категория: Контекстно-свободные грамматики]][[Категория:«Мир», 1978. — С. 358 — 364.Алгоритмы разбора]]