38
правок
Изменения
Нет описания правки
<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>Строим <tex>I_0</tex><br><i>Шаг 1.</i> Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>.<br>Выполняем шаги 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>
