Analýza rekurzivním sestupem
Analýza rekurzivním sestupem () 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.

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.

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 

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ší.

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, .
 Recursive Programming Techniques, W.H. Burge, 1975, 
 Crafting Compiler with C, Charles N Fischer a Richard J LeBlanc, Jr, 1991, .
 Compiling with C# and Java, Pat Terry, 2005, , 624
 Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, 
 Compiler Construction, Niklaus Wirth, 1996,

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 
 Introduction to Parsing - lehce čitelný úvod do syntaktické analýzy s vyčerpávající částí o analyzátoru s rekurzivním sestupem
 How to turn Grammar to a program in C language - stručný tutorial o implementaci analyzátoru s rekurzivním sestupem
 Simple mathematical expressions parser Jednoduchý analyzátor matematických výrazů v jazyce Ruby
 Simple Top Down Parsing in Python  Jednoduchý parser shora dolů v Pythonu
 Jack W. Crenshaw: Let's Build a Compiler (1988-1995), v Pascalu, s výstupem v jazyce symbolických adres, zkonstruovaný s přístupem „keep it simple“
 Functional Pearls: Monadic Parsing in Haskell

Algoritmy syntaktické analýzy