Analýza rekurzivním sestupem

Analýza rekurzivním sestupem (anglicky recursive descent parser) je metoda syntaktické analýzy shora dolů, implementovaná sadou vzájemně rekurzivních procedur (nebo jejich nerekurzivních ekvivalentů), kde každá taková procedura obvykle implementuje jedno z pravidel gramatiky. Výsledná struktura programu zrcadlí strukturu gramatiky, kterou má rozpoznávat.[1]

Prediktivní syntaktický analyzátor je analyzátor s rekurzivním sestupem, který nepoužívá backtracking. Prediktivní syntaktická analýza je možná pouze pro třídu LL(k) gramatik, což jsou bezkontextové gramatiky, pro které existuje nějaké kladné celé číslo k, které umožňuje, aby analyzátor s rekurzivním sestupem rozhodoval, jaké přepisovací pravidlo se má použít, na základě prohlédnutí dalších k symbolů na vstupu. LL(k) gramatiky proto neobsahují žádné nejednoznačné gramatiky, ani gramatiky, které obsahují levou rekurzi. Jakákoli bezkontextová gramatika může být převedena na ekvivalentní gramatiku bez levé rekurze, ale odstranění levé rekurze nedává vždy LL(k) gramatiku. Prediktivní syntaktický analyzátor pracuje v lineárním čase.

Rekurzivní sestup s backtracking je technika, která určuje, jaké přepisovací pravidlo se použije, zkoušením každého přepisovacího pravidla. Rekurzivní sestup s backtrackingem není omezený na LL(k) gramatiky, ale není zaručené, že skončí, pokud gramatika není LL(k). I když analýza skončí, analyzátor, který používá rekurzivní sestup s backtrackingem, může vyžadovat exponenciální čas.

Ačkoli prediktivní syntaktické analyzátory jsou často používány a jsou velmi oblíbené při ruční konstrukci analyzátorů, programátoři často dávají přednost používání analyzátorů vytvořených generátorem syntaktických analyzátorů buď pro LL(k) jazyk nebo pomocí alternativního parseru, jako například LALR anebo LR založeného na tabulkové syntaktické analýze. To je obzvláště případ, jestliže gramatika není ve tvaru LL(k), protože transformační gramatika na LL upraví gramatiku na vhodnou pro prediktivní syntaktickou analýzu. Prediktivní syntaktické analyzátory mohou být také automaticky generované pomocí nástroje jako je ANTLR.

Prediktivní syntaktické analyzátory lze znázornit pomocí přechodových diagramů pro každý neterminální symbol, kde hrany mezi počátečním a koncovým stavem jsou označeny symboly (terminály a neterminály) z pravé strany přepisovacího pravidla.[2]

Příklad syntaktického analyzátorů

Následující gramatika podobná EBNF (pro programovací jazyk PL/0, který navrhl Niklaus Wirth v knize Algoritmy + datové struktury = programy) je ve tvaru LL(1):

 program = block "." .
 
 block =
     ["const" ident "=" number {"," ident "=" number} ";"]
     ["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 zapsány v uvozovkách. Každý neterminál je definován pravidlem v gramatice, kromě symbolu ident a number, o nichž se předpokládá, že jsou implicitně definovány.

Implementace v jazyce C

Následuje implementace analyzátoru s rekurzivním sestupem v jazyce C pro jazyk PL/0 popsaný výše. Analyzátor čte v zdrojový text a skončí s chybovou zprávou, jestliže se nepodaří analyzovat kód, a tiše skončí, jestliže se kód analyzuje úspěšně.

Všimněte si, jak je prediktivní syntaktický analyzátor uvedený níže blízce strukturován podle gramatiky popsané výše. Pro každý neterminál v gramatice existuje procedura. Analýza klesá shora dolů, dokud není zpracován poslední neterminál. Fragment program závisí na globální proměnné, sym, který obsahuje další symbol ze vstupu a funkce getsym, která při svém vyvolání aktualizuje sym.

Implementace funkcí getsym 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 getsym(void);
void error(const char msg[]);
void expression(void);

int accept(Symbol s) {
    if (sym == s) {
        getsym();
        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");
        getsym();
    }
}

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

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

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

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");
        getsym();
    }
}

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) {
    getsym();
    block();
    expect(period);
}

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Recursive descent parser na anglické Wikipedii.

Anglická verze tohoto článku byla převzata z Free On-line Dictionary of Computing před 1. listopadem 2008 a byla zahrnuta pod licenční podmínky GFDL verze 1.3 nebo pozdější.

  1. ↑ Burge, W.H. Recursive Programming Techniques. [s.l.]: [s.n.], 1975. Dostupné online. ISBN 0-201-14450-6. 
  2. ↑ AHO, Alfred V.; SETHI, Ravi; ULLMAN, Jeffrey. Compilers: Principles, Techniques and Tools. 1. vyd. [s.l.]: Addison Wesley, 1986. 

Literatura

  • Compilers: Principles, Techniques, and Tools, first edition, Alfred V Aho, Ravi Sethi a Jeffrey D Ullman, Section 4.4.
  • Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, ISBN 0-521-82060-X.
  • Recursive Programming Techniques, W.H. Burge, 1975, ISBN 0-201-14450-6
  • Crafting Compiler with C, Charles N Fischer a Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
  • Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
  • Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, ISBN 0-13-022418-9
  • Compiler Construction, Niklaus Wirth, 1996, ISBN 0-201-40353-6

Související články

  • JavaCC – generátor syntaktických analyzátorů rekurzivním sestupem
  • Coco/R – generátor syntaktických analyzátorů rekurzivním sestupem
  • ANTLR – generátor syntaktických analyzátorů s rekurzivním sestupem
  • Parsing expression grammar – jiný druh reprezentující gramatiku s rekurzivním sestupem
  • Spirit Parser Framework – framework generátoru syntaktických analyzátorů s rekurzivním sestupem pro jazyk C++ nevyžadující žádný krok před překladem
  • Tail recursive parser – varianta analyzátoru s rekurzivním sestupem
  • parboiled (Java) – PEG knihovna pro syntaktickou analýzu s rekurzivním sestupem pro jazyk Java
  • Recursive ascent parser
  • bnf2xml Nástroj pro doplnění textu XML značkami používající pokročilé vyhledávání v BNF. (LL rekurzivní analyzátor shora dolů, nevyžaduje překlad lexikálního analyzátoru)
  • Parse::RecDescent: Univerzální modul pro jazyk Perl implementující rekurzivní sestup.
  • pyparsing: Univerzální modul pro rekurzivní parsing pro jazyk Python, který neimplemtuje rekurzivní sestup (python-list post).
  • Jparsec Javový port modulu Parsec pro jazyk Haskell.

Externí odkazy