Изменения

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

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

32 байта убрано, 17:17, 17 января 2016
подвинул содержание, удалил "постановку задачи"
__TOC__
{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (англ. ''direct left recursion''), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
== Постановка задачи ==
[[Методы трансляции#Нисходящий разбор|Методы нисходящего разбора]] не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
54
правки

Навигация