为什么递归下降解析器不能处理左递归

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)*

转换的一般形式是:任何一个非左递归析取,后跟任何数量的左递归析取而没有第一个元素.

改变动作代码有点诡计,但我的事情也可以插件.