Анализатор рекурзивним спустом

Анализатор рекурзивним спустом је анализатор наниже направљен од скупа вишезначно-рекурзивних процедура (или нерекурзивних еквивалената) где свака од процедура најчешће имплементира једно од правила граматике. Тако структура резултујућег програма најближе пресликава граматику која је препозната.

Предувидни анализатор је анализатор рекурзивним спустом који не захтева враћање уназад. Предувидна анализа је могућа једино за класе LL(k) граматика, тј. оних контекстно слободних граматика за које постоји неки позитиван цео број к који дозвољава анализатору да одлучи које правило граматике да примени испитујући првих к токена на улазу. (LL(k) граматике према томе искључују све вишезначне граматике, као и све граматике које садрже леву рекурзију. Свака контекстно слободна граматика се може трансформисати у еквивалентну граматику без леве рекурзије, иако уклањање леве рекурзије неће увек довести до LL(k) граматике.) Предувидни анализатор завршава рад у линеарном времену.

Рекурзивни спуст са подршком је техника којом се одређује које правило ће се применити тако што испробава сва правила, редом. Рекурзивни спуст са подршком није ограничен на LL(k) граматике, али не гарантује да ће завршити осим ако граматика није LL(k). Чак и када успешно заврше, анализатори који користе рекурзивни спуст са подршком могу да захтевају експоненцијално време за рад.

Иако су предувидни анализатори широко распрострањени, програмери често радије праве LR или LALR анализаторе помоћу генератора анализатора без трансформације граматике у LL(k) форму.

Неки аутори дефинишу анализаторе рекурзивним спустом као предувидне анализаторе. Други тај термин користе шире, те укључују рекурзивни спуст са подршком.

Пример анализатора

Следећа EBNF граматика (за програмски језик Никлауса Вирта PL/0, из Algorithms + Data Structures = Programs) је у LL(1) форми (због једноставности, претпоставља се да су ident и number терминали):

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

Терминали су наведени под наводницима (изузев ident и number). Сваки нетерминал дефинисан је правилом граматике.

C имплементација

Оно што следи је имплементација анализатора рекурзивним спустом за језик који је претходио у C-у. Анализатор учитава изворни код, и излази са поруком о грешци ако код не прође анализу, или излази без порука ако код прође анализу.

Приметите колико приближно предувидни анализатор који следи осликава граматику изнад. Постоји процедура за сваки нетерминал у граматици. Анализа се врши наниже, све док последњи нетерминал није обрађен. Део програма зависи од глобалне променљиве, sym, која садржи следећи симбол са улаза, и функције getsym, која по позиву ажурира sym.

Имплементације функција getsym и error су изостављене због једноставности.

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

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

Имплементација у функционалним језицима

Анализаторе рекурзивним спустом је нарочито једноставно имплементирати у функционалним језицима као што су Haskell или ML.

Спољашње везе

Functional Pearls: Monadic Parsing in Haskell