Изменения

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

Устранение левой рекурсии

155 байт убрано, 21:59, 18 января 2013
Алгоритм устранения произвольной левой рекурсии
Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, | \, \varepsilon </tex>.
На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma | \ldots | \delta_k\gamma</tex> где <tex>A_j \to \delta_1 | \ldots | \delta_k</tex>. Таким образом остается только избавиться от непосредственной рекурсии для <tex>A_i</tex>.Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
Анонимный участник

Навигация