228
правок
Изменения
Нет описания правки
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию(left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}
Методы нисходящего разбора (top=down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, поэтому который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
Левая рекурсия может быть:
* непосредственной(immidiate)
<tex>A \Rightarrow A\alpha</tex>
* произвольной(indirect)
<tex>A_0 \rightarrow A_1\alpha</tex>
<tex>A_1 \rightarrow A_0\alpha</tex>
==Устранение непосредственной левой рекурсии==
</ol>
Этот алгоритм не устраняет произвольную левую рекурсию,вызванную двумя или более шагами порождения.
===Пример===
