Изменения

Перейти к: навигация, поиск

Удаление eps-правил из грамматики

2 байта добавлено, 03:02, 23 ноября 2011
м
Поиск ε-порождающих нетерминалов
# Построить граф <tex>Gr = \langle V = N, E = \mathcal {f} (A, B) | A \rightarrow \alpha B \beta \mathcal {g}\rangle</tex>, где <tex>\alpha, \beta</tex> состоят из нетерминалов.
# Пометить все нетерминалы, из которых непосредственно можно вывести <tex>\mathcal {f} \varepsilon \mathcal {g}</tex>, как <tex>\varepsilon</tex>-порождающие.
# Обойти граф <tex>Gr</tex> в глубину. Если для нетерминала <tex>A</tex> верно, что все его соседи <tex>\varepsilon</tex>-порождающие нетерминалы, и при этом эти нетеминалы принаджедат нетерминалы принадлежат одному правилу, то пометить нетерминал <tex>A</tex>, как <tex>\varepsilon</tex>-порождающий.
{{Теорема
205
правок

Навигация