Почему парсер рекурсивного спуска не может обработать рекурсию

Question

Может кто-нибудь объяснить мне, почему парсеры рекурсивного спуска не могут работать с грамматикой, содержащей левую рекурсию?

Answer 1

рассмотреть следующие вопросы:

A ::= A B

эквивалентный код

boolean A() {
    if (A()) {
        return B();
    }
    return false;
}

видите бесконечную рекурсию?

Answer 2

Для тех, кто заинтересован

 A ::= A B | A C | D | E

можно переписать как:

 A ::= (D | E) (B | C)*

Общая форма преобразования такова: любой из не левосторонних рекурсивных дизъюнктов, за которым следует любое количество левых рекурсивных дизъюнктов без первого элемента.

Реформировать код действия немного хитро, но я думаю, что это может быть и плагином.