|
|
| Строка 101: |
Строка 101: |
| | По построению: <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/> | | По построению: <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...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. | | Cледовательно <tex>\alpha = \alpha ' A' \Rightarrow^* w_i...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}</tex>, что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо. |
| − |
| |
| | | | |
| | =====<tex>\Longleftarrow</tex>===== | | =====<tex>\Longleftarrow</tex>===== |
| | + | В обратную сторону будем доказывать индукцией по суммарной длине вывода <tex>w_0...w_{i-1} A \delta</tex> из <tex>S</tex> и <tex>w_i...w_{j-1}</tex> из <tex>\alpha</tex>.<br/> |
| | + | Рассмотрим три случая последнего символа <tex>\alpha</tex>: |
| | | | |
| − | Для всех наборов <tex>\tau = \langle \alpha, \beta, \gamma, \delta, A, i , j \rangle</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]</tex> в <tex> I_{j}</tex>.
| + | 1. <tex>\alpha = \alpha ' a</tex>, тогда <tex>a = w_{j-1}</tex> и <tex>\alpha ' \Rightarrow^* w_i...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>. |
| − | ''Рангом набора'' <tex> \tau </tex> называется <tex> \tau_{S'}(\tau) + 2(j + \tau_{\gamma}(\tau) + \tau_{\alpha}(\tau))</tex>, где <tex>\tau_{S'}(\tau)</tex> — длина кратчайшего вывода <tex>S' \Rightarrow^* \gamma A \delta </tex>, <tex>\tau_{\gamma}(\tau)</tex> — длина кратчайшего вывода <tex>\gamma \Rightarrow^* a_1...a_{i}</tex>, <tex>\tau_{\alpha}(\tau)</tex> — длина кратчайшего вывода <tex>\alpha \Rightarrow^* a_{i+1}...a_{j}</tex>.
| |
| − | | |
| − | Докажем утверждение индукцией по рангу набора.<br/>
| |
| − | База: если ранг <tex>\tau</tex> равен 0, то <tex>\tau_{S'} = \tau_{\gamma} = \tau_{\alpha} = j = i = 0</tex>. Значит, <tex>A = S'</tex>, <tex>\alpha = \gamma = \delta = \varepsilon </tex>, <tex>\beta = S </tex>. При инициализации такая ситуация <tex>[S' \rightarrow \cdot S, 0]</tex> будет добавлена в <tex>I_0</tex>.<br/>
| |
| − | Индукционный переход:
| |
| − | пусть ранг <tex>\tau</tex> равен <tex>r > 0</tex>, пусть для всех наборов с меньшими рангами утверждение верно. Докажем для набора <tex>\tau</tex>. Для этого рассмотрим три случая:
| |
| − | | |
| − | 1. <tex>\alpha</tex> оканчивается терминалом.<br/>
| |
| − | <tex>\alpha = \alpha' c</tex>. <tex>\alpha \Rightarrow^*a_{i+1}...a_{j}</tex>, значит <tex>c = a_{j}</tex>. Рассмотрим набор <tex>\tau' = \langle \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \rangle </tex>. <tex>(A \rightarrow \alpha' a_{j} \beta) \in P</tex>, следовательно ранг <tex>\tau'</tex> равен <tex>r - 2</tex>, так как <tex>\tau_{S'}(\tau) = \tau_{S'}(\tau'), \tau_{\gamma}(\tau) = \tau_{\gamma}(\tau'), \tau_{\alpha}(\tau) = \tau_{\alpha}(\tau')</tex>. Значит, по предположению <tex>[A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}</tex>, и <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex> по правилу <tex>(1)</tex>.
| |
| − | | |
| − | 2. <tex>\alpha</tex> оканчивается нетерминалом.<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' = \langle \alpha', B \beta, \gamma, \delta, A, i, k \rangle</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'' = \langle \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \rangle</tex>. <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta</tex>, следовательно <tex>\tau_{S'}(\tau'') \leqslant \tau_{S'}(\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_{\alpha}(\tau) = n_1 + n_2</tex>. Так как <tex> B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}</tex>, то <tex>\tau_{\alpha}(\tau'') = n_2 - 1</tex>. Очевидно, что <tex>\tau_{\gamma}(\tau'') = \tau_{\gamma}(\tau) + n_1</tex>. Тогда ранг <tex>\tau''</tex> равен <tex>\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)</tex> <tex>= \tau_{S'}(\tau) - 1 + 2(\tau_{\gamma}(\tau) + \tau_{\alpha}(\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>, по правилу <tex>(2)</tex> <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
| |
| | | | |
| − | 3. <tex>\alpha = \varepsilon</tex>.<br/>
| |
| − | В этом случае <tex>i = j, \tau_{\alpha}(\tau) = 0, (A \rightarrow \beta) \in P</tex>.<br/>
| |
| − | <tex>\tau_{S'}(\tau) \neq 0</tex> т.к. иначе <tex> \gamma = \varepsilon</tex>, следовательно <tex> \tau_{\gamma}(\tau) = 0, i = 0 </tex>, откуда <tex> r = 0</tex>, но <tex>r > 0</tex>.
| |
| − | Т.к. <tex>\tau_{S'}(\tau) > 0</tex>, <tex> \exists B, \gamma', \gamma'', \delta', \delta'' : S' \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''</tex>, где <tex>(B \rightarrow \gamma'' A \delta'') \in P</tex>. Рассмотрим набор <tex>\tau' = \langle \gamma'', A \delta'', \gamma', \delta', B, k, j \rangle</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_{S'}(\tau') = \tau_{S'}(\tau) - 1, \tau_{\gamma}(\tau') = n_1, \tau_{\alpha}(\tau') = n_2</tex>. <tex>\tau_{\alpha}(\tau) = 0, \tau_{\gamma}(\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>, следовательно по правилу <tex>(3)</tex> <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
| |
| | }} | | }} |
| | | | |
Алгоритм Эрли позволяет определить, выводится ли данное слово [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_1 w_2 ... w_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] \cdot [/math] — вспомогательный символ, который не явлется терминалом или нетерминалом ( [math] \cdot \notin \Sigma \cup N[/math]). |
| Определение: |
| [math]j[/math]-м списком ситуаций [math]D_j[/math] для входной цепочки [math]w = w_1 w_2 ... w_n[/math], где [math]0 \leqslant j \leqslant n[/math], называется множество ситуаций [math]\lbrace [A \rightarrow \alpha \cdot \beta , i] \mid \alpha \Rightarrow^* w_{i+1} ... w_j; \exists \gamma, \delta : S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* w_1...w_i \rbrace[/math]. То есть [math]\gamma \alpha [/math] выводит часть [math]w[/math] c первого по [math]j[/math]-й символ. |
| Лемма: |
[math](\exists \alpha : [S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow w \in L(G)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Поскольку [math]S \Rightarrow^* \gamma S \delta[/math] (при [math]\gamma = \delta = \varepsilon[/math]), из определения [math]D_n[/math] получаем, что [math]([S \rightarrow \alpha \cdot, 0] \in D_n) \Leftrightarrow (S \Rightarrow \alpha \Rightarrow^* w_1 ... w_n = w)[/math]. |
| [math]\triangleleft[/math] |
| Определение: |
| Последовательность списков ситуаций [math]D_0, D_1, .., D_n[/math] называется списком разбора для входной цепочки [math]w[/math]. |
Алгоритм Эрли
Чтобы воспользоваться леммой, необходимо найти [math]D_n[/math] для [math]w[/math]. Алгоритм Эрли является динамическим алгоритмом: он последовательно строит список разбора, причём при построении [math]D_j[/math] используются [math]D_0, \ldots, D_{j}[/math] (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
Алгоритм основывается на следующих трёх правилах:
- Если [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].
- Если [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].
- Если [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 i = 1 to len(w) - 1
[math]D_i[/math] = [math]\varnothing [/math]
// Вычисление ситуаций
for j = 0 to len(w) - 1
[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 \cdot a \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, k] \in D_{i} [/math]
[math]D_{j}[/math] [math] \cup[/math]= [math][A \rightarrow \alpha B \cdot \beta, k][/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...w_{i-1} A \delta) \wedge A \Rightarrow^* w_i...w_{j-1})[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
[math]\Longrightarrow[/math]
Докажем индукцией по исполнению алгоритма.
База — [math][S' \rightarrow \cdot S, 0] \in D_0[/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...w_{i-1} A \delta[/math] и [math]\alpha' \Rightarrow^* w_i...w_{j-2}[/math],
тогда в силу [math]a = w_{j-1}[/math] получаем [math]\alpha = \alpha ' a \Rightarrow^* w_i...w_{j-2}w_{j-1} = w_i...w_{j-1}[/math].
Таким образом условия: [math]S \Rightarrow^* w_0...w_{i-1} A \delta[/math] и [math]\alpha \Rightarrow^* w_i...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...w_{i'-1} A' \delta ''[/math]
и [math] \alpha ' \Rightarrow^* w_{i'}...w_{i-1}[/math].
Получаем, что [math]S \Rightarrow^* w_0...w_{i'-1} A' \delta ''[/math], значит [math]S \Rightarrow^* w_0...w_{i'-1} \alpha' A \delta' \delta '' [/math], следовательно [math] S \Rightarrow^* w_0...w_{i'-1} w_{i'}...w_{i-1} A \delta' \delta ''
[/math], в итоге [math] S \Rightarrow^* w_0...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...w_{i'-1} w_{i'}...w_{j} = w_i...w_{j-1}[/math], что дает нам второй пункт утверждения, а так как первый пункт следует из индукционного предположения, все хорошо.
[math]\Longleftarrow[/math]
В обратную сторону будем доказывать индукцией по суммарной длине вывода [math]w_0...w_{i-1} A \delta[/math] из [math]S[/math] и [math]w_i...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...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]. |
| [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.
