Изменения

Пусть <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>

*Необходимость <br>Докажем по индукции.<brb>База: для любой ситуации из <tex>I_0\Longrightarrow</tex> <tex/b>\alpha \Rightarrow^* \varepsilon <br/tex> и <tex>S \Rightarrow^* \gamma A \delta Докажем индукцией по исполнению алгоритма.<br/tex> при <texu>\gamma = \varepsilon ''База индукции:'' </texu>.<br/>Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}[S' \rightarrow \cdot S, i 0] \in D_0 \leqslant j </tex>. Пусть включаем <texbr/><u>[A \rightarrow \alpha \cdot \beta, i] ''Индукционный переход:'' </texu> в <tex>I_{j}<br/tex>. Рассмотрим три случая:Пусть предположение верно для всех списков ситуаций с номерами меньше <brtex>*Пусть включаем по правилу 4j <br/tex>Тогда . Разберемся, в результате применения какого правила ситуация <tex>\alpha = \alpha' a_{j} , [[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_</tex> попала в <tex>D_{j-1}</tex><br/> 1. По и.п. Включаем по правилу <tex>\alpha' \Rightarrow^* a_mathtt{i+1scan}\ </tex>...a_{j-1} <<br/tex>и существуют Это произошло, если <tex>\gammaalpha = \alpha 'a</tex> и , <tex>\delta' a = w_{j-1}</tex> такие, что и <tex>S [A \Rightarrow^* rightarrow \gammaalpha ' A \delta'cdot a \beta, i] \gamma' = a_1...a_{iin D_{j-1} </tex>. Значит <br/>По предположению индукции <tex> \alpha = \alphaS' a_{j} \Rightarrow^* a_w_0 \ldots w_{i+-1}...a_{j}A \delta</tex> и при <tex>\gamma = \gammaalpha', \delta = Rightarrow^* w_i \delta' ldots w_{j-2}</tex> для ,<br/> тогда в силу <tex>[A \rightarrow \alpha \cdot \beta, i]a = w_{j-1}</tex> утверждение верно.*Пусть включаем по правилу 5<br>Тогда получаем <tex>\alpha = \alpha' B , [A a \rightarrow Rightarrow^* w_i \alpha' \cdot B ldots w_{j-2}w_{j-1} = w_i \beta, k] \in I_ldots w_{ij-1}\ </tex> и .<texbr/> [B Таким образом условия: <tex>S' \rightarrow Rightarrow^* w_0 \eta \cdot, ldots w_{i] -1} A \in I_{j} delta</tex>. По и.п. и <tex>\alpha' \Rightarrow^* a_w_i \ldots w_{k+j-1}</tex> выполняются. 2..a_Включаем по правилу <tex> \mathtt{ipredict}, \eta \Rightarrow^* a_{i+1}</tex>...a_{j} <br/tex>, откуда По построению: <tex>\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} <varepsilon </tex>. Также по и.п. существуют <tex>\gamma'i=j</tex> и , что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\deltaexists i' \le i</tex> такие, что и ситуация <tex>S [A' \Rightarrow^* rightarrow \gammaalpha ' \cdot A \delta', i'] \gamma' = a_1...a_{k} in D_i</tex>. Значит при , из чего по предположению индукции следует <tex>S' \gamma = Rightarrow^* w_0 \gammaldots w_{i'-1} A', \delta = \delta'' </tex> для и <tex>[A \rightarrow \alpha ' \cdot Rightarrow^* w_{i'} \beta, ldots w_{i]-1}</tex> утверждение верно.*Пусть включаем по правилу 6<br/>Тогда Получаем, что <tex>S' \alpha = Rightarrow^* w_0 \varepsilon, ldots w_{i = j, [B '-1} A' \rightarrow \alphadelta '' \cdot A \beta, k] \in I_{j}</tex>. По и.п. , значит <tex>\alpha' S \Rightarrow^* a_w_0 \ldots w_{k+i'-1}...a_{i}</tex> и существуют <tex>\gammaalpha' A \delta'</tex> и <tex>\delta'' </tex> такие, что следовательно <tex>S ' \Rightarrow^* w_0 \gammaldots w_{i' B \delta-1} w_{i', } \gamma' = a_1...a_ldots w_{ki-1} A \delta' \delta ''</tex>. Значит при , в итоге <tex>\gamma = \gammaS' \alpha', Rightarrow^* w_0 \delta = \beta ldots w_{i-1} A \delta' </tex> выполнено , что нам и требовалось. 3. Включаем по правилу <tex> S \Rightarrow^* mathtt{complete} \gamma A \delta</tex>, значит для .<br/>По построению: <tex>[A \rightarrow alpha = \alpha \cdot \beta, i]' A' </tex> утверждение верно.*ДостаточностьДля всех наборов и <tex>\tau = {\alphaexists i', \beta, delta : [A \gamma, rightarrow \delta, alpha ' \cdot A' \beta, i , j] \in D_{i'} </tex> нужно доказать, что если <tex> S \Rightarrow^* wedge [A' \rightarrow \eta \gamma A \deltacdot, i'] \gamma \Rightarrow^* a_1in D_j</tex>...a_{i}, A \rightarrow <br/>Cледовательно <tex>\alpha \beta \in P, = \alpha ' A' \Rightarrow^* a_w_i \ldots w_{i+'-1}...aw_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, то <tex> [A \rightarrow \alpha \cdot B \betaчто дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, i] \in I_{j}</tex>все хорошо. <brb>*Рангом набора <tex> \tau Longleftarrow</tex> называется </b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex> w_0 \tau_ldots w_{i-1}(A \tau) + 2(j + delta \tau_{2}(\tau) + \tau_{3}(\tau))</tex>, где из <tex>S'</tex> и <tex>w_i \tau_ldots w_{j-1}(\tau)</tex> — длина кратчайшего вывода из <tex>S \Rightarrow^* \gamma A \delta alpha</tex>, . После чего примениминдукцию по длине вывода <tex>w_i \tau_ldots w_{2j-1}(\tau)</tex> — длина кратчайшего вывода из <tex>\gamma \Rightarrow^* a_1..alpha</tex>.a_{i}<br/tex>, Рассмотрим три случая последнего символа <tex>\tau_{3}(\tau)alpha</tex> — длина кратчайшего вывода : 1. <tex>\alpha = \Rightarrow^* a_{i+1}...a_{j}alpha ' a</tex>.Докажем утверждение по индукции:<br>База: если ранг , тогда <tex>\taua = w_{j-1}</tex> равен 0, то и <tex>\tau_{1} = alpha ' \tau_Rightarrow^* w_i \ldots w_{j-2} = \tau_{3} = j = i = 0</tex>. Значит <br/>По предположению индукции: <tex>[A \rightarrow \alpha = ' \gamma = cdot a \delta = beta, i] \varepsilon in D_{j-1}</tex>, а отсюда по правилу <tex>A = S\mathtt{scan}</tex>, следовательно получаем <tex>S [A \rightarrow \alpha ' a \cdot \beta , i] \in PD_{j}</tex>. Значит по правилу 1  2. <tex>[S \rightarrow alpha = \cdot \beta, 0] \in I_0alpha ' B</tex>Индукционный переход:<br>Пусть ранг , тогда <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>exists i' : \tau</tex>. Для этого рассмотрим три случая:alpha ' \Rightarrow^*<tex>w_i \ldots w_{i'-1} \alpha</tex> оканчивается терминалом<br><tex>wedge B ' \alpha = Rightarrow^* w_{i'} \alpha' aldots w_{j-1}</tex>. <texbr/>Тогда имеем <tex>[A \rightarrow \alpha ' a \Rightarrow^*a_cdot \beta, i] \in D_{i+1j}...a_{j}<</tex>, значит . Также можно записать <tex>a = a_S' \Rightarrow^* w_0 \ldots w_{ji-1}A \delta</tex>. Рассмотрим набор , как <tex>S' \tau' = Rightarrow^* w_0 \mathcal ldots w_{fi-1} w_i \alphaldots w_{i', a_{j-1} B \beta, \gamma, \delta</tex>, A, а также <tex>B \rightarrow \eta \wedge \eta \rightarrow w_{i, '} \ldots w_{j-1 \mathcal {g} </tex>. <br/>Применяя индукцию по второму параметру получим <tex>A [B \rightarrow \alphaeta \cdot, i' a_{j} ] \beta in D_j \in P</tex>, следовательно ранг откуда по правилу <tex>\tau'mathtt{complete}</tex> равен получаем <tex>r - 2[A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}</tex>, так как . 3. <tex>\tau_{1}(\tau) alpha = \tau_1(\tau')varepsilon </tex>, \tau_2(\tau) тогда <tex>i= \tau_2(\tau'), \tau_{3}(\tau) = \tau_3(\tau')j</tex>. Значит по и.п. <br/> Тогда либо <tex>[i = 0 \wedge A = S \rightarrow wedge \alpha' delta = \cdot a_{j} \betavarepsilon</tex>, что доказывает базу индукции, i] \in I_{j-1}<br/tex>, по правилу 4 получаем, что либо вывод можно записать в виде <tex>[A S' \rightarrow Rightarrow^* w_0 \alpha ldots w{i'-1}w_{i'} \cdot \beta, ldots w{i] <-1} A \delta ' \delta '' = w_0 \ldots w_{i-1} A \delta \ </tex> будет добавлена в для некоторого правила <tex>I_(A' \rightarrow w_{ji'} \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> ==См. также==* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] ==Источники информации==*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]* Ахо А.Ахо, Дж. УльманД. {{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический Синтаксический анализ.Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364. [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Алгоритмы разбора]]