Изменения

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

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

4 байта добавлено, 14:45, 7 января 2013
Нет описания правки
{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная(КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''', если она содержит правило вида <tex>A \Rightarrow A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию(left recursion)''', если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}
Методы нисходящего разбора(top-down parsers) не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.
<tex>A \Rightarrow S\alpha </tex>
 
<tex>S \Rightarrow S\beta | A\gamma | b</tex>
228
правок

Навигация