Изменения

__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> — иначе.

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

'''Ситуации хранятся в множествах <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>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> (где <tex>w_j</tex> — <tex>j</tex>-ый символ строки), то <brtex>[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>(B \rightarrow \eta) \in P <br/tex>, то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}</tex>. === Псевдокод ===Добавим Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>. '''function''' <tex>\mathtt{earley}(G, w)<br/tex>:Добавим в <texfont color=green>I_0// Инициализация </texfont> ситуацию <tex>D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0]\rbrace </tex> '''for''' <tex>i = 1</tex> '''to''' <tex>len(w)<br/tex> <tex>D_i</tex> = <tex>\varnothing </tex> <font color=green>// Вычисление ситуаций </font> '''for'''Построение <tex>I_jj = 0</tex> по '''to''' <tex>I_0len(w)</tex> <tex>\mathtt{scan}(D, j,...G,I_{j-1}w)</tex>. '''while''' <tex>D_j<br/tex>изменяетсяПока в <tex>I_j\mathtt{complete}(D, j, G, w)</tex> можно добавить новые ситуации повторяем шаги 1—3. <tex>\mathtt{predict}(D, j, G, w)<br/tex> <ifont color=green>Шаг 1.// Результат </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>: '''if''' <tex>a_jj</tex> — j-й символ в == <tex>\omega0</tex>, включить '''return''' '''for''' <tex>[B A \rightarrow \alpha a_{j} \cdot a \beta, i] \in D_{j - 1} </tex> в '''if''' <tex>I_ja</tex>.== <tex>w_{j - 1}<br/tex> <tex>D_{j}</tex> <itex>Шаг 2.\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>Шаг 3.\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>.<brtex>'''Завершение.\cup<br/tex>Если = <tex>[S' B \rightarrow S \cdot\ \eta, 0j] \in I_n</tex>, то <tex>\omega \in L(G) </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>\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. Пусть включаем Включаем по правилу 1<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>S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex> и.п. <tex>\alpha' \Rightarrow^* a_w_i \ldots w_{j-2}</tex>,<br/> тогда в силу <tex>a = w_{j-1}</tex> получаем <tex>\alpha = \alpha ' a \Rightarrow^* w_i \ldots w_{j-2}w_{j-1} = w_i \ldots w_{j-1} \ </tex>.<br/>Таким образом условия: <tex>S' \Rightarrow^* w_0 \ldots w_{i+-1}...a_A \delta</tex> и <tex>\alpha \Rightarrow^* w_i \ldots w_{j-1} </tex> выполняются. 2. Включаем по правилу <tex> \mathtt{predict} \ </tex>.<br/>По построению: <tex> \alpha = \varepsilon </tex> и существуют <tex>i=j</tex>, что автоматически влечет второй пункт утверждения.<br/>Кроме того <tex>\gammaexists i'\le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta' , i'] \in D_i</tex> такие, что из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0 \gammaldots w_{i' -1} A ' \delta', '</tex> и <tex> \gammaalpha ' = a_1...a_\Rightarrow^* w_{i'} \ldots w_{i-1} </tex>. Значит <br/>Получаем, что <tex> \alpha = \alphaS' a_{j} \Rightarrow^* a_w_0 \ldots w_{i+'-1}...a_{j} A' \delta ''</tex> и при , значит <tex>S \Rightarrow^* w_0 \gamma = ldots w_{i'-1} \gammaalpha', A \delta = ' \delta'' </tex> для , следовательно <tex>[A S' \Rightarrow^* w_0 \rightarrow ldots w_{i'-1} w_{i'} \alpha ldots w_{i-1} A \cdot delta' \beta, i]delta ''</tex> утверждение верно. , в итоге <brtex>S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta<br/tex>, что нам и требовалось. <b>23. Пусть включаем Включаем по правилу 2<tex> \mathtt{complete} \ </btex>.<br/>Тогда По построению: <tex>\alpha = \alpha' B A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha' \cdot B A' \beta, ki] \in I_D_{i'}</tex> и <tex> \wedge [B A' \rightarrow \eta \cdot, i'] \in I_{j} D_j</tex>. По и.п. <br/>Cледовательно <tex>\alpha= \alpha ' A' \Rightarrow^* a_w_i \ldots w_{k+i'-1}...a_w_{i'}, \eta \Rightarrow^* a_ldots w_{i+1j}...a_= w_i \ldots w_{j-1} </tex>, откуда что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. <b><tex>\Longleftarrow</tex></b><br/>В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0 \ldots w_{i-1} A \alpha = delta \alpha</tex> из <tex>S' B </tex> и <tex>w_i \Rightarrow^*a_ldots w_{k+j-1}</tex> из <tex>\alpha</tex>...a_После чего примениминдукцию по длине вывода <tex>w_i \ldots w_{j-1} </tex>. Также по и.п. существуют из <tex>\gamma'alpha</tex> и .<br/>Рассмотрим три случая последнего символа <tex>\delta' alpha</tex> такие, что : 1. <tex>S' \Rightarrow^* alpha = \gamma' A \deltaalpha 'a</tex>, \gamma' тогда <tex>a = a_1...a_w_{kj-1} </tex>. Значит при и <tex>\gamma = \gammaalpha ', \delta = Rightarrow^* w_i \delta' ldots w_{j-2}</tex> для .<br/>По предположению индукции: <tex>[A \rightarrow \alpha ' \cdot a \beta, i]\in D_{j-1}</tex> утверждение верно.<br><br><b>3. Пусть включаем , а отсюда по правилу 3</btex>\mathtt{scan}<br/tex>Тогда получаем <tex>\alpha = \varepsilon, i = j, [B A \rightarrow \alpha' a \cdot A \beta, ki] \in I_D_{j}</tex>. По и.п 2. <tex>\alpha = \alpha ' B</tex>, тогда <tex>\exists i' : \alpha' \Rightarrow^* a_w_i \ldots w_{k+i'-1}...a_\wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}</tex> и существуют .<br/>Тогда имеем <tex>[A \rightarrow \gammaalpha '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 \gammaldots w_{i' -1}B \beta \delta'</tex>, а также <tex>B \rightarrow \eta \wedge \eta \gammarightarrow w_{i' } \Rightarrow^* a_1...a_ldots w_{kj-1} </tex>. Значит при <br/>Применяя индукцию по второму параметру получим <tex>[B \gamma = rightarrow \gamma' eta \alphacdot, i', ] \delta = \beta in D_j \delta' </tex> выполнено , откуда по правилу <tex> S' \Rightarrow^* \gamma A \deltamathtt{complete}</tex>, значит для получаем <tex>[A \rightarrow \alpha ' B \cdot \beta, i]\in D_{j}</tex> утверждение верно. <br>

Рассмотрим грамматику Построим список разбора для строки <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_0D_1</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[S' F \rightarrow ( \cdot S), 0]</tex> — из инициализации <br>|| 1|-|<tex>[S \rightarrow \cdot T + S, 01]</tex> — из правила || 3 <br>|-|<tex>[S \rightarrow \cdot T, 01]</tex> — из правила || 3 <br>|-|<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>[F \rightarrow \cdot a, 01]</tex> — из правила || 3 <br>|}|}

<b>{| class="wikitable"|-!<tex>I_1D_2</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow ( a \cdot S ), 01]</tex> — из правила || 1 <br>|-|<tex>[S T \rightarrow F \cdot * T + S, 1]</tex> — из правила 3 <br>|| 2<tex>[S \rightarrow \cdot T, 1]</tex> — из правила 3 <br>|-|<tex>[T \rightarrow F \cdot F * T, 1]</tex> — из правила 3 <br>|| 2|-|<tex>[T S \rightarrow T \cdot F, 1]</tex> — из правила 3 <br>|| 2|-|<tex>[F S \rightarrow T \cdot ( + S ), 1]</tex> — из правила 3 <br>|| 2|-|<tex>[F \rightarrow ( S \cdot a), 10]</tex> — из правила 3 <br>|| 2|}|}

{| 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> — из правила 1 <br>|| 3|-|<tex>[T S \rightarrow F \cdot * T, 13]</tex> — из правила 2 <br>|| 3|-|<tex>[T \rightarrow F \cdot F * T, 13]</tex> — из правила 2<br>|| 3|-|<tex>[S T \rightarrow T \cdot F, 13]</tex> — из правила 2 <br>|| 3|-|<tex>[S F \rightarrow T \cdot + ( S), 13]</tex> — из правила 2 <br>|| 3|-|<tex>[F \rightarrow ( S \cdot )a, 03]</tex> — из правила 2 <br>|| 3|}|}

<b>{| class="wikitable"|-!<tex>I_3D_4</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[S F \rightarrow T + a \cdot S, 13]</tex> — из правила || 1 <br>|-|<tex>[S T \rightarrow F \cdot * T + S, 3]</tex> — из правила 3 <br>|| 2|-|<tex>[S T \rightarrow F \cdot T, 3]</tex> — из правила 3<br>|| 2|-|<tex>[T S \rightarrow T \cdot F * T+ S, 3]</tex> — из правила 3 <br>|| 2|-|<tex>[T S \rightarrow T \cdot F, 3]</tex> — из правила 3 <br>|| 2|-|<tex>[F S \rightarrow T + S \cdot ( S ), 31]</tex> — из правила 3 <br>|| 2|-|<tex>[F \rightarrow ( S \cdot a), 30]</tex> — из правила 3 <br>|| 2|}|}

<b>{| class="wikitable"|-!<tex>I_4D_5</tex></b> <br>|-|{||-!Ситуация !! Из правила|-|<tex>[F \rightarrow a ( S )\cdot , 30]</tex> — из правила || 1 <br>|-|<tex>[T \rightarrow F \cdot * T, 30]</tex> — из правила || 2 <br>|-|<tex>[T \rightarrow F \cdot , 30]</tex> — из правила || 2<br>|-|<tex>[S \rightarrow T \cdot + S, 30]</tex> — из правила || 2 <br>|-|<tex>[S \rightarrow T \cdot , 30]</tex> — из правила || 2 <br>|-|<tex>[S ' \rightarrow T + S \cdot , 10]</tex> — из правила || 2 <br><tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 2 <br>|}|}

<b><tex>I_5</tex></b> <br>Так как <tex>[F S' \rightarrow ( S )\cdot , 0]</tex> — из правила 1 <br><tex>[T \rightarrow F \cdot * T, 0]in D_5</tex> — из правила 2 <br><tex>[T \rightarrow F \cdot , 0]то </tex> — из правила 2<br><tex>[S w \rightarrow T \cdot + S, 0]</tex> — из правила 2 <br><tex>[S \rightarrow T \cdot , 0]</tex> — из правила 2 <br><tex>[S' \rightarrow S \cdot , 0]in L(G) </tex> — из правила 2 .<br>

Так как <tex>==Источники информации==*[S' \rightarrow S \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.Алгоритмы разбора]]