390
правок
Изменения
м
==Определения==
<b>Cписком ситуаций</b> <tex>I_j</tex> для входной цепочки Ситуации хранятся в множествах <tex>D_0, \omega = a_1 a_2 ... a_n</tex>ldots , где <tex>0 \leqslant j \leqslant D_{n-1}</tex> называется множество , называемых '''списками ситуаций '''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i] </tex> таких, что в <tex>\alpha \Rightarrow^* a_{i+1} ... a_jj</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>w_i \gamma \alpha </tex> выводит часть <tex>\omega</tex> c первого по <tex>ldots w_{j-1})</tex>-й символ.
<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>
*<i>Рангом набора </i> <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>
Индукционный переход:
Пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:<br> <br>
<b>1. <tex>\alpha</tex> оканчивается терминалом </b> <br>
<tex>\alpha = \alpha' a</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>a = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \mathcal {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>, его ранг меньше <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>.<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>.
Рассмотрим грамматику Построим список разбора для строки <tex>Gw = (a + a)</tex> с в грамматике со следующими правилами: <br>* <tex>S \rightarrow T + S</tex> <br>* <tex>S \rightarrow T </tex> <br>* <tex>T \rightarrow F * T</tex> * <brtex>T \rightarrow F</tex>* <tex>T F \rightarrow ( S )</tex>* <tex>F\rightarrow a</tex> {||-| {| class="wikitable"|-!<tex>D_0</tex>|-|{||-!Ситуация !! Из правила|-|<tex>[S' \rightarrow \cdot S, 0]<br/tex>|| 0|-|<tex>F [S \rightarrow ( \cdot T + S ), 0]</tex> || 3|-|<tex>[S \rightarrow \cdot T, 0]<br/tex>|| 3|-|<tex>F [T \rightarrow a\cdot F * T, 0]</tex> || 3|-|<brtex>[T \rightarrow \cdot F, 0]</tex> || 3Построим для строки |-|<tex>[F \omega = rightarrow \cdot (a + aS ), 0]</tex> список разбора.|| 3|-|<tex>[F \rightarrow \cdot a, 0]<br/tex>|| 3|}|}
<b>{| class="wikitable"|-!<tex>I_1D_2</tex></b> <br><tex>[F \rightarrow ( \cdot S ), 0]</tex> — из |-|{||-!Ситуация !! Из правила 4 <br>|-|<tex>[S F \rightarrow a \cdot T + S, 1]</tex> — из правила 6 <br>|| 1|-|<tex>[S T \rightarrow F \cdot * T, 1]</tex> — из правила 6 <br>|| 2|-|<tex>[T \rightarrow F \cdot F * T, 1]</tex> — из правила 6 <br>|| 2|-|<tex>[T S \rightarrow T \cdot F, 1]</tex> — из правила 6 <br>|| 2|-|<tex>[F S \rightarrow T \cdot ( + S ), 1]</tex> — из правила 6 <br>|| 2|-|<tex>[F \rightarrow ( S \cdot a), 10]</tex> — из правила 6 <br>|| 2|}|}
<b>{| class="wikitable"|-!<tex>I_3D_4</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[S F \rightarrow T + a \cdot S, 13]</tex> — из правила 4 <br>|| 1|-|<tex>[S T \rightarrow F \cdot * T + S, 3]</tex> — из правила 6 <br>|| 2|-|<tex>[S T \rightarrow F \cdot T, 3]</tex> — из правила 6<br>|| 2|-|<tex>[T S \rightarrow T \cdot F * T+ S, 3]</tex> — из правила 6 <br>|| 2|-|<tex>[T S \rightarrow T \cdot F, 3]</tex> — из правила 6 <br>|| 2|-|<tex>[F S \rightarrow T + S \cdot ( S ), 31]</tex> — из правила 6 <br>|| 2|-|<tex>[F \rightarrow ( S \cdot a), 30]</tex> — из правила 6 <br>|| 2|}|}
<b>{| class="wikitable"|-!<tex>I_4D_5</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow a ( S )\cdot , 30]</tex> — из правила 4 <br>|| 1|-|<tex>[T \rightarrow F \cdot * T, 30]</tex> — из правила 5 <br>|| 2|-|<tex>[T \rightarrow F \cdot , 30]</tex> — из правила 5<br>|| 2|-|<tex>[S \rightarrow T \cdot + S, 30]</tex> — из правила 5 <br>|| 2|-|<tex>[S \rightarrow T \cdot , 30]</tex> — из правила 5 <br>|| 2|-|<tex>[S ' \rightarrow T + S \cdot , 10]</tex> — из правила 5 <br>|| 2|}<tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 5 <br>|}
<b><tex>I_5</tex></b> <br>Так как <tex>[F S' \rightarrow ( S )\cdot , 0]</tex> — из правила 4 <br><tex>[T \rightarrow F \cdot * T, 0]</tex> — из правила 5 <br><tex>[T \rightarrow F \cdot , 0]in D_5</tex> — из правила 5<br><tex>[S \rightarrow T \cdot + S, 0]</tex> — из правила 5 <br>то <tex>[S w \rightarrow T \cdot , 0]in L(G) </tex> — из правила 5 .<br>
Так как <tex>==Источники информации==*[S \rightarrow T \cdot http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]* Ахо А., 0] \in I_5</tex>Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», то <tex>\omega \in L(G) </tex>1978. С. 358 — 364.<br>
==Литература==[[Категория: Теория формальных языков]]''Ахо А., Ульман Д.'' Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.[[Категория: Контекстно-свободные грамматики]][[Категория:«Мир», 1978. С. 358 — 364.Алгоритмы разбора]]
Исправил многоточия ещё
__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> называется <b>ситуацией</b>, относящейся к цепочке <tex>\omega</tex>, если где <tex>A \rightarrow \alpha \beta </tex> {{---}} — правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex>\omegacdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \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>.
}}
==Алгоритм Эрли==Добавим вспомогательный нетерминал Чтобы воспользоваться леммой, необходимо найти <tex>S'D_n</tex> и правило для <tex>S' \rightarrow Sw</tex>.Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <brtex>D_j</tex>используются <tex>D_0, \ldots, D_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент). Алгоритм основывается на следующих трёх правилах:Построим список разбора для # Если <tex>[A \omegarightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex>.(где <brtex>'''Инициализация.w_j<br/tex>Добавим в — <tex>I_0j</tex> ситуацию -ый символ строки), то <tex>[S' A \rightarrow \alpha w_{j} \cdot S\beta, 0i]\in D_j</tex>.# Если <brtex>'''Продолжение.[B \rightarrow \eta \ \cdot, i] \in D_j<br/tex>Пока в и <tex>I_j[A \rightarrow \alpha \cdot B \beta, k] \in D_i</tex> можно добавить новые ситуации повторяем шаги 1—3., то <tex>[A \rightarrow \alpha B \cdot \beta, k] \in D_j<br/tex>.# Если <tex>[A \rightarrow \alpha \ \cdot B \beta, i] \in D_{j} </tex>Шаг 1.и <tex>(B \rightarrow \eta) \in P </itex> Для каждой ситуации , то <tex>[B \rightarrow \alpha cdot \cdot a_{j} \betaeta, ij] \in I_D_{j-1}</tex>, где . === Псевдокод ===Для простоты добавим новый стартовый вспомогательный нетерминал <tex>a_jS'</tex> — j-й символ в и правило <tex>(S' \omegarightarrow S)</tex>. '''function''' <tex>\mathtt{earley}(G, включить w)</tex>: <font color=green>// Инициализация </font> <tex> D_{0} = \lbrace [B S' \rightarrow \alpha a_{j} \cdot \betaS, i0] \rbrace </tex> в '''for''' <tex>I_ji = 1</tex>.'''to''' <tex>len(w)<br/tex>Пока можно включить новые ситуации в <tex>D_i</tex> = <tex>I_j\varnothing </tex> повторяем шаги 5 и 6. <font color=green>// Вычисление ситуаций <br/font> '''for''' <itex>j = 0</tex> '''to''' <tex>Шаг 2.len(w)</itex> Если <tex>[A \rightarrow mathtt{scan}(D, j, G, w)</tex> '''while''' <tex>D_j</tex> изменяется <tex>\alpha mathtt{complete}(D, j, G, w)</tex> <tex>\cdot mathtt{predict}(D, j, G, i] \in I_jw)</tex>, то для каждой ситуации <font color=green>// Результат </font> '''if''' <tex>[B S' \rightarrow S \gamma \cdot A \beta, k0] \in I_D_{ilen(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>[B A \rightarrow \gamma A alpha \cdot a \beta, ki]\in D_{j - 1} </tex> в '''if''' <tex>I_ja</tex>.== <tex>w_{j - 1}<br/tex> <tex>D_{j}<i/tex> <tex>Шаг 3.\cup</itex> Для всех = <tex>[A \rightarrow \alpha a \cdot B \beta, i] \in I_j</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, j]\in D_{i} </tex> <tex>D_{j}</tex> в <tex>I_j\cup</tex>.= <tex>[A \rightarrow \alpha B \cdot \beta, j]<br/tex> '''Завершение.function''' <tex>\mathtt{predict}(D, j, G, w)<br/tex>:Если '''for''' <tex>[S' A \rightarrow S \alpha \cdotB \beta, 0i] \in I_nD_{j} </tex>, то '''for''' <tex>(B \omega rightarrow \eta) \in L(G) P </tex> <tex>D_{j}</tex> <tex>\cup</tex>.= <tex>[B \rightarrow \cdot \ \eta, j]<br/tex>
==Корректность алгоритма==
{{Теорема
|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>.
|proof =
<b><tex>\RightarrowLongrightarrow</tex></b> <br/>Докажем индукцией по индукцииисполнению алгоритма.<br/><u> ''База индукции: для любой ситуации из '' <tex/u>I_0<br/tex> <tex>[S' \rightarrow \alpha cdot S, 0] \Rightarrow^* in D_0 \varepsilon </tex> и <tex>S \Rightarrow^* \gamma A \delta .<br/tex> при <texu>\gamma = \varepsilon ''Индукционный переход:'' </texu>.<br/>Индукционный переход (и.п.): пусть Пусть предположение верно для всех списков ситуаций из списков с номерами меньше <tex> I_{i}, i \leqslant j </tex>. Пусть включаем Разберемся, в результате применения какого правила ситуация <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>I_D_{j}</tex>. Рассмотрим три случая:<br><br/><b>1. Пусть включаем Включаем по правилу 4<tex> \mathtt{scan} \ </btex>.<br/>Тогда Это произошло, если <tex>\alpha = \alpha' a_a</tex>, <tex>a = w_{j-1} , </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> и <tex>\delta' ,<br/tex> такие, что тогда в силу <tex>S \Rightarrow^* \gamma' A \delta', \gamma' a = a_1...a_w_{ij-1} </tex>. Значит получаем <tex> \alpha = \alpha' a_{j} a \Rightarrow^* a_w_i \ldots w_{j-2}w_{i+j-1}...a_= w_i \ldots w_{j-1} \ </tex> и при .<br/>Таким образом условия: <tex>S' \gamma = Rightarrow^* w_0 \gamma', \delta = ldots w_{i-1} A \delta' </tex> для и <tex>[A \rightarrow \alpha \cdot Rightarrow^* w_i \beta, i]ldots w_{j-1}</tex> утверждение верновыполняются. <br><br><b>2. Пусть включаем Включаем по правилу 5<tex> \mathtt{predict} \ </btex>.<br/>Тогда По построению: <tex>\alpha = \alpha' B varepsilon </tex> и <tex>i=j</tex>, [A что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\rightarrow \alphaexists i' \cdot B \beta, k] \in I_{le i}</tex> и ситуация <tex> [B A' \rightarrow \eta alpha ' \cdotA \delta ', i'] \in I_{j} D_i</tex>. По и.п. , из чего по предположению индукции следует <tex>\alphaS' \Rightarrow^* a_{k+1}...a_{i}, \eta w_0 \Rightarrow^* a_ldots w_{i+'-1}...a_{j} A' \delta ''</tex>, откуда и <tex>\alpha = \alpha' B \Rightarrow^*a_w_{k+1i'}...a_\ldots w_{ji-1} </tex>. Также по и.п. существуют <tex>\gamma'<br/tex> и Получаем, что <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta'' </tex> такие, что значит <tex>S \Rightarrow^* w_0 \ldots w_{i'-1} \gammaalpha' A \delta', \gammadelta '' = a_1...a_{k} </tex>. Значит при , следовательно <tex>S' \gamma = Rightarrow^* w_0 \gammaldots w_{i'-1} w_{i', } \ldots w_{i-1} A \delta = ' \delta' '</tex> для , в итоге <tex>[A S' \rightarrow Rightarrow^* w_0 \alpha ldots w_{i-1} A \cdot \beta, i]delta</tex> утверждение верно, что нам и требовалось.<br><br><b>3. Пусть включаем Включаем по правилу 6<tex> \mathtt{complete} \ </btex>.<br/>Тогда По построению: <tex>\alpha = \varepsilon, alpha ' A' </tex> и <tex>\exists i = j', \delta : [B A \rightarrow \alpha' \cdot A ' \beta, ki] \in I_D_{ji'}\wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>. По и.п. <br/>Cледовательно <tex>\alpha = \alpha' A' \Rightarrow^* a_w_i \ldots w_{k+i'-1}...a_w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex> и существуют , что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. <b><tex>\gamma'Longleftarrow</tex> и </b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0 \ldots w_{i-1} A \delta' \ </tex> такие, что из <tex>S \Rightarrow^* \gamma' B \delta', </tex> и <tex>w_i \gamma' = a_1...a_ldots w_{kj-1} </tex>. Значит при из <tex>\gamma = \gamma' \alpha', \delta = \beta \delta' </tex> выполнено . После чего примениминдукцию по длине вывода <tex> S w_i \Rightarrow^* \gamma A \deltaldots w_{j-1}</tex>, значит для из <tex>[A \rightarrow \alpha \cdot \beta, i]</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>, что и требовалось.
}}
==Пример==
||
{| class="wikitable"|-!<btex>D_1</tex>I_0|-|{||-!Ситуация !! Из правила|-|</tex>[F \rightarrow ( \cdot S ), 0]</b> <brtex>|| 1|-|<tex>[S \rightarrow \cdot T + S, 01]</tex> — из правила 1 <br>|| 3|-|<tex>[S \rightarrow \cdot T, 01]</tex> — из правила 1 <br>|| 3|-|<tex>[T \rightarrow \cdot F * T, 01]</tex> — из правила || 3 <br>|-|<tex>[T \rightarrow \cdot F, 01]</tex> — из правила || 3 <br>|-|<tex>[F \rightarrow \cdot ( S ), 01]</tex> — из правила || 3 <br>|-|<tex>[S F \rightarrow \cdot a, 01]</tex> — из правила || 3 <br>|}|}
||
|-
|
{| class="wikitable"|-!<btex>D_3</tex>I_2|-|{||-!Ситуация !! Из правила|-|</tex>[S \rightarrow T + \cdot S, 1]</b> <brtex>|| 1|-|<tex>[F S \rightarrow a \cdotT + S, 13]</tex> — из правила 4 <br>|| 3|-|<tex>[T S \rightarrow F \cdot * T, 13]</tex> — из правила 5 <br>|| 3|-|<tex>[T \rightarrow F \cdot F * T, 13]</tex> — из правила 5<br>|| 3|-|<tex>[S T \rightarrow T \cdot F, 13]</tex> — из правила 5 <br>|| 3|-|<tex>[S F \rightarrow T \cdot + ( S), 13]</tex> — из правила 5 <br>|| 3|-|<tex>[F \rightarrow ( S \cdot )a, 03]</tex> — из правила 5 <br>|| 3|}|}
||
||
|}
==См. также==
* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
