In parole povere, cos'è la ricorsione sinistra?

8

In base alla una pagina su code.google.com, la "ricorsione sinistra" è definita come segue :

Left recursion just refers to any recursive nonterminal that, when it produces a sentential form containing itself, that new copy of itself appears on the left of the production rule.

Wikipedia offre due diverse definizioni:

  1. In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.

  2. "A grammar is left-recursive if we can find some non-terminal A which will eventually derive a sentential form with itself as the left-symbol."

Sto appena iniziando con la creazione del linguaggio qui, e lo sto facendo nel mio tempo libero. Tuttavia, quando si tratta di selezionare un parser della lingua, se la ricorsione sinistra è supportata da questo parser o che il parser è un problema che immediatamente viene visualizzato in primo piano. Cercare termini come "forma sentimentale" porta solo a ulteriori elenchi di termini tecnici, ma la distinzione della ricorsione "di sinistra" deve essere qualcosa di molto semplice. Traduzione per favore?

    
posta Panzercrisis 05.09.2014 - 05:00
fonte

2 risposte

16

Una regola R è left-ricorsiva se, per scoprire se R corrisponde, devi prima scoprire se R corrisponde. Questo accade quando R appare, direttamente o indirettamente, come il primo termine in qualche produzione di se stesso.

Immagina una versione giocattolo della grammatica per le espressioni matematiche, con solo addizione e moltiplicazione per evitare distrazioni:

Expression ::= Multiplication '+' Expression
            || Multiplication

Multiplication ::= Term '*' Term
                 || Term

Term ::= Number | Variable

Come scritto, non c'è ricorsione a sinistra qui - potremmo passare questa grammatica ad un parser ricorsivo-discendente.

Supponiamo che tu abbia provato a scrivere in questo modo:

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

Questa è una grammatica e alcuni parser possono farcela, ma i parser di discesa ricorsivi e i parser LL non possono - perché la regola per Expression inizia con Expression stessa. Dovrebbe essere ovvio il motivo per cui in un parser ricorsivo-discendente questo porta alla ricorsione illimitata senza effettivamente consumare alcun input.

Non importa se la regola si riferisce a se stessa direttamente o indirettamente; se A ha un'alternativa che inizia con B , e B ha un'alternativa che inizia con A , quindi A e B sono entrambi indirettamente left-ricorsivi e in un parser ricorsivo-discendente le loro funzioni di corrispondenza porterebbero a una ricorsione reciproca senza fine.

    
risposta data 05.09.2014 - 05:25
fonte
3

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.

    
risposta data 18.09.2014 - 03:42
fonte

Leggi altre domande sui tag