Analizzatore di discesa ricorsivo - Recursive descent parser

In informatica , un parser a discesa ricorsiva è una sorta di parser top-down costruito da un insieme di procedure reciprocamente ricorsive (o un equivalente non ricorsivo) in cui ciascuna di tali procedure implementa uno dei non terminali della grammatica . Quindi la struttura del programma risultante rispecchia da vicino quella della grammatica che riconosce.

Un parser predittivo è un parser discendente ricorsivo che non richiede il backtracking . L'analisi predittiva è possibile solo per la classe di grammatiche LL ( k ) , che sono le grammatiche prive di contesto per le quali esiste un intero positivo k che consente a un parser discendente ricorsivo di decidere quale produzione usare esaminando solo i successivi k token di ingresso. Le grammatiche LL ( k ) escludono quindi tutte le grammatiche ambigue , nonché tutte le grammatiche che contengono la ricorsione a sinistra . Qualsiasi grammatica libera dal contesto può essere trasformata in una grammatica equivalente che non ha ricorsione a sinistra, ma la rimozione della ricorsione a sinistra non sempre produce una grammatica LL ( k ). Un parser predittivo viene eseguito in tempo lineare .

La discesa ricorsiva con backtracking è una tecnica che determina quale produzione utilizzare provando a turno ciascuna produzione. La discesa ricorsiva con backtracking non è limitata alle grammatiche LL ( k ), ma non è garantito che termini a meno che la grammatica non sia LL ( k ). Anche quando terminano, i parser che utilizzano la discesa ricorsiva con backtracking possono richiedere tempo esponenziale .

Sebbene i parser predittivi siano ampiamente utilizzati e siano spesso scelti se si scrive un parser a mano, i programmatori spesso preferiscono utilizzare un parser basato su tabella prodotto da un generatore di parser , sia per un linguaggio LL ( k ) o utilizzando un parser alternativo, come LALR o LR . Questo è particolarmente vero se una grammatica non è in forma LL ( k ) , poiché è coinvolta la trasformazione della grammatica in LL per renderla adatta all'analisi predittiva. I parser predittivi possono anche essere generati automaticamente, utilizzando strumenti come ANTLR .

I parser predittivi possono essere rappresentati utilizzando diagrammi di transizione per ciascun simbolo non terminale in cui i bordi tra lo stato iniziale e quello finale sono etichettati dai simboli (terminali e non terminali) del lato destro della regola di produzione.

Parser di esempio

Il seguente EBNF -come grammatica (per Niklaus Wirth s' PL / 0 linguaggio di programmazione, dalle strutture Algoritmi + Dati = Programmi ) è in LL (1) modulo: 

 program = block "." .
 
 block =
     ["const" ident "=" num {"," ident "=" num} ";"]
     ["var" ident {"," ident} ";"]
     {"procedure" ident ";" block ";"} statement .
 
 statement =
     ident ":=" expression
     | "call" ident
     | "begin" statement {";" statement } "end"
     | "if" condition "then" statement
     | "while" condition "do" statement .
 
 condition =
     "odd" expression
     | expression ("="|"#"|"<"|"<="|">"|">=") expression .
 
 expression = ["+"|"-"] term {("+"|"-") term} .
 
 term = factor {("*"|"/") factor} .
 
 factor =
     ident
     | number
     | "(" expression ")" .

I terminali sono espressi tra virgolette. Ogni non terminale è definito da una regola nella grammatica, ad eccezione di ident e number , che si presume siano definiti implicitamente.

Implementazione C.

Quello che segue è l'implementazione di un parser discesa ricorsiva per il linguaggio sopra C . Il parser legge il codice sorgente ed esce con un messaggio di errore se il codice non riesce ad analizzare, chiudendosi silenziosamente se il codice viene analizzato correttamente.

Nota quanto il parser predittivo sotto rispecchi la grammatica sopra. C'è una procedura per ogni non terminale nella grammatica. L'analisi discende dall'alto verso il basso, finché non è stato elaborato il non terminale finale. Il frammento di programma dipende da una variabile globale, sym , che contiene il simbolo corrente dall'input, e dalla funzione nextsym , che aggiorna sym quando viene chiamata.

Le implementazioni delle funzioni nextsym ed error sono omesse per semplicità. 

typedef enum {ident, number, lparen, rparen, times, slash, plus,
    minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,
    endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,
    varsym, procsym, period, oddsym} Symbol;

Symbol sym;
void nextsym(void);
void error(const char msg[]);

int accept(Symbol s) {
    if (sym == s) {
        nextsym();
        return 1;
    }
    return 0;
}

int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}

void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        nextsym();
    }
}

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        nextsym();
        factor();
    }
}

void expression(void) {
    if (sym == plus || sym == minus)
        nextsym();
    term();
    while (sym == plus || sym == minus) {
        nextsym();
        term();
    }
}

void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {
            nextsym();
            expression();
        } else {
            error("condition: invalid operator");
            nextsym();
        }
    }
}

void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    } else {
        error("statement: syntax error");
        nextsym();
    }
}

void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}

void program(void) {
    nextsym();
    block();
    expect(period);
}

Esempi

Alcuni generatori di parser a discesa ricorsiva:

Guarda anche

Riferimenti

Riferimenti generali

link esterno