Prenderò una pugnalata nel metterlo in parole povere.
Se si pensa in termini di albero di analisi (non dell'AST, ma della visita del parser e dell'espansione dell'input), i risultati della ricorsione vengono lasciati in un albero che cresce a sinistra e in basso. La ricorsione giusta è esattamente l'opposto.
Ad esempio, una grammatica comune in un compilatore è una lista di elementi. Consente di prendere un elenco di stringhe ("rosso", "verde", "blu") e analizzarlo. Potrei scrivere la grammatica in alcuni modi. I seguenti esempi sono rispettivamente ricorsivi a destra oa sinistra rispettivamente:
arg_list: arg_list:
STRING STRING
| arg_list ',' STRING | STRING ',' arg_list
Gli alberi per queste analisi:
(arg_list) (arg_list)
/ \ / \
(arg_list) BLUE RED (arg_list)
/ \ / \
(arg_list) GREEN GREEN (arg_list)
/ /
RED BLUE
Nota come cresce nella direzione della ricorsione.
Questo non è davvero un problema, va bene scrivere una grammatica ricorsiva a sinistra ... se il tuo parser può gestirlo. I parser dal basso lo gestiscono bene. Così possono più parser LL moderni. Il problema con le grammatiche ricorsive non è la ricorsione, è la ricorsione senza far avanzare il parser o, ricorrendo senza consumare un token. Se consumiamo sempre almeno 1 gettone quando ricontiamo, alla fine raggiungiamo la fine dell'analisi. La ricorsione sinistra è definita come recursing senza consumo, che è un loop infinito.
Questa limitazione è puramente un dettaglio di implementazione dell'implementazione di una grammatica con un parser LL top-down ingenuo (parser di discendenza ricorsiva). Se si vuole attenersi alle grammatiche ricorsive di sinistra, è possibile gestirlo riscrivendo la produzione per consumare almeno 1 token prima di ricorrere, quindi questo ci assicura di non rimanere mai bloccati nel ciclo non produttivo. Per ogni regola grammaticale che è ricorsiva a sinistra, possiamo riscriverla aggiungendo una regola intermedia che appiattisce la grammatica ad un solo livello di lookahead, consumando un token tra le produzioni ricorsive. (NOTA: Non sto dicendo che questo è l'unico modo o il modo preferito per riscrivere la grammatica, sottolineando semplicemente la regola generalizzata.IN questo semplice esempio, l'opzione migliore è usare la forma ricorsiva destra). Poiché questo approccio è generalizzato, un generatore di parser può implementarlo senza coinvolgere il programmatore (in teoria). In pratica, credo che ANTLR 4 ora faccia proprio questo.
Per la grammatica di cui sopra, l'implementazione LL che mostra la ricorsione a sinistra sarebbe simile a questa. Il parser inizierà con la previsione di un elenco ...
bool match_list()
{
if(lookahead-predicts-something-besides-comma) {
match_STRING();
} else if(lookahead-is-comma) {
match_list(); // left-recursion, infinite loop/stack overflow
match(',');
match_STRING();
} else {
throw new ParseException();
}
}
In realtà, ciò di cui stiamo veramente parlando è "l'implementazione ingenua", vale a dire. inizialmente abbiamo previsto una determinata frase, quindi chiamata ricorsivamente la funzione per quella predizione, e quella funzione chiama di nuovo la stessa predizione di nuovo.
I parser bottom-up non hanno il problema delle regole ricorsive in entrambe le direzioni, perché non ripetono l'inizio di una frase, lavorano rimettendo insieme la frase.
La ricorsione in una grammatica è solo un problema se produciamo dall'alto verso il basso, cioè. il nostro parser funziona "espandendo" le nostre previsioni mentre consumiamo i token. Se invece di espanderci, collassiamo (le produzioni sono "ridotte"), come in un parser bottom-up LALR (Yacc / Bison), quindi la ricorsione di entrambi i lati non è un problema.