Изменения
Нет описания правки
}}
Опишем процедуру, устраняющую все правила вида <tex>A \rightarrow A\alpha</tex> для фиксированного нетерминала <tex>A</tex>.
</ol>
Пусть множество всех нетерминалов <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex>
<div>
*<tex>B_i \rightarrow c \alpha </tex>, где <tex>c</tex> - терминал
*<tex>B_i \rightarrow B_j \alpha </tex>, где <tex>i < j</tex>
Приведем алгоритм, позволяющий для к.с. грамматики ''без <tex> \varepsilon </tex>-правил'' построить эквивалентную ей к.с. грамматику (без <tex> \varepsilon </tex>-правил), не содержащую левой рекурсии.
==Алгоритм устранения левой рекурсии==
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:
#Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>
#Воспользоваться алгоритмом устранения произвольной левой рекурсии
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
