205
правок
Изменения
м
→Алгоритм удаления ε-правил из грамматики
== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S \rangle : </tex> без <tex>\varepsilon</tex>-правил (возможно правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил). <tex>L(G') = L(G) \setminus \lbrace \varepsilon \rbrace</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# Рассмотрим правила вида (*) <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex>, где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*)в <tex>P'</tex>, в которых либо присутствует, либо отсутствует <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось пустое слово <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правила <tex>S' \rightarrow S|\varepsilon</tex>.
