26
правок
Изменения
м
→Алгоритм устранения левой рекурсии
Приведем алгоритм, позволяющий для к.с. грамматики '''без ε-правил''' построить эквивалентную ей к.с. грамматику (без ε-правил), не содержащую левой рекурсии.
Для произвольной грамматики <tex>\Gamma</tex> левую рекурсию можно устранить следующим образом:#воспользоваться Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления ε-правил]]. Получим грамматику без ε-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>#воспользоваться Воспользоваться алгоритмом для новой грамматики
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>
===Устранение непосредственной левой рекурсии===
