Изменения

Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем <b>ситуацией</b>, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex> — позиция в <tex>\omega</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.

 <b>Вход.</b> контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>.<br><b>Выход.</b> Список Построим список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>.<br><b>Метод.</b><br>

<i>Шаг 1.</i> Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>\in P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>.<br>Выполняем шаги 2 и 3 до тех пор, пока можем включать Пока можно включить новые ситуации в <tex>I_0</tex>повторяем шаги 2 и 3.<br><i>Шаг 2.</i> Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих из <tex>I_0</tex>.<br><i>Шаг 3.</i> Допустим, что Для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из , для всех <tex>P\gamma</tex> вида таких, что <tex>B \rightarrow \gamma\in P</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там)в <tex>I_0</tex>.<br>

<i>Шаг 4.</i> Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a a_{j} \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить — j-й символ в <tex>I_j\omega</tex> ситуацию включить <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex> в <tex>I_j</tex>.<br>Выполняем шаги 5 и 6 до тех пор, пока можем включать Пока можно включить новые ситуации в <tex>I_j</tex>повторяем шаги 5 и 6.<br><i>Шаг 5.</i> Пусть Если <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем , то для каждой ситуации вида <tex>[B \rightarrow \gamma \cdot A \deltabeta, k]\in I_{i}</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \gamma A \cdot \deltabeta, k]</tex> в <tex>I_j</tex>.<br><i>Шаг 6.</i> Пусть Для всех <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого , для всех <tex>B \rightarrow \gamma</tex> из таких, что <tex>B \rightarrow \gamma \in P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>.<br>Вычисляем все в <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>.<br>Если <tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>., то <tex>\omega \in L(G) <br/tex>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 4.'''&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 5.'''&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''Шаг 6.'''<br>[[Файл:Эрли2.png]] [[Файл:Эрли1.png]] [[Файл:Эрли3.png]]