38
правок
Изменения
Новая страница: «{{Определение |definition = Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omeg…»
{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <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>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}
{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим <b>список ситуаций</b> <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \beta \cdot , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}
{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>\omega</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>
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <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>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}
{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим <b>список ситуаций</b> <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \beta \cdot , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}
{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется <b>списком разбора</b> для входной цепочки <tex>\omega</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>
