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

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

变换的一般形式是：后跟任意数量的左侧的非左递归析取项中的任一项没有第一个元素的递归分离。

改革行动代码是有点诡计，但我可以插入n-chug以及。