editor
177
правок
Изменения
м
→Алгоритм удаления ε-правил из грамматики
# Добавить все правила из <tex>P</tex> в <tex>P'</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>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>.
