Analizator rekurzivnim spustom

Analizator rekurzivnim spustom je analizator naniže napravljen od skupa višeznačno-rekurzivnih procedura (ili nerekurzivnih ekvivalenata) gde svaka od procedura najčešće implementira jedno od pravila gramatike. Tako struktura rezultujućeg programa najbliže preslikava gramatiku koja je prepoznata.

Preduvidni analizator je analizator rekurzivnim spustom koji ne zahteva vraćanje unazad. Preduvidna analiza je moguća jedino za klase LL(k) gramatika, tj. onih kontekstno slobodnih gramatika za koje postoji neki pozitivan ceo broj k koji dozvoljava analizatoru da odluči koje pravilo gramatike da primeni ispitujući prvih k tokena na ulazu. (LL(k) gramatike prema tome isključuju sve višeznačne gramatike, kao i sve gramatike koje sadrže levu rekurziju. Svaka kontekstno slobodna gramatika se može transformisati u ekvivalentnu gramatiku bez leve rekurzije, iako uklanjanje leve rekurzije neće uvek dovesti do LL(k) gramatike.) Preduvidni analizator završava rad u linearnom vremenu.

Rekurzivni spust sa podrškom je tehnika kojom se određuje koje pravilo će se primeniti tako što isprobava sva pravila, redom. Rekurzivni spust sa podrškom nije ograničen na LL(k) gramatike, ali ne garantuje da će završiti osim ako gramatika nije LL(k). Čak i kada uspešno završe, analizatori koji koriste rekurzivni spust sa podrškom mogu da zahtevaju eksponencijalno vreme za rad.

Iako su preduvidni analizatori široko rasprostranjeni, programeri često radije prave LR ili LALR analizatore pomoću generatora analizatora bez transformacije gramatike u LL(k) formu.

Neki autori definišu analizatore rekurzivnim spustom kao preduvidne analizatore. Drugi taj termin koriste šire, te uključuju rekurzivni spust sa podrškom.

Primer analizatora

Sledeća EBNF gramatika (za programski jezik Niklausa Virta PL/0, iz Algorithms + Data Structures = Programs) je u LL(1) formi (zbog jednostavnosti, pretpostavlja se da su ident i number terminali):

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

Terminali su navedeni pod navodnicima (izuzev ident i number). Svaki neterminal definisan je pravilom gramatike.

C implementacija

Ono što sledi je implementacija analizatora rekurzivnim spustom za jezik koji je prethodio u C-u. Analizator učitava izvorni kod, i izlazi sa porukom o grešci ako kod ne prođe analizu, ili izlazi bez poruka ako kod prođe analizu.

Primetite koliko približno preduvidni analizator koji sledi oslikava gramatiku iznad. Postoji procedura za svaki neterminal u gramatici. Analiza se vrši naniže, sve dok poslednji neterminal nije obrađen. Deo programa zavisi od globalne promenljive, sym, koja sadrži sledeći simbol sa ulaza, i funkcije getsym, koja po pozivu ažurira sym.

Implementacije funkcija getsym i error su izostavljene zbog jednostavnosti.

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

Implementacija u funkcionalnim jezicima

Analizatore rekurzivnim spustom je naročito jednostavno implementirati u funkcionalnim jezicima kao što su Haskell ili ML.

Spoljašnje veze

Functional Pearls: Monadic Parsing in Haskell