Analyzátor rekurzivního sestupu - Recursive descent parser

Ve výpočetní techniky , je rekurzivní sestup analyzátor je druh shora dolů analyzátor postavený ze sady vzájemně rekurzivní postupů (nebo non-rekurzivní ekvivalentu), kde každý takový postup provádí jednu z nonterminálů z gramatiky . Struktura výsledného programu tedy úzce odráží strukturu rozpoznávané gramatiky.

Prediktivní parser je rekurzivní sestup analyzátor, který nevyžaduje ústupek . Prediktivní analýza je možná pouze pro třídu LL ( k ) gramatik, což jsou bezkontextové gramatiky, pro které existuje kladné celé číslo k, které umožňuje syntaktickému analyzátoru sestupu rozhodnout, kterou produkci použít, zkoumáním pouze následujících k tokenů k vstup. Gramatiky LL ( k ) proto vylučují všechny nejednoznačné gramatiky i všechny gramatiky, které obsahují levou rekurzi . Libovolnou bezkontextovou gramatiku lze transformovat na ekvivalentní gramatiku, která nemá levou rekurzi, ale odstranění levé rekurze ne vždy přináší gramatiku LL ( k ). Prediktivní analyzátor běží v lineárním čase .

Rekurzivní sestup se zpětným sledováním je technika, která určuje, kterou produkci použít, a to postupně zkoušením každé produkce. Rekurzivní sestup se zpětným sledováním není omezen na gramatiky LL ( k ), ale není zaručeno jeho ukončení, pokud gramatika není LL ( k ). I když se ukončí, analyzátory, které používají rekurzivní sestup se zpětným sledováním, mohou vyžadovat exponenciální čas .

Ačkoli jsou prediktivní analyzátory široce používány a jsou často vybírány při ručním psaní syntaktického analyzátoru, programátoři často upřednostňují použití syntaktického analyzátoru založeného na tabulkách vytvořeného generátorem syntaktického analyzátoru , a to buď pro jazyk LL ( k ), nebo pomocí alternativního syntaktického analyzátoru, například LALR nebo LR . To platí zejména v případě, že gramatika není ve formě LL ( k ) , protože jde o transformaci gramatiky na LL, aby byla vhodná pro prediktivní analýzu. Prediktivní analyzátory lze také generovat automaticky pomocí nástrojů, jako je ANTLR .

Prediktivní parsery lze zobrazit pomocí přechodových diagramů pro každý nekoncový symbol, kde jsou okraje mezi počátečním a konečným stavem označeny symboly (terminály a nekoncové) na pravé straně produkčního pravidla.

Příklad analyzátoru

Následující EBNF like gramatiky (pro Niklaus Wirth je PL / 0 programovacího jazyka, z Algoritmy + datové struktury = Programy ) je v LL (1) tvaru: 

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

Terminály jsou vyjádřeny v uvozovkách. Každý neterminál je definován pravidlem v gramatice, kromě ident a number , u nichž se předpokládá, že jsou implicitně definovány.

C implementace

Co bude následovat, je implementace rekurzivní sestup analyzátor při výše jazyka C . Analyzátor načte zdrojový kód a ukončí se chybovou zprávou, pokud se kód nepodaří analyzovat. Pokud kód správně analyzuje, ukončí se tiše.

Všimněte si, jak blízko prediktivní analyzátor níže zrcadlí gramatiku výše. V gramatice je postup pro každého neterminálu. Parsování sestupuje způsobem shora dolů, dokud nebude zpracován konečný neterminál. Fragment programu závisí na globální proměnné sym , která obsahuje aktuální symbol ze vstupu, a funkci nextsym , která při volání aktualizuje sym .

Implementace funkcí nextsym a error jsou pro jednoduchost vynechány. 

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

Příklady

Některé generátory syntaktického analyzátoru rekurzivního sestupu:

Viz také

Reference

Obecné odkazy

externí odkazy