228
правок
Изменения
→Алгоритм устранения произвольной левой рекурсии
==Алгоритм устранения произвольной левой рекурсии==
Упорядочим нетерминалы и будим добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j < i</tex>.
Можно заметить, что если данное условие выполняется для <tex>A_i</tex>, то в грамматике не будет <tex>A_i \Rightarrow^* A_i</tex>, а значит надо будет только устранить непосредственную левую рекурсию для <tex>A_i</tex>.
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
устранить непосредственную левую рекурсию для <tex>A_i</tex>.
</div>
На <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>.
Алгоритм не работает для грамматик с <tex>\varepsilon</tex> переходами и с грамматиками имеющими <tex>A \Rightarrow^+ A</tex>. Поэтому для произвольной грамматики необходимо сначала воспользоваться алгоритмом [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]].
===Асимптотика===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O(\sum\limits_{A_i \to A_j, j < i} a_j) + O(a_i)</tex>, что меньше чем <tex>O(\sum\limits_{i=1}^n a_j)</tex>, значит асимптотика алгоритма <tex>O(n\sum\limits_{i=1}^n a_j)</tex>.
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.
