Warum kann ein Recursive-Descent-Parser keine linke Rekursion behandeln?

Question

Könnte mir bitte jemand erklären, warum Recursive-Descent-Parser nicht mit einer Grammatik arbeiten können, die Linksrekursion enthält?

Answer 1

betrachten:

A ::= A B 

der entsprechende Code

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

ist die unendliche Rekursion sehen?

Answer 2

Denn wer interessiert

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

kann wie folgt umgeschrieben werden:

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

Die allgemeine Form der Transformation ist: eine der nicht links rekursive Disjunktionen von einer beliebigen Anzahl von links gefolgt Rekursive Disjunkte ohne das erste Element.

Die Reform des Action-Code ist ein bisschen Trickery, aber ich denke, dass Plug-n-Tuck auch sein kann.