Изменения
Нет описания правки
==Определения==
{{Определение
|definition =
<i>Шаг 5.</i> Если <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>, то для каждой ситуации <tex>[B \rightarrow \gamma \cdot A \beta, k] \in I_{i}</tex> включить <tex>[B \rightarrow \gamma A \cdot \beta, k]</tex> в <tex>I_j</tex>.<br>
<i>Шаг 6.</i> Для всех <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>, для всех <tex>\gamma</tex> таких, что <tex>B \rightarrow \gamma \in P</tex> включить <tex>[B \rightarrow \cdot \gamma, j]</tex> в <tex>I_j</tex>.<br>
Если <tex>[S \rightarrow \alpha \cdot, 0] \in I_n</tex>, то <tex>\omega \in L(G) </tex>.<br>
==Пример==
Рассмотрим грамматику <tex>G</tex> с правилами: <br>
<tex>S \rightarrow T + S</tex> <br>
<tex>S \rightarrow T </tex> <br>
<tex>T \rightarrow F * T</tex> <br>
<tex>T \rightarrow F</tex> <br>
<tex>F \rightarrow ( S )</tex> <br>
<tex>F \rightarrow a</tex> <br>
Построим для строки <tex>\omega = (a + a)</tex> список разбора.<br>
<b><tex>I_0</tex></b> <br>
<tex>[S \rightarrow \cdot T + S, 0]</tex> — из правила 1 <br>
<tex>[S \rightarrow \cdot T, 0]</tex> — из правила 1 <br>
<tex>[T \rightarrow \cdot F * T, 0]</tex> — из правила 3 <br><tex>[T \rightarrow \cdot F, 0]</tex> — из правила 3 <br>
<tex>[F \rightarrow \cdot ( S ), 0]</tex> — из правила 3 <br>
<tex>[S \rightarrow \cdot a, 0]</tex> — из правила 3 <br>
<b><tex>I_1</tex></b> <br>
<tex>[F \rightarrow ( \cdot S ), 0]</tex> — из правила 4 <br>
<tex>[S \rightarrow \cdot T + S, 1]</tex> — из правила 6 <br>
<tex>[S \rightarrow \cdot T, 1]</tex> — из правила 6 <br>
<tex>[T \rightarrow \cdot F * T, 1]</tex> — из правила 6 <br>
<tex>[T \rightarrow \cdot F, 1]</tex> — из правила 6 <br>
<tex>[F \rightarrow \cdot ( S ), 1]</tex> — из правила 6 <br>
<tex>[F \rightarrow \cdot a, 1]</tex> — из правила 6 <br>
<b><tex>I_2</tex></b> <br>
<tex>[F \rightarrow a \cdot, 1]</tex> — из правила 4 <br>
<tex>[T \rightarrow F \cdot * T, 1]</tex> — из правила 5 <br>
<tex>[T \rightarrow F \cdot , 1]</tex> — из правила 5<br>
<tex>[S \rightarrow T \cdot , 1]</tex> — из правила 5 <br>
<tex>[S \rightarrow T \cdot + S, 1]</tex> — из правила 5 <br>
<tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 5 <br>
<b><tex>I_3</tex></b> <br>
<tex>[S \rightarrow T + \cdot S, 1]</tex> — из правила 4 <br>
<tex>[S \rightarrow \cdot T + S, 3]</tex> — из правила 6 <br>
<tex>[S \rightarrow \cdot T, 3]</tex> — из правила 6<br>
<tex>[T \rightarrow \cdot F * T, 3]</tex> — из правила 6 <br>
<tex>[T \rightarrow \cdot F, 3]</tex> — из правила 6 <br>
<tex>[F \rightarrow \cdot ( S ), 3]</tex> — из правила 6 <br>
<tex>[F \rightarrow \cdot a, 3]</tex> — из правила 6 <br>
<b><tex>I_4</tex></b> <br>
<tex>[F \rightarrow a \cdot , 3]</tex> — из правила 4 <br>
<tex>[T \rightarrow F \cdot * T, 3]</tex> — из правила 5 <br>
<tex>[T \rightarrow F \cdot , 3]</tex> — из правила 5<br>
<tex>[S \rightarrow T \cdot + S, 3]</tex> — из правила 5 <br>
<tex>[S \rightarrow T \cdot , 3]</tex> — из правила 5 <br>
<tex>[S \rightarrow T + S \cdot , 1]</tex> — из правила 5 <br>
<tex>[F \rightarrow ( S \cdot ), 0]</tex> — из правила 5 <br>
<b><tex>I_5</tex></b> <br>
<tex>[F \rightarrow ( S )\cdot , 0]</tex> — из правила 4 <br>
<tex>[T \rightarrow F \cdot * T, 0]</tex> — из правила 5 <br>
<tex>[T \rightarrow F \cdot , 0]</tex> — из правила 5<br>
<tex>[S \rightarrow T \cdot + S, 0]</tex> — из правила 5 <br>
<tex>[S \rightarrow T \cdot , 0]</tex> — из правила 5 <br>
Так как <tex>[S \rightarrow T \cdot , 0] \in I_5</tex>, то <tex>\omega \in L(G) </tex>.<br>
==Корректность алгоритма==
