228
правок
Изменения
→Алгоритм устранения произвольной левой рекурсии
==Алгоритм устранения произвольной левой рекурсии==
Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.
<div>
for все нетерминалы <tex>A_i</tex>
Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.
Алгоритм не работает для грамматик с <tex>\varepsilon</tex> переходами и с грамматиками имеющими <tex>A \Rightarrow^+ A</tex>. Поэтому для произвольной грамматики необходимо сначала воспользоваться алгоритмом [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]].
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.
===Пример===
<tex>A_1 \to 0 | 1</tex>
<tex>A_{i+1} \to {A_i}0</tex> для <tex>1 \leq i < n</tex>
==Пример==
