Rekursiv nedstigningsparser - Recursive descent parser

I datalogi , en rekursiv afstamning parser er en slags top-down parser bygget fra et sæt af gensidigt rekursive procedurer (eller en ikke-rekursiv tilsvarende), hvor hver sådan procedure redskaber en af nonterminals af grammatik . Således afspejler strukturen i det resulterende program tæt den grammatik, den genkender.

En prædiktiv parser er en recursiv afstamningsparser, der ikke kræver backtracking . Prediktiv parsing er kun mulig for klassen af LL ( k ) -grammatikker, som er de kontekstfrie grammatikker, for hvilke der findes noget positivt heltal k, der gør det muligt for en rekursiv nedstigningsparser at beslutte, hvilken produktion der skal bruges ved kun at undersøge de næste k- tokens af input. LL ( k ) -grammatikkerne udelukker derfor alle tvetydige grammatikker såvel som alle grammatikker, der indeholder venstre rekursion . Enhver kontekstfri grammatik kan omdannes til en ækvivalent grammatik, der ikke har nogen venstre rekursion, men fjernelse af venstre rekursion giver ikke altid en LL ( k ) grammatik. En forudsigende parser kører i lineær tid .

Rekursiv afstamning med backtracking er en teknik, der bestemmer hvilken produktion der skal bruges ved at prøve hver produktion igen. Rekursiv afstamning med backtracking er ikke begrænset til LL ( k ) grammatik, men garanteres ikke at ophøre, medmindre grammatikken er LL ( k ). Selv når de ophører, kan parsere, der bruger rekursiv afstamning med backtracking, kræve eksponentiel tid .

Selvom prædiktive parsere bruges i vid udstrækning og ofte vælges, hvis de skriver en parser manuelt, foretrækker programmører ofte at bruge en tabelbaseret parser produceret af en parsergenerator , enten til et LL ( k ) -sprog eller ved at bruge en alternativ parser, såsom LALR eller LR . Dette er især tilfældet, hvis en grammatik ikke er i form af LL ( k ) , da det er involveret at omdanne grammatikken til LL for at gøre den egnet til forudsigelig parsing. Prediktive parsere kan også genereres automatisk ved hjælp af værktøjer som ANTLR .

Prediktive parsere kan afbildes ved hjælp af overgangsdiagrammer for hvert ikke-terminale symbol, hvor kanterne mellem den indledende og den endelige tilstand er mærket med symbolerne (terminaler og ikke-terminaler) på højre side af produktionsreglen.

Eksempel parser

Følgende EBNF lignende grammatik (for Niklaus Wirth 's PL / 0 programmeringssprog, fra Algoritmer + datastrukturer = Programmer ) er i LL (1) formular: 

 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 ")" .

Terminaler udtrykkes i tilbud. Hver ikke-terminal er defineret af en regel i grammatikken bortset fra ident og nummer , der antages at være implicit defineret.

C implementering

Hvad der følger er en implementering af en rekursiv afstamning parser for ovenstående sprog i C . Parseren læser i kildekoden og afsluttes med en fejlmeddelelse, hvis koden ikke parser, og afsluttes lydløst, hvis koden analyseres korrekt.

Bemærk, hvor tæt den forudsigende parser nedenfor afspejler grammatikken ovenfor. Der er en procedure for hver ikke-terminal i grammatikken. Parsing falder ned fra top-down måde, indtil den sidste ikke-terminal er behandlet. Programfragmentet afhænger af en global variabel, sym , som indeholder det aktuelle symbol fra input, og funktionen nextsym , der opdaterer sym, når der kaldes på.

Implementeringerne af funktionerne nextsym og error udelades for enkelhedens skyld. 

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);
}

Eksempler

Nogle rekursive parsergeneratorer:

Se også

Referencer

Generelle referencer

eksterne links