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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определения)
Строка 32: Строка 32:
  
 
Если <tex>[S \rightarrow \alpha \cdot, 0] \in I_n</tex>, то <tex>\omega \in L(G) </tex>.<br>
 
Если <tex>[S \rightarrow \alpha \cdot, 0] \in I_n</tex>, то <tex>\omega \in L(G) </tex>.<br>
 +
 +
 +
 +
==Корректность алгоритма==
 +
{{Теорема
 +
|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>
 +
|proof =
 +
 +
 +
<tex>\Rightarrow</tex> <br>
 +
Докажем по индукции.<br>
 +
База: для любой ситуации из <tex>I_0</tex>  <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>S \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>
 +
Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br><br>
 +
<b>1. Пусть включаем по правилу 4</b><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>
 +
<b>2. Пусть включаем по правилу 5</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>
 +
<b>3. Пусть включаем по правилу 6</b><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' = 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>\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 B \beta, i] \in I_{j}</tex>.<br>
 +
*<b>Рангом набора </b> <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</tex>, следовательно <tex>S \rightarrow \beta \in P</tex>. Значит по правилу 1 <tex>[S \rightarrow \cdot \beta, 0] \in I_0</tex>
 +
Индукционный переход:
 +
Пусть ранг <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>, по правилу 4 получаем, что <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> по правилу 4 или 5 <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>, следовательно по правилу 6 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 +
}}
  
 
==Пример==
 
==Пример==
Строка 100: Строка 135:
  
 
Так как <tex>[S \rightarrow T \cdot , 0] \in I_5</tex>, то <tex>\omega \in L(G) </tex>.<br>
 
Так как <tex>[S \rightarrow T \cdot , 0] \in I_5</tex>, то <tex>\omega \in L(G) </tex>.<br>
 
==Корректность алгоритма==
 
{{Теорема
 
|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>
 
|proof =
 
 
 
<tex>\Rightarrow</tex> <br>
 
Докажем по индукции.<br>
 
База: для любой ситуации из <tex>I_0</tex>  <tex>\alpha \Rightarrow^* \varepsilon </tex> и <tex>S \Rightarrow^* \gamma A \delta </tex> при <tex>\gamma = \varepsilon </tex>.<br>
 
Индукционный переход (и.п.): пусть верно для всех ситуаций из списков <tex> I_{i}, i \leqslant j </tex>. Пусть включаем <tex>[A \rightarrow \alpha \cdot \beta, i] </tex> в <tex>I_{j}</tex>. Рассмотрим три случая:<br><br>
 
<b>1. Пусть включаем по правилу 4</b><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>
 
<b>2. Пусть включаем по правилу 5</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>
 
<b>3. Пусть включаем по правилу 6</b><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' = 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>\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 B \beta, i] \in I_{j}</tex>.<br>
 
*<b>Рангом набора </b> <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</tex>, следовательно <tex>S \rightarrow \beta \in P</tex>. Значит по правилу 1 <tex>[S \rightarrow \cdot \beta, 0] \in I_0</tex>
 
Индукционный переход:
 
Пусть ранг <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>, по правилу 4 получаем, что <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> по правилу 4 или 5 <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>, следовательно по правилу 6 <tex>[A \rightarrow \cdot \beta, i] </tex> будет добавлена в <tex>I_{j}</tex>.
 
}}
 
  
 
==Литература==
 
==Литература==
 
Ахо А., Ульман Д. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. — С. 358 — 364.
 
Ахо А., Ульман Д. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. — С. 358 — 364.

Версия 02:23, 7 декабря 2011

Пусть дана контекстно-свободная грамматика [math]G[/math] и входная цепочка [math]\omega[/math]. Требуется определить, выводится ли [math]\omega[/math] в [math]G[/math].

Определения

Определение:
Пусть [math]G = (N, \Sigma, P, S)[/math]контекстно-свободная грамматика и [math]\omega = a_1 a_2 ... a_n[/math] — входная цепочка из [math]\Sigma^*[/math]. Объект вида [math][A \rightarrow \alpha \cdot \beta, i][/math] называется ситуацией, относящейся к цепочке [math]\omega[/math], если [math]A \rightarrow \alpha \beta [/math] — правило из [math]P[/math] и [math]0 \leqslant i \leqslant n[/math] — позиция в [math]\omega[/math].


Определение:
Cписком ситуаций [math]I_j[/math], где [math]0 \leqslant j \leqslant n[/math] называется множество ситуаций [math][A \rightarrow \alpha \cdot \beta , i] [/math] таких, что [math]\alpha \Rightarrow^* a_{i+1} ... a_j[/math], и для некоторых [math]\gamma[/math] и [math]\delta[/math] существуют выводы [math]S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i[/math].


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


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

Построим список разбора для [math]\omega[/math] Строим [math]I_0[/math]
Шаг 1. Если [math]S \rightarrow \alpha \in P[/math], включить [math][S \rightarrow \cdot \alpha, 0][/math] в [math]I_0[/math].
Пока можно включить новые ситуации в [math]I_0[/math] повторяем шаги 2 и 3.
Шаг 2. Если [math][B \rightarrow \gamma \cdot, 0] \in I_0[/math], включить в [math]I_0[/math] ситуацию [math][A \rightarrow \alpha B \cdot \beta, 0][/math] для всех [math][A \rightarrow \alpha \cdot B \beta, 0][/math] из [math]I_0[/math].
Шаг 3. Для всех [math][A \rightarrow \alpha \cdot B \beta, 0] \in I_0[/math], для всех [math]\gamma[/math] таких, что [math]B \rightarrow \gamma \in P[/math] включить [math][B \rightarrow \cdot \gamma, 0][/math] в [math]I_0[/math].
Построение [math]I_j[/math] по [math]I_0, I_1, ..., I_{j-1}[/math].
Шаг 4. Для каждой ситуации [math][B \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}[/math], где [math]a_j[/math] — j-й символ в [math]\omega[/math], включить [math][B \rightarrow \alpha a_{j} \cdot \beta, i] [/math] в [math]I_j[/math].
Пока можно включить новые ситуации в [math]I_j[/math] повторяем шаги 5 и 6.
Шаг 5. Если [math][A \rightarrow \alpha \cdot , i] \in I_j[/math], то для каждой ситуации [math][B \rightarrow \gamma \cdot A \beta, k] \in I_{i}[/math] включить [math][B \rightarrow \gamma A \cdot \beta, k][/math] в [math]I_j[/math].
Шаг 6. Для всех [math][A \rightarrow \alpha \cdot B \beta, i] \in I_j[/math], для всех [math]\gamma[/math] таких, что [math]B \rightarrow \gamma \in P[/math] включить [math][B \rightarrow \cdot \gamma, j][/math] в [math]I_j[/math].


Если [math][S \rightarrow \alpha \cdot, 0] \in I_n[/math], то [math]\omega \in L(G) [/math].


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

Теорема:
[math][A \rightarrow \alpha \cdot \beta, i] \in I_{j} \Leftrightarrow \alpha \Rightarrow^* a_{i+1}...a_{j}[/math] и [math] \mathcal {9} \gamma [/math] и [math] \delta[/math] такие, что [math]S \Rightarrow^* \gamma A \delta[/math] и [math] \gamma \Rightarrow^* a_1...a_{i}[/math]
Доказательство:
[math]\triangleright[/math]

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

1. Пусть включаем по правилу 4
Тогда [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' = 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][/math] утверждение верно.

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

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


[math]\Leftarrow[/math]
Для всех наборов [math]\tau = {\alpha, \beta, \gamma, \delta, A, i , j} [/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 B \beta, i] \in I_{j}[/math].

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

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

1. [math]\alpha[/math] оканчивается терминалом
[math]\alpha = \alpha' a[/math]. [math]\alpha \Rightarrow^*a_{i+1}...a_{j}[/math], значит [math]a = a_{j}[/math]. Рассмотрим набор [math]\tau' = \mathcal {f} \alpha', a_{j} \beta, \gamma, \delta, A, i, j-1 \mathcal {g} [/math]. [math]A \rightarrow \alpha' a_{j} \beta \in P[/math], следовательно ранг [math]\tau'[/math] равен [math]r - 2[/math], так как [math]\tau_{1}(\tau) = \tau_1(\tau'), \tau_2(\tau) = \tau_2(\tau'), \tau_{3}(\tau) = \tau_3(\tau')[/math]. Значит по и.п. [math][A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math], по правилу 4 получаем, что [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/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' = \mathcal {f} \alpha', B \beta, \gamma, \delta, A, i, k \mathcal {g} [/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'' = \mathcal {f} \eta, \varepsilon, \gamma \alpha', \beta \delta, B, k, j \mathcal {g} [/math]. [math]S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta[/math], следовательно [math]\tau_1(\tau'') \leqslant \tau_1(\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_3(\tau) = n_1 + n_2[/math]. Так как [math] B \Rightarrow \eta \Rightarrow^* a_{k+1}...a_{j}[/math], то [math]\tau_3(\tau'') = n_2 - 1[/math]. Очевидно, что [math]\tau_2(\tau'') = \tau_2(\tau) + n_1[/math]. Тогда ранг [math]\tau''[/math] равен [math]\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)[/math] [math]= \tau_1(\tau) - 1 + 2(\tau_2(\tau) + \tau_3(\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] по правилу 4 или 5 [math][A \rightarrow \alpha \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].

3. [math]\alpha[/math] является пустой

[math]\alpha = \varepsilon[/math], значит [math]i = j, \tau_3(\tau) = 0[/math].
Если [math] \tau_1(\tau) = 0[/math], то [math] \gamma = \varepsilon[/math], следовательно [math] \tau_2(\tau) = 0, i = 0 [/math], откуда [math] r = 0[/math], а по и.п. [math]r \gt 0[/math]. Значит [math] \tau_1(\tau) \neq 0[/math]. Тогда [math] \mathcal {9} B, \gamma', \gamma'', \delta', \delta''[/math] такие, что [math]S \Rightarrow^* \gamma' B \delta' \Rightarrow \gamma' \gamma'' A \delta' \delta''[/math], где [math]B = \gamma'' A \delta'' \in P[/math]. Рассмотрим набор [math]\tau' = \mathcal {f} \gamma'', A \delta'', \gamma', \delta', B, k, j \mathcal {g} [/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_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[/math]. Следовательно ранг [math]\tau'[/math] равен [math]r - 1[/math]. Значит по и.п. [math][B \rightarrow \gamma'' \cdot A \delta'', k] \in I_{j}[/math], следовательно по правилу 6 [math][A \rightarrow \cdot \beta, i] [/math] будет добавлена в [math]I_{j}[/math].
[math]\triangleleft[/math]

Пример

Рассмотрим грамматику [math]G[/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]\omega = (a + a)[/math] список разбора.


[math]I_0[/math]
[math][S \rightarrow \cdot T + S, 0][/math] — из правила 1
[math][S \rightarrow \cdot T, 0][/math] — из правила 1
[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][S \rightarrow \cdot a, 0][/math] — из правила 3


[math]I_1[/math]
[math][F \rightarrow ( \cdot S ), 0][/math] — из правила 4
[math][S \rightarrow \cdot T + S, 1][/math] — из правила 6
[math][S \rightarrow \cdot T, 1][/math] — из правила 6
[math][T \rightarrow \cdot F * T, 1][/math] — из правила 6
[math][T \rightarrow \cdot F, 1][/math] — из правила 6
[math][F \rightarrow \cdot ( S ), 1][/math] — из правила 6
[math][F \rightarrow \cdot a, 1][/math] — из правила 6


[math]I_2[/math]
[math][F \rightarrow a \cdot, 1][/math] — из правила 4
[math][T \rightarrow F \cdot * T, 1][/math] — из правила 5
[math][T \rightarrow F \cdot , 1][/math] — из правила 5
[math][S \rightarrow T \cdot , 1][/math] — из правила 5
[math][S \rightarrow T \cdot + S, 1][/math] — из правила 5
[math][F \rightarrow ( S \cdot ), 0][/math] — из правила 5


[math]I_3[/math]
[math][S \rightarrow T + \cdot S, 1][/math] — из правила 4
[math][S \rightarrow \cdot T + S, 3][/math] — из правила 6
[math][S \rightarrow \cdot T, 3][/math] — из правила 6
[math][T \rightarrow \cdot F * T, 3][/math] — из правила 6
[math][T \rightarrow \cdot F, 3][/math] — из правила 6
[math][F \rightarrow \cdot ( S ), 3][/math] — из правила 6
[math][F \rightarrow \cdot a, 3][/math] — из правила 6


[math]I_4[/math]
[math][F \rightarrow a \cdot , 3][/math] — из правила 4
[math][T \rightarrow F \cdot * T, 3][/math] — из правила 5
[math][T \rightarrow F \cdot , 3][/math] — из правила 5
[math][S \rightarrow T \cdot + S, 3][/math] — из правила 5
[math][S \rightarrow T \cdot , 3][/math] — из правила 5
[math][S \rightarrow T + S \cdot , 1][/math] — из правила 5
[math][F \rightarrow ( S \cdot ), 0][/math] — из правила 5


[math]I_5[/math]
[math][F \rightarrow ( S )\cdot , 0][/math] — из правила 4
[math][T \rightarrow F \cdot * T, 0][/math] — из правила 5
[math][T \rightarrow F \cdot , 0][/math] — из правила 5
[math][S \rightarrow T \cdot + S, 0][/math] — из правила 5
[math][S \rightarrow T \cdot , 0][/math] — из правила 5


Так как [math][S \rightarrow T \cdot , 0] \in I_5[/math], то [math]\omega \in L(G) [/math].

Литература

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