Grammatica: differenza tra un top down e un bottom up?

Question

Qual è la differenza tra una grammatica in alto e in basso? Un esempio sarebbe fantastico.

Answer 1

Prima di tutto, la grammatica non è orizzontale o verticale, il parser è (sebbene ci siano grammatiche che possono essere analizzate da una, ma non dall'altra).

Da un punto di vista pratico, la differenza principale è che la maggior parte dei parser scritti a mano è top-down, mentre una percentuale molto più ampia di parser generati dal computer è di tipo bottom-up (sebbene, ovviamente, il contrario sia certamente possibile) .

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

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

A bottom-up lavoro parser nella direzione inversa - - dove un parser di discesa ricorsivo inizia dall'espressione completa e lo suddivide in pezzi sempre più piccoli fino a raggiungere il livello di token individuali, un parser bottom-up parte dai token individuali e utilizza tabelle di regole su come quei token combaciare con i livelli sempre più alti della gerarchia dell'espressione fino a raggiungere il livello più alto (ciò che è rappresentato come "espressione" 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; 
} 

Nota che il lexing qui è abbastanza stupido (è fondamentalmente solo accetta un singolo carattere come token) e le espressioni consentite sono abbastanza limitate (solo + - * /). OTOH, è abbastanza buono per gestire un ingresso come:

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

da cui essa produce quella che credo sia uscita corretta:

1 2 3 4 5 6/* + * +

Answer 2

Afaik non fa alcuna differenza per la grammatica stessa, ma per il parser è .

Wikipedia ha una spiegazione abbastanza lunga di entrambi bottom-up e top-down parsing.

In genere il modo (imho) più intuitivo è top-down. Si inizia con il simbolo di inizio e si applicano le regole di trasformazione che si adattano, mentre con il basso verso l'alto è necessario applicare le regole di trasformazione all'indietro (che di solito creava un bel mal di testa per me).