爲什麼不能遞歸下降解析器處理左遞歸

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以及。