Dlaczego parser rekursywno-potomny nie może obsługiwać lewej rekursji

Question

Czy ktoś mógłby mi wyjaśnić, dlaczego parsery rekursywno-opadowe nie mogą pracować z gramatyką zawierającą lewą rekursję?

Answer 1

rozważenia:

A ::= A B 

odpowiednik kod jest

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

zobaczyć nieskończoną rekurencję?

Answer 2

dla tego, kto jest zainteresowany

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

może być zapisane jako:

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

Ogólna postać przemiana: każdy jeden z nie lewej disjuncts rekurencyjnych następuje dowolny numer lewej rekursywne disjunkty bez pierwszego elementu.

Reformowanie kodu akcji jest trochę podstępne, ale ja też mogę być plug-n-chug.