Grammatica: differenza tra un verso il basso in alto e in fondo?

Question

Qual è la differenza tra un down in alto e fino grammatica fondo? Un esempio potrebbe essere impressionante.

Answer 1

Prima di tutto, la grammatica in sé non è top-down o bottom-up, il parser è (anche se ci sono le grammatiche che può essere analizzato da uno ma non l'altro).

Dal punto di vista pratico, la differenza principale è che la maggior parte parser scritti a mano sono top-down, mentre una percentuale molto maggiore di parser generato dalla macchina sono bottom-up (anche se, naturalmente, il contrario è certamente possibile).

Un parser top-down utilizza tipicamente discesa ricorsiva, che significa in genere una struttura simile a questo (utilizzando espressioni matematiche tipiche come esempio):

expression() { term() [-+] expression }
term() { factor() [*/] term() }
factor() { operand() | '(' expression() ')' }

Un lavoro parser bottom-up in direzione inversa - dove un ricorsive discesa parser parte dalla piena espressione, e lo divide in pezzi più piccoli fino a raggiungere il livello di singoli token, bottom-up parser inizia dai singoli token, e utilizza le tabelle di regole su come quelle pedine si incastrano in più alti livelli della gerarchia espressione fino a raggiungere il livello più alto (ciò che è rappresentato come "espressione" di cui sopra).

Modifica: Per chiarire, forse avrebbe senso aggiungere un parser davvero banale. In questo caso, mi limiterò a fare il vecchio classico di conversione di una versione semplificata di un tipico un'espressione matematica da infissa a postfix:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void expression(void);

void show(int ch) { 
    putchar(ch);
    putchar(' ');
}

int token() { 
    int ch;
    while (isspace(ch=getchar()))
        ;
    return ch;
}

void factor() { 
    int ch = token();
    if (ch == '(') {
        expression();
        ch = token();
        if (ch != ')') {
            fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch);
            exit(EXIT_FAILURE);
        }
    }
    else
        show(ch);
}

void term() { 
    int ch;
    factor();
    ch = token();
    if (ch == '*' || ch == '/') {
        term();
        show(ch);
    }
    else
        ungetc(ch, stdin);
}

void expression() {
    int ch;
    term();
    ch = token();
    if (ch == '-' || ch=='+') {
        expression();
        show(ch);
    }
    else 
        ungetc(ch, stdin);
}

int main(int argc, char **argv) {
    expression();
    return 0;
}

Si noti che il Lexing qui è abbastanza stupido (fondamentalmente accetta solo un singolo carattere come un token) e le espressioni consentite sono piuttosto limitate (solo + - * /). OTOH, è bene sufficiente per gestire un ingresso come:

1 + 2 * (3 + 4 * (5/6))

da cui si fa produrre quella che credo sia uscita corretta:

1 2 3 4 5 6 / * * + +

Answer 2

AFAIK non fa alcuna differenza per la grammatica in sé, ma non per il parser.

Wikipedia ha un bel lunga spiegazione di entrambi bottom-up e top-down parsing .

Generalmente la (imho) modo più intuitivo è top-down. Si inizia con il simbolo di inizio e di applicare le regole di trasformazione che in forma, mentre con il bottom-up è necessario applicare regole di trasformazione all'indietro (che di solito ha creato un bel mal di testa per me).