Алгоритм Эрли — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 6 участников)
Строка 1: Строка 1:
'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>\omega</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
+
__TOC__
 +
'''Алгоритм Эрли''' позволяет определить, выводится ли данное слово <tex>w</tex> в данной [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободной]] грамматике <tex>G</tex>.
  
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>\omega</tex>.<br/>
+
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex> и слово <tex>w</tex>.<br/>
'''Выход:''' <tex>true</tex>, если <tex>\omega</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
+
'''Выход:''' <tex>true</tex>, если <tex>w</tex> выводится в <tex>G</tex>; <tex>false</tex> — иначе.
  
==Определения==
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
+
Пусть <tex>G = \langle N, \Sigma, P, S \rangle</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная]] грамматика и <tex>w = w_0 w_1 \ldots 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>\omega</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>w</tex>, называется '''ситуацией''', относящейся к цепочке <tex>w</tex>, где '''<tex> \cdot </tex>''' {{---}} вспомогательный символ, который не явлется терминалом или нетерминалом ( <tex> \cdot \notin \Sigma \cup N</tex>).
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<b>Cписком ситуаций</b> <tex>I_j</tex> для входной цепочки <tex>\omega = a_1 a_2 ... a_n</tex>, где <tex>0 \leqslant j \leqslant n</tex> называется множество ситуаций <tex>[A \rightarrow \alpha \cdot \beta , i] </tex> таких, что <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>, и для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex>. То есть <tex>\gamma \alpha </tex> выводит часть <tex>\omega</tex> c первого по <tex>j</tex>-й символ.
+
Ситуации хранятся в множествах <tex>D_0, \ldots ,D_{n-1}</tex>, называемых '''списками ситуаций'''. Причем наличие ситуации <tex>[A \rightarrow \alpha \cdot \beta , i]</tex> в <tex>j</tex>-м списке ситуаций <tex>D_j</tex> равносильно тому, что
 +
<tex>\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>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Последовательность списков ситуаций <tex>I_0, I_1, .., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>\omega</tex>.
+
Последовательность списков ситуаций <tex>D_0, D_1, \ldots, D_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>.
 
}}
 
}}
  
==Алгоритм Эрли==
+
== Алгоритм Эрли ==
Добавим вспомогательный нетерминал <tex>S'</tex> и правило <tex>S' \rightarrow S</tex>.<br>
+
Чтобы воспользоваться леммой, необходимо найти <tex>D_n</tex> для <tex>w</tex>. Алгоритм Эрли является [[Динамическое программирование|динамическим алгоритмом]]: он последовательно строит список разбора, причём при построении <tex>D_j</tex> используются <tex>D_0, \ldots, D_{j}</tex> (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
Построим список разбора для <tex>\omega</tex>.<br>
+
 
'''Инициализация.<br>
+
Алгоритм основывается на следующих трёх правилах:
Добавим в <tex>I_0</tex> ситуацию <tex>[S' \rightarrow \cdot S, 0]</tex><br>
+
# Если <tex>[A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}</tex> (где <tex>w_j</tex> <tex>j</tex>-ый символ строки), то <tex>[A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j</tex>.
'''Продолжение.<br>
+
# Если <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>I_j</tex> можно добавить новые ситуации повторяем шаги 1—3.<br>
+
# Если <tex>[A \rightarrow \alpha \ \cdot B \beta, i] \in D_{j} </tex> и <tex>(B \rightarrow \eta) \in P </tex>, то <tex>[B \rightarrow \cdot \ \eta, j] \in D_{j}</tex>.
<i>Шаг 1.</i> Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>, где <tex>a_j</tex> — j-й символ в <tex>\omega</tex>, включить <tex>[B \rightarrow \alpha a_{j} \cdot \beta, i] </tex> в <tex>I_j</tex>.<br>
+
 
Пока можно включить новые ситуации в <tex>I_j</tex> повторяем шаги 5 и 6.<br>
+
=== Псевдокод ===
<i>Шаг 2.</i> Если <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>, то для каждой ситуации <tex>[B \rightarrow \gamma \cdot A \beta, k] \in I_{i}</tex> включить <tex>[B \rightarrow \gamma A \cdot \beta, k]</tex> в <tex>I_j</tex>.<br>
+
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
<i>Шаг 3.</i> Для всех <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>, для всех <tex>\gamma</tex> таких, что <tex>B \rightarrow \gamma \in P</tex> включить <tex>[B \rightarrow \cdot \gamma, j]</tex> в <tex>I_j</tex>.<br>
+
'''Завершение.<br>
+
'''function''' <tex>\mathtt{earley}(G, w)</tex>:
Если <tex>[S' \rightarrow S \cdot, 0] \in I_n</tex>, то <tex>\omega \in L(G) </tex>.<br>
+
  <font color=green>// Инициализация </font>
 +
  <tex> D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0] \rbrace </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>
 +
      <tex>\mathtt{predict}(D, j, G, w)</tex>
 +
  <font color=green>// Результат </font>
 +
  '''if'''  <tex>[S' \rightarrow S \ \cdot, 0] \in D_{len(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>[A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} </tex>
 +
    '''if''' <tex>a</tex> == <tex>w_{j - 1}</tex>
 +
      <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha a \cdot \beta, i]</tex>
 +
 
 +
'''function''' <tex>\mathtt{complete}(D, j, G, w)</tex>:
 +
  '''for''' <tex>[B \rightarrow \eta \ \cdot, i] \in D_{j} </tex>
 +
    '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, j] \in D_{i} </tex>
 +
      <tex>D_{j}</tex> <tex> \cup</tex>= <tex>[A \rightarrow \alpha B \cdot \beta, j]</tex>
 +
 
 +
'''function''' <tex>\mathtt{predict}(D, j, G, w)</tex>:
 +
  '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, i] \in D_{j} </tex>
 +
    '''for''' <tex>(B \rightarrow \eta) \in P </tex>
 +
      <tex>D_{j}</tex> <tex>\cup</tex>= <tex>[B \rightarrow \cdot \ \eta, j]</tex>
  
 
==Корректность алгоритма==
 
==Корректность алгоритма==
 
{{Теорема
 
{{Теорема
|statement = <tex>[A \rightarrow \alpha \cdot \beta, i] \in I_{j} \Leftrightarrow \alpha \Rightarrow^* a_{i+1}...a_{j}</tex> и <tex> \mathcal {9} \gamma </tex> и <tex> \delta</tex> такие, что <tex>S' \Rightarrow^* \gamma A \delta</tex> и <tex> \gamma \Rightarrow^* a_1...a_{i}</tex>.
+
|statement = Приведенный алгоритм правильно строит все списки ситуаций.
 +
То есть алгоритм поддерживает инвариант <tex> [A \rightarrow \alpha \cdot \beta, i] \in 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 =
 
|proof =
  
  
<tex>\Rightarrow</tex> <br>
+
<b><tex>\Longrightarrow</tex></b><br/>
Докажем по индукции.<br>
+
Докажем индукцией по исполнению алгоритма.<br/>
База: для любой ситуации из <tex>I_0</tex> <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>S' \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>
+
<u> ''База индукции:'' </u><br/>
Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br><br>
+
<tex>[S' \rightarrow \cdot S, 0] \in D_0 \ </tex>.<br/>
<b>1. Пусть включаем по правилу 1</b><br>
+
<u> ''Индукционный переход:'' </u> <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>
+
Пусть предположение верно для всех списков ситуаций с номерами меньше <tex> j </tex>. Разберемся, в результате применения какого правила ситуация <tex> [A \rightarrow \alpha \cdot \beta, i] </tex> попала в <tex>D_{j}</tex><br/>
<b>2. Пусть включаем по правилу 2</b><br>
+
 
Тогда <tex>\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \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} </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>
+
1. Включаем по правилу <tex> \mathtt{scan} \ </tex>.<br/>
<b>3. Пусть включаем по правилу 3</b><br>
+
Это произошло, если <tex> \alpha = \alpha ' a</tex>, <tex>a = w_{j-1}</tex> и <tex> [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}</tex>.<br/>
Тогда <tex>\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] \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' \Rightarrow^* 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]</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>\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 \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>\exists  i' \le i</tex> и ситуация <tex>[A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i</tex>, из чего по предположению индукции следует <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex>  
 +
и <tex> \alpha ' \Rightarrow^* w_{i'} \ldots w_{i-1}</tex>.<br/>
 +
Получаем, что <tex>S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''</tex>, значит <tex>S \Rightarrow^* w_0 \ldots w_{i'-1} \alpha' A \delta' \delta '' </tex>, следовательно <tex> S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \ldots w_{i-1} A \delta' \delta ''
 +
</tex>, в итоге <tex> S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta</tex>, что нам и требовалось.
 +
 
 +
3. Включаем по правилу <tex> \mathtt{complete} \ </tex>.<br/>
 +
По построению: <tex> \alpha = \alpha ' A' </tex> и <tex>\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j</tex>.<br/>
 +
Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
 +
 
 +
<b><tex>\Longleftarrow</tex></b><br/>
 +
В обратную сторону будем доказывать индукцией по суммарной длине вывода  <tex>w_0 \ldots w_{i-1} A \delta \ </tex> из <tex>S'</tex> и  <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</tex>. После чего применим
 +
индукцию по длине вывода <tex>w_i \ldots w_{j-1}</tex> из <tex>\alpha</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>, что и требовалось.
  
<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 \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', \beta = S </tex>. Значит по инициализации <tex>[S' \rightarrow \cdot S, 0] \in I_0</tex>. <br>
 
Индукционный переход:
 
Пусть ранг <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>, по правилу 1 получаем, что <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> по правилу 1 или 2 <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>, следовательно по правилу 3 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 
 
}}
 
}}
  
 
==Пример==
 
==Пример==
Рассмотрим грамматику <tex>G</tex> с правилами: <br>
+
Построим список разбора для строки <tex>w = (a + a)</tex> в грамматике со следующими правилами:
<tex>S \rightarrow T + S</tex> <br>
+
* <tex>S \rightarrow T + S</tex>
<tex>S \rightarrow T </tex> <br>
+
* <tex>S \rightarrow T </tex>
<tex>T \rightarrow F * T</tex> <br>
+
* <tex>T \rightarrow F * T</tex>
<tex>T \rightarrow F</tex> <br>
+
* <tex>T \rightarrow F</tex>
<tex>F \rightarrow ( S )</tex> <br>
+
* <tex>F \rightarrow ( S )</tex>
<tex>F \rightarrow a</tex> <br>
+
* <tex>F \rightarrow a</tex>
Построим для строки <tex>\omega = (a + a)</tex> список разбора.<br>
+
 
 +
{|
 +
|-
 +
|
 +
 
 +
{| 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
 +
|}
 +
|}
  
 +
||
  
<b><tex>I_0</tex></b> <br>
+
{| class="wikitable"
<tex>[S' \rightarrow \cdot S, 0]</tex> — из инициализации <br>
+
|-
<tex>[S \rightarrow \cdot T + S, 0]</tex> — из правила 3 <br>
+
!<tex>D_1</tex>
<tex>[S \rightarrow \cdot T, 0]</tex> — из правила 3 <br>
+
|-
<tex>[T \rightarrow \cdot F * T, 0]</tex> — из правила 3 <br>
+
|
<tex>[T \rightarrow \cdot F, 0]</tex> — из правила 3 <br>
+
{|
<tex>[F \rightarrow \cdot ( S ), 0]</tex> — из правила 3 <br>
+
|-
<tex>[F \rightarrow \cdot a, 0]</tex> — из правила 3 <br>
+
!Ситуация !! Из правила
 +
|-
 +
|<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
 +
|}
 +
|}
  
 +
||
  
<b><tex>I_1</tex></b> <br>
+
{| class="wikitable"
<tex>[F \rightarrow ( \cdot S ), 0]</tex> — из правила 1 <br>
+
|-
<tex>[S \rightarrow \cdot T + S, 1]</tex> — из правила 3 <br>
+
!<tex>D_2</tex>
<tex>[S \rightarrow \cdot T, 1]</tex> — из правила 3 <br>
+
|-
<tex>[T \rightarrow \cdot F * T, 1]</tex> — из правила 3 <br>
+
|
<tex>[T \rightarrow \cdot F, 1]</tex> — из правила 3 <br>
+
{|
<tex>[F \rightarrow \cdot ( S ), 1]</tex> — из правила 3 <br>
+
|-
<tex>[F \rightarrow \cdot a, 1]</tex> — из правила 3 <br>
+
!Ситуация !! Из правила
 +
|-
 +
|<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
 +
|}
 +
|}
  
 +
|-
 +
|
  
<b><tex>I_2</tex></b> <br>
+
{| class="wikitable"
<tex>[F \rightarrow a \cdot, 1]</tex> — из правила 1 <br>
+
|-
<tex>[T \rightarrow F \cdot * T, 1]</tex> — из правила 2 <br>
+
!<tex>D_3</tex>
<tex>[T \rightarrow F \cdot , 1]</tex> — из правила 2<br>
+
|-
<tex>[S \rightarrow T \cdot , 1]</tex> — из правила 2 <br>
+
|
<tex>[S \rightarrow T \cdot + S, 1]</tex> — из правила 2 <br>
+
{|
<tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 2 <br>
+
|-
 +
!Ситуация !! Из правила
 +
|-
 +
|<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
 +
|}
 +
|}
  
 +
||
  
<b><tex>I_3</tex></b> <br>
+
{| class="wikitable"
<tex>[S \rightarrow T + \cdot S, 1]</tex> — из правила 1 <br>
+
|-
<tex>[S \rightarrow \cdot T + S, 3]</tex> — из правила 3 <br>
+
!<tex>D_4</tex>
<tex>[S \rightarrow \cdot T, 3]</tex> — из правила 3<br>
+
|-
<tex>[T \rightarrow \cdot F * T, 3]</tex> — из правила 3 <br>
+
|
<tex>[T \rightarrow \cdot F, 3]</tex> — из правила 3 <br>
+
{|
<tex>[F \rightarrow \cdot ( S ), 3]</tex> — из правила 3 <br>
+
|-
<tex>[F \rightarrow \cdot a, 3]</tex> — из правила 3 <br>
+
!Ситуация !! Из правила
 +
|-
 +
|<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
 +
|}
 +
|}
  
 +
||
  
<b><tex>I_4</tex></b> <br>
+
{| class="wikitable"
<tex>[F \rightarrow a \cdot , 3]</tex> — из правила 1 <br>
+
|-
<tex>[T \rightarrow F \cdot * T, 3]</tex> — из правила 2 <br>
+
!<tex>D_5</tex>
<tex>[T \rightarrow F \cdot , 3]</tex> — из правила 2<br>
+
|-
<tex>[S \rightarrow T \cdot + S, 3]</tex> — из правила 2 <br>
+
|
<tex>[S \rightarrow T \cdot , 3]</tex> — из правила 2 <br>
+
{|
<tex>[S \rightarrow T + S \cdot , 1]</tex> — из правила 2 <br>
+
|-
<tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 2 <br>
+
!Ситуация !! Из правила
 +
|-
 +
|<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
 +
|}
 +
|}
  
 +
|}
  
<b><tex>I_5</tex></b> <br>
+
Так как <tex>[S' \rightarrow S \cdot , 0] \in D_5</tex>, то <tex>w \in L(G) </tex>.<br>
<tex>[F \rightarrow ( S )\cdot , 0]</tex> — из правила 1 <br>
 
<tex>[T \rightarrow F \cdot * T, 0]</tex> — из правила 2 <br>
 
<tex>[T \rightarrow F \cdot , 0]</tex> — из правила 2<br>
 
<tex>[S \rightarrow T \cdot + S, 0]</tex> — из правила 2 <br>
 
<tex>[S \rightarrow T \cdot , 0]</tex> — из правила 2 <br>
 
<tex>[S' \rightarrow S \cdot , 0]</tex> — из правила 2 <br>
 
  
 +
==См. также==
 +
* [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 +
* [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
  
Так как <tex>[S' \rightarrow S \cdot , 0] \in I_5</tex>, то <tex>\omega \in L(G) </tex>.<br>
+
==Источники информации==
 +
*[http://lpcs.math.msu.su/~sk/lehre/fivt2013/Earley.pdf Алексей Сорокин {{---}} Алгоритм Эрли]
 +
* Ахо А., Ульман Д.{{---}} Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. {{---}} М.:«Мир», 1978. С. 358 — 364.
  
==Литература==
+
[[Категория: Теория формальных языков]]
''Ахо А., Ульман Д.'' Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.
+
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 19:27, 4 сентября 2022

Алгоритм Эрли позволяет определить, выводится ли данное слово [math]w[/math] в данной контекстно-свободной грамматике [math]G[/math].

Вход: КС грамматика [math] G=\langle N,\Sigma, P, S \rangle[/math] и слово [math]w[/math].
Выход: [math]true[/math], если [math]w[/math] выводится в [math]G[/math]; [math]false[/math] — иначе.


Определение:
Пусть [math]G = \langle N, \Sigma, P, S \rangle[/math]контекстно-свободная грамматика и [math]w = w_0 w_1 \ldots w_{n-1}[/math] — входная цепочка из [math]\Sigma^*[/math]. Объект вида [math][A \rightarrow \alpha \cdot \beta, i][/math], где [math]A \rightarrow \alpha \beta [/math] — правило из [math]P[/math] и [math]0 \leqslant i \leqslant n[/math] — позиция в [math]w[/math], называется ситуацией, относящейся к цепочке [math]w[/math], где [math] \cdot [/math] — вспомогательный символ, который не явлется терминалом или нетерминалом ( [math] \cdot \notin \Sigma \cup N[/math]).


Определение:
Ситуации хранятся в множествах [math]D_0, \ldots ,D_{n-1}[/math], называемых списками ситуаций. Причем наличие ситуации [math][A \rightarrow \alpha \cdot \beta , i][/math] в [math]j[/math]-м списке ситуаций [math]D_j[/math] равносильно тому, что [math]\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})[/math].


Определение:
Последовательность списков ситуаций [math]D_0, D_1, \ldots, D_{n-1} \ [/math] называется списком разбора для входной цепочки [math]w[/math].


Алгоритм Эрли

Чтобы воспользоваться леммой, необходимо найти [math]D_n[/math] для [math]w[/math]. Алгоритм Эрли является динамическим алгоритмом: он последовательно строит список разбора, причём при построении [math]D_j[/math] используются [math]D_0, \ldots, D_{j}[/math] (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).

Алгоритм основывается на следующих трёх правилах:

  1. Если [math][A \rightarrow \alpha \cdot w_{j} \beta, i] \in D_{j-1}[/math] (где [math]w_j[/math][math]j[/math]-ый символ строки), то [math][A \rightarrow \alpha w_{j} \cdot \beta, i] \in D_j[/math].
  2. Если [math][B \rightarrow \eta \ \cdot, i] \in D_j[/math] и [math][A \rightarrow \alpha \cdot B \beta, k] \in D_i[/math], то [math][A \rightarrow \alpha B \cdot \beta, k] \in D_j[/math].
  3. Если [math][A \rightarrow \alpha \ \cdot B \beta, i] \in D_{j} [/math] и [math](B \rightarrow \eta) \in P [/math], то [math][B \rightarrow \cdot \ \eta, j] \in D_{j}[/math].

Псевдокод

Для простоты добавим новый стартовый вспомогательный нетерминал [math]S'[/math] и правило [math](S' \rightarrow S)[/math].

function [math]\mathtt{earley}(G, w)[/math]:
  // Инициализация 
  [math] D_{0} = \lbrace [S' \rightarrow \cdot \ S, 0] \rbrace [/math]
  for [math]i = 1[/math] to [math]len(w)[/math]
    [math]D_i[/math] = [math]\varnothing [/math]
  // Вычисление ситуаций 
  for [math]j = 0[/math] to [math]len(w)[/math]
    [math]\mathtt{scan}(D, j, G, w)[/math]
    while [math]D_j[/math] изменяется
      [math]\mathtt{complete}(D, j, G, w)[/math]
      [math]\mathtt{predict}(D, j, G, w)[/math]
  // Результат 
  if  [math][S' \rightarrow S \ \cdot, 0] \in D_{len(w)} [/math]
    return true
  else
    return false    


function [math]\mathtt{scan}(D, j, G, w)[/math]:
  if [math]j[/math] == [math]0[/math]
    return
  for [math][A \rightarrow \alpha \cdot a \beta, i] \in D_{j - 1} [/math]
    if [math]a[/math] == [math]w_{j - 1}[/math]
      [math]D_{j}[/math] [math] \cup[/math]= [math][A \rightarrow \alpha a \cdot \beta, i][/math]
function [math]\mathtt{complete}(D, j, G, w)[/math]:
  for [math][B \rightarrow \eta \ \cdot, i] \in D_{j} [/math]
    for [math][A \rightarrow \alpha \cdot B \beta, j] \in D_{i} [/math]
      [math]D_{j}[/math] [math] \cup[/math]= [math][A \rightarrow \alpha B \cdot \beta, j][/math]
function [math]\mathtt{predict}(D, j, G, w)[/math]:
  for [math][A \rightarrow \alpha \cdot B \beta, i] \in D_{j} [/math]
    for [math](B \rightarrow \eta) \in P [/math]
      [math]D_{j}[/math] [math]\cup[/math]= [math][B \rightarrow \cdot \ \eta, j][/math]

Корректность алгоритма

Теорема:
Приведенный алгоритм правильно строит все списки ситуаций. То есть алгоритм поддерживает инвариант [math] [A \rightarrow \alpha \cdot \beta, i] \in 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})[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Longrightarrow[/math]
Докажем индукцией по исполнению алгоритма.
База индукции:
[math][S' \rightarrow \cdot S, 0] \in D_0 \ [/math].
Индукционный переход:
Пусть предположение верно для всех списков ситуаций с номерами меньше [math] j [/math]. Разберемся, в результате применения какого правила ситуация [math] [A \rightarrow \alpha \cdot \beta, i] [/math] попала в [math]D_{j}[/math]

1. Включаем по правилу [math] \mathtt{scan} \ [/math].
Это произошло, если [math] \alpha = \alpha ' a[/math], [math]a = w_{j-1}[/math] и [math] [A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}[/math].
По предположению индукции [math]S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta[/math] и [math]\alpha' \Rightarrow^* w_i \ldots w_{j-2}[/math],
тогда в силу [math]a = w_{j-1}[/math] получаем [math]\alpha = \alpha ' a \Rightarrow^* w_i \ldots w_{j-2}w_{j-1} = w_i \ldots w_{j-1} \ [/math].
Таким образом условия: [math]S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta[/math] и [math]\alpha \Rightarrow^* w_i \ldots w_{j-1}[/math] выполняются.

2. Включаем по правилу [math] \mathtt{predict} \ [/math].
По построению: [math] \alpha = \varepsilon [/math] и [math]i=j[/math], что автоматически влечет второй пункт утверждения.
Кроме того [math]\exists i' \le i[/math] и ситуация [math][A' \rightarrow \alpha ' \cdot A \delta ', i'] \in D_i[/math], из чего по предположению индукции следует [math]S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''[/math] и [math] \alpha ' \Rightarrow^* w_{i'} \ldots w_{i-1}[/math].
Получаем, что [math]S' \Rightarrow^* w_0 \ldots w_{i'-1} A' \delta ''[/math], значит [math]S \Rightarrow^* w_0 \ldots w_{i'-1} \alpha' A \delta' \delta '' [/math], следовательно [math] S' \Rightarrow^* w_0 \ldots w_{i'-1} w_{i'} \ldots w_{i-1} A \delta' \delta '' [/math], в итоге [math] S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta[/math], что нам и требовалось.

3. Включаем по правилу [math] \mathtt{complete} \ [/math].
По построению: [math] \alpha = \alpha ' A' [/math] и [math]\exists i', \delta : [A \rightarrow \alpha ' \cdot A' \beta, i] \in D_{i'} \wedge [A' \rightarrow \eta \cdot, i'] \in D_j[/math].
Cледовательно [math]\alpha = \alpha ' A' \Rightarrow^* w_i \ldots w_{i'-1} w_{i'} \ldots w_{j} = w_i \ldots w_{j-1}[/math], что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.

[math]\Longleftarrow[/math]
В обратную сторону будем доказывать индукцией по суммарной длине вывода [math]w_0 \ldots w_{i-1} A \delta \ [/math] из [math]S'[/math] и [math]w_i \ldots w_{j-1}[/math] из [math]\alpha[/math]. После чего применим индукцию по длине вывода [math]w_i \ldots w_{j-1}[/math] из [math]\alpha[/math].
Рассмотрим три случая последнего символа [math]\alpha[/math]:

1. [math]\alpha = \alpha ' a[/math], тогда [math]a = w_{j-1}[/math] и [math]\alpha ' \Rightarrow^* w_i \ldots w_{j-2}[/math].
По предположению индукции: [math][A \rightarrow \alpha ' \cdot a \beta, i] \in D_{j-1}[/math], а отсюда по правилу [math] \mathtt{scan}[/math] получаем [math][A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}[/math].

2. [math]\alpha = \alpha ' B[/math], тогда [math]\exists i' : \alpha ' \Rightarrow^* w_i \ldots w_{i'-1} \wedge B ' \Rightarrow^* w_{i'} \ldots w_{j-1}[/math].
Тогда имеем [math][A \rightarrow \alpha ' a \cdot \beta, i] \in D_{j}[/math]. Также можно записать [math]S' \Rightarrow^* w_0 \ldots w_{i-1} A \delta[/math], как [math]S' \Rightarrow^* w_0 \ldots w_{i-1} w_i \ldots w_{i'-1}B \beta \delta[/math], а также [math]B \rightarrow \eta \wedge \eta \rightarrow w_{i'} \ldots w_{j-1}[/math].
Применяя индукцию по второму параметру получим [math][B \rightarrow \eta \cdot, i'] \in D_j \ [/math], откуда по правилу [math] \mathtt{complete}[/math] получаем [math][A \rightarrow \alpha ' B \cdot \beta, i] \in D_{j}[/math].

3. [math]\alpha = \varepsilon [/math], тогда [math]i=j[/math].
Тогда либо [math]i = 0 \wedge A = S \wedge \delta = \varepsilon[/math], что доказывает базу индукции,
либо вывод можно записать в виде [math]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 \ [/math] для некоторого правила [math](A' \rightarrow w_{i'} \ldots w_{i-1} A \delta ') \in P[/math].
Отсюда по предположению индукции [math][A' \rightarrow \cdot w_{i'} \ldots w_{i-1} A \delta ', i'] \in D_{i'} \ [/math], что после нескольких применений правила [math] \mathtt{scan}[/math] приводит к [math][A' \rightarrow w_{i'} \ldots w_{i-1} \cdot A \delta ', i'] \in D_{i} \ [/math],

после чего по правилу [math] \mathtt{predict} \ [/math] получим [math][A \rightarrow \cdot \beta, i] \in D_{j} \ [/math], что и требовалось.
[math]\triangleleft[/math]

Пример

Построим список разбора для строки [math]w = (a + a)[/math] в грамматике со следующими правилами:

  • [math]S \rightarrow T + S[/math]
  • [math]S \rightarrow T [/math]
  • [math]T \rightarrow F * T[/math]
  • [math]T \rightarrow F[/math]
  • [math]F \rightarrow ( S )[/math]
  • [math]F \rightarrow a[/math]
[math]D_0[/math]
Ситуация Из правила
[math][S' \rightarrow \cdot S, 0][/math] 0
[math][S \rightarrow \cdot T + S, 0][/math] 3
[math][S \rightarrow \cdot T, 0][/math] 3
[math][T \rightarrow \cdot F * T, 0][/math] 3
[math][T \rightarrow \cdot F, 0][/math] 3
[math][F \rightarrow \cdot ( S ), 0][/math] 3
[math][F \rightarrow \cdot a, 0][/math] 3
[math]D_1[/math]
Ситуация Из правила
[math][F \rightarrow ( \cdot S ), 0][/math] 1
[math][S \rightarrow \cdot T + S, 1][/math] 3
[math][S \rightarrow \cdot T, 1][/math] 3
[math][T \rightarrow \cdot F * T, 1][/math] 3
[math][T \rightarrow \cdot F, 1][/math] 3
[math][F \rightarrow \cdot ( S ), 1][/math] 3
[math][F \rightarrow \cdot a, 1][/math] 3
[math]D_2[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot, 1][/math] 1
[math][T \rightarrow F \cdot * T, 1][/math] 2
[math][T \rightarrow F \cdot , 1][/math] 2
[math][S \rightarrow T \cdot , 1][/math] 2
[math][S \rightarrow T \cdot + S, 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]D_3[/math]
Ситуация Из правила
[math][S \rightarrow T + \cdot S, 1][/math] 1
[math][S \rightarrow \cdot T + S, 3][/math] 3
[math][S \rightarrow \cdot T, 3][/math] 3
[math][T \rightarrow \cdot F * T, 3][/math] 3
[math][T \rightarrow \cdot F, 3][/math] 3
[math][F \rightarrow \cdot ( S ), 3][/math] 3
[math][F \rightarrow \cdot a, 3][/math] 3
[math]D_4[/math]
Ситуация Из правила
[math][F \rightarrow a \cdot , 3][/math] 1
[math][T \rightarrow F \cdot * T, 3][/math] 2
[math][T \rightarrow F \cdot , 3][/math] 2
[math][S \rightarrow T \cdot + S, 3][/math] 2
[math][S \rightarrow T \cdot , 3][/math] 2
[math][S \rightarrow T + S \cdot , 1][/math] 2
[math][F \rightarrow ( S \cdot ), 0][/math] 2
[math]D_5[/math]
Ситуация Из правила
[math][F \rightarrow ( S )\cdot , 0][/math] 1
[math][T \rightarrow F \cdot * T, 0][/math] 2
[math][T \rightarrow F \cdot , 0][/math] 2
[math][S \rightarrow T \cdot + S, 0][/math] 2
[math][S \rightarrow T \cdot , 0][/math] 2
[math][S' \rightarrow S \cdot , 0][/math] 2

Так как [math][S' \rightarrow S \cdot , 0] \in D_5[/math], то [math]w \in L(G) [/math].

См. также

Источники информации

  • Алексей Сорокин — Алгоритм Эрли
  • Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.