Участник:Shovkoplyas Grigory — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 37: Строка 37:
 
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
 
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'</tex> и правило <tex>(S' \rightarrow S)</tex>.
 
  <font color=green> // Инициализация </font>
 
  <font color=green> // Инициализация </font>
  D[0] = {[S' &#x27f6; &middot;S, 0]}
+
  D[0] = {[S' <tex>\rightarrow</tex> <tex>\cdot</tex>S, 0]}
 
  '''for''' i = 1 '''to''' len(w) - 1
 
  '''for''' i = 1 '''to''' len(w) - 1
 
   D[i] = <tex>\varnothing </tex>
 
   D[i] = <tex>\varnothing </tex>
 
  <font color=green> // Основная часть </font>
 
  <font color=green> // Основная часть </font>
  '''for''' j = 0 '''to''' len(w) -1
+
  '''for''' j = 0 '''to''' len(w) - 1
 
   scan(D, j)
 
   scan(D, j)
 
   '''while''' D[j] изменяется
 
   '''while''' D[j] изменяется
Строка 51: Строка 51:
 
   '''if''' j = 0
 
   '''if''' j = 0
 
     '''return'''
 
     '''return'''
   '''for''' [A &#x27f6; &alpha;&middot;a&beta;, i] &isin; D[j - 1]
+
   '''for''' [A <tex>\rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>a<tex>\beta</tex>, i] <tex>\in</tex> D[j - 1]
 
     '''if''' a = w[j - 1]
 
     '''if''' a = w[j - 1]
       D[j] &cup;= {[A &#x27f6; &alpha;a&middot;&beta;, i]}
+
       D[j] &cup;= {[A <tex>\rightarrow</tex> <tex>\alpha</tex>a<tex>\cdot</tex><tex>\beta</tex>, i]}
 
 
  <font color=green> // Второе правило </font>
 
  <font color=green> // Второе правило </font>
 
  '''function''' predict(D, j)
 
  '''function''' predict(D, j)
   '''for''' [A &#x27f6; &alpha;&middot;B&beta;, i] &isin; D[j]
+
   '''for''' [A <tex>\rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>B<tex>\beta</tex>, i] <tex>\in</tex> D[j]
     '''for''' [B &#x27f6; &eta;] &isin; P
+
     '''for''' [B <tex>\rightarrow</tex> &eta;] <tex>\in</tex> P
       D[j] &cup;= {[B &#x27f6; &middot;&eta;]}
+
       D[j] &cup;= {[B <tex>\rightarrow</tex> <tex>\cdot</tex>&eta;]}
 
 
 
  <font color=green> // Третье правило </font>
 
  <font color=green> // Третье правило </font>
 
  '''function''' complete(D, j)
 
  '''function''' complete(D, j)
   '''for''' [B &#x27f6; &eta;&middot;, i] &isin; D[j]
+
   '''for''' [B <tex>\rightarrow</tex> &eta;<tex>\cdot</tex>, i] <tex>\in</tex> D[j]
     '''for''' [A &#x27f6; &alpha;&middot;B&beta;, k] &isin; D[i]
+
     '''for''' [A <tex>\rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>B<tex>\beta</tex>, k] <tex>\in</tex> D[i]
       D[j] &cup;= {[A &#x27f6; &alpha;&middot;B&beta;, k]}
+
       D[j] &cup;= {[A <tex>\rightarrow</tex> <tex>\alpha</tex><tex>\cdot</tex>B<tex>\beta</tex>, k]}
  
 
==Корректность алгоритма==
 
==Корректность алгоритма==

Версия 19:41, 16 января 2016

Алгоритм Эрли позволяет определить, выводится ли данное слово [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 = a_1 a_2 ... a_n[/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]j[/math]-м списком ситуаций [math]I_j[/math] для входной цепочки [math]w = a_1 a_2 ... a_n[/math], где [math]0 \leqslant j \leqslant n[/math], называется множество ситуаций [math]\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[/math]. То есть [math]\gamma \alpha [/math] выводит часть [math]w[/math] c первого по [math]j[/math]-й символ.


Лемма:
[math](\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow w \in L(G)[/math].
Доказательство:
[math]\triangleright[/math]
Поскольку [math]S \Rightarrow^* \gamma S \delta[/math] (при [math]\gamma = \delta = \varepsilon[/math]), из определения [math]I_n[/math] получаем, что [math]([S \rightarrow \alpha \cdot, 0] \in I_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* a_1 ... a_n = w)[/math].
[math]\triangleleft[/math]


Определение:
Последовательность списков ситуаций [math]I_0, I_1, .., I_n[/math] называется списком разбора для входной цепочки [math]w[/math].


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

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

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

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

Псевдокод

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

 // Инициализация 
D[0] = {[S' [math]\rightarrow[/math] [math]\cdot[/math]S, 0]}
for i = 1 to len(w) - 1
  D[i] = [math]\varnothing [/math]
 // Основная часть 
for j = 0 to len(w) - 1
  scan(D, j)
  while D[j] изменяется
    complete(D, j)
    predict(D, j)
 // Первое правило 
function scan(D, j)
  if j = 0
    return
  for [A [math]\rightarrow[/math] [math]\alpha[/math][math]\cdot[/math]a[math]\beta[/math], i] [math]\in[/math] D[j - 1]
    if a = w[j - 1]
      D[j] ∪= {[A [math]\rightarrow[/math] [math]\alpha[/math]a[math]\cdot[/math][math]\beta[/math], i]}
 // Второе правило 
function predict(D, j)
  for [A [math]\rightarrow[/math] [math]\alpha[/math][math]\cdot[/math]B[math]\beta[/math], i] [math]\in[/math] D[j]
    for [B [math]\rightarrow[/math] η] [math]\in[/math] P
      D[j] ∪= {[B [math]\rightarrow[/math] [math]\cdot[/math]η]}
 // Третье правило 
function complete(D, j)
  for [B [math]\rightarrow[/math] η[math]\cdot[/math], i] [math]\in[/math] D[j]
    for [A [math]\rightarrow[/math] [math]\alpha[/math][math]\cdot[/math]B[math]\beta[/math], k] [math]\in[/math] D[i]
      D[j] ∪= {[A [math]\rightarrow[/math] [math]\alpha[/math][math]\cdot[/math]B[math]\beta[/math], k]}

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

Теорема:
Приведенный алгоритм правильно строит все списки ситуаций.
Доказательство:
[math]\triangleright[/math]
Алгоритм не добавит в список ситуацию, которая ему не принадлежит:

Докажем индукцией по исполнению алгоритма.
База (инициализация): [math]\alpha = \varepsilon \Rightarrow^* \varepsilon [/math] и [math]S' \Rightarrow^* \gamma S \delta [/math] при [math]\gamma = \delta = \varepsilon [/math].
Индукционный переход: пусть в [math] I_{0},...,I_{j} [/math] нет лишних ситуаций. Пусть включаем [math][A \rightarrow \alpha \cdot \beta, i] [/math] в [math]I_{j}[/math]. Рассмотрим три случая:

1. Включаем по правилу [math](1)[/math].
Тогда [math]\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math]. По предположению [math]\alpha' \Rightarrow^* a_{i+1}...a_{j-1} [/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' \Rightarrow^* a_1...a_{i} [/math]. Значит, [math] \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j} [/math] и при [math]\gamma = \gamma', \delta = \delta'[/math] [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

2. Включаем по правилу [math](2)[/math].
Тогда [math]\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] и [math] [B \rightarrow \eta \cdot, k] \in I_{j} [/math]. По предположению, [math]\alpha' \Rightarrow^* a_{i+1}...a_{k}, \eta \Rightarrow^* a_{k+1}...a_{j} [/math], откуда [math]\alpha = \alpha' B \Rightarrow^*a_{i+1}...a_{j} [/math]. Кроме того, существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} [/math]. Значит, при [math]\gamma = \gamma', \delta = \delta'[/math] [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

3. Включаем по правилу [math](3)[/math].
Тогда [math]\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \eta, k] \in I_{j}, A \Rightarrow \beta[/math]. По предположению [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}[/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S' \Rightarrow^* \gamma' B \delta', \gamma' \Rightarrow^* a_1...a_{k} [/math]. Значит, при [math]\gamma = \gamma' \alpha', \delta = \eta \delta' [/math] выполнено [math] S' \Rightarrow^* \gamma A \delta[/math], следовательно [math][A \rightarrow \alpha \cdot \beta, i] \in I_j[/math].

В каждый список попадут все ситуации, которые ему принадлежат:

Для всех наборов [math]\tau = \langle \alpha, \beta, \gamma, \delta, A, i , j \rangle[/math] нужно доказать, что, если [math] S' \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_{i}, (A \rightarrow \alpha \beta) \in P, \alpha \Rightarrow^* a_{i+1}...a_{j}[/math], то алгоритм добавит [math] [A \rightarrow \alpha \cdot \beta, i][/math] в [math] I_{j}[/math].

Рангом набора [math] \tau [/math] называется [math] \tau_{S'}(\tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(\tau))[/math], где [math]\tau_{S'}(\tau)[/math] — длина кратчайшего вывода [math]S' \Rightarrow^* \gamma A \delta [/math], [math]\tau_{\gamma}(\tau)[/math] — длина кратчайшего вывода [math]\gamma \Rightarrow^* a_1...a_{i}[/math], [math]\tau_{\alpha}(\tau)[/math] — длина кратчайшего вывода [math]\alpha \Rightarrow^* a_{i+1}...a_{j}[/math].

Докажем утверждение индукцией по рангу набора.
База: если ранг [math]\tau[/math] равен 0, то [math]\tau_{S'} = \tau_{\gamma} = \tau_{\alpha} = j = i = 0[/math]. Значит, [math]A = S'[/math], [math]\alpha = \gamma = \delta = \varepsilon [/math], [math]\beta = S [/math]. При инициализации такая ситуация [math][S' \rightarrow \cdot S, 0][/math] будет добавлена в [math]I_0[/math].
Индукционный переход: пусть ранг [math]\tau[/math] равен [math]r \gt 0[/math], пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора [math]\tau[/math]. Для этого рассмотрим три случая:

1. [math]\alpha[/math] оканчивается терминалом.
[math]\alpha = \alpha' c[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]c = a_{j}[/math]. Рассмотрим набор [math]\tau' = \langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \rangle [/math]. [math](A \rightarrow \alpha' a_{j} \beta) \in P[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 2[/math], так как [math]\tau_{S'}(\tau) = \tau_{S'}(\tau'), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')[/math]. Значит, по предположению [math][A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math], и [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math] по правилу [math](1)[/math].

2. [math]\alpha[/math] оканчивается нетерминалом.
[math]\alpha = \alpha' B[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]\mathcal {9} k[/math] такое, что [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}, B \Rightarrow^* a_{k+1}...a_{j}[/math].
Рассмотрим набор [math]\tau' = \langle \alpha', B \beta, \gamma, \delta, A, i, k \rangle[/math], его ранг меньше [math]r[/math], следовательно [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] по предположению.
Пусть [math]B \Rightarrow \eta[/math] — первый шаг в кратчайшем выводе [math]B \Rightarrow^* a_{k+1}...a_{j}[/math]. Рассмотрим набор [math]\tau'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle[/math]. [math]S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta[/math], следовательно [math]\tau_{S'}(\tau'') \leqslant \tau_{S'}(\tau) + 1[/math].
Пусть длина кратчайшего вывода [math]\alpha' \Rightarrow^*a_{i+1}...a_{k}[/math] равна [math]n_1[/math], а длина кратчайшего вывода [math] B \Rightarrow^* a_{k+1}...a_{j}[/math] равна [math]n_2[/math]. Тогда [math]\tau_{\alpha}(\tau) = n_1 + n_2[/math]. Так как [math] B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}[/math], то [math]\tau_{\alpha}(\tau'') = n_2 - 1[/math]. Очевидно, что [math]\tau_{\gamma}(\tau'') = \tau_{\gamma}(\tau) + n_1[/math]. Тогда ранг [math]\tau''[/math] равен [math]\tau_{S'}(\tau'') + 2(\tau_{\gamma}(\tau'') + \tau_{\alpha}(\tau'') + j) \leqslant \tau_{S'}(\tau) + 1 + 2(\tau_{\gamma}(\tau) + n_1 + n_2 - 1 + j)[/math] [math]= \tau_{S'}(\tau) - 1 + 2(\tau_{\gamma}(\tau) + \tau_{\alpha}(\tau) + j) \lt r[/math]. Значит, по предположению для [math]\tau''[/math], [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math]. Из того, что [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_{k}[/math] и [math][B \rightarrow \eta \cdot, k] \in I_{j}[/math], по правилу [math](2)[/math] [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].

3. [math]\alpha = \varepsilon[/math].
В этом случае [math]i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P[/math].
[math]\tau_{S'}(\tau) \neq 0[/math] т.к. иначе [math] \gamma = \varepsilon[/math], следовательно [math] \tau_{\gamma}(\tau) = 0, i = 0 [/math], откуда [math] r = 0[/math], но [math]r \gt 0[/math]. Т.к. [math]\tau_{S'}(\tau) \gt 0[/math], [math] \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''[/math], где [math](B \rightarrow \gamma'' A \delta'') \in P[/math]. Рассмотрим набор [math]\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle[/math], где [math]k[/math] такое, что [math]\gamma' \Rightarrow^* a_1...a_{k}, \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math]. Пусть длина кратчайшего вывода [math]\gamma' \Rightarrow^*a_{1}...a_{k}[/math] равна [math]n_1[/math], а длина кратчайшего вывода [math] \gamma'' \Rightarrow^* a_{k+1}...a_{j}[/math] равна [math]n_2[/math].

Найдём ранг [math]\tau'[/math]. [math]\tau_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2[/math]. [math]\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\tau) = n_1 + n_2[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 1[/math]. Значит, по предположению [math][B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}[/math], следовательно по правилу [math](3)[/math] [math][A \rightarrow \cdot \beta, i] [/math] будет добавлена в [math]I_{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]I_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]I_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]I_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]I_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]I_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]I_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 I_5[/math], то [math]w \in L(G) [/math].

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

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