Grammatica: differenza tra una top down e una bottom up? (Esempio)

Question

Si tratta di un follow-up domanda da Grammar: difference between a top down and bottom up?

ho capito da questa domanda che:

• la grammatica in sé non è top-down o bottom-up, il parser è
• ci sono le grammatiche che può essere analizzato da uno ma non l'altro
• (grazie Jerry Coffin

Così, per questa grammatica (tutte le OP formule matematiche possibili):

E -> E T E 
    E -> (E) 
    E -> D 

    T -> + | - | * |/

    D -> 0 
    D -> L G 

    G -> G G  
    G -> 0 | L 

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

Questo può essere letto da un parser dall'alto verso il basso e dal basso verso l'alto?

Potresti dire che si tratta di una grammatica top-down o di una grammatica bottom-up (o nessuna)?

---

sto chiedendo perché ho una domanda compiti a casa che chiede:

"Write top-down e bottom-up grammatiche per il linguaggio che consiste di tutti ..." (questione diversa)

Non sono sicuro se questo può essere corretto poiché sembra che non esista una grammatica top-down e bottom-up. Qualcuno potrebbe chiarire?

Answer 1

Questa grammatica è stupida, poiché unisce lexing e parsing come una cosa sola. Ma ok, è un esempio accademico.

La cosa con valori inferiori e superiori è che presenta casi d'angolo speciali che sono difficili da implementare con un normale aspetto 1. Probabilmente penso che dovresti controllare se ha qualche problema e cambiare la grammatica.

Per comprendere la grammatica ho scritto una corretta EBNF

expr: 
    expr op expr | 
    '(' expr ')' | 
    number; 

op: 
    '+' | 
    '-' | 
    '*' | 
    '/'; 

number: 
    '0' | 
    digit digits; 

digits: 
    '0' | 
    digit | 
    digits digits; 

digit: 
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9'; 

particolare mi non mi piace la regola digits: digits digits. Non è chiaro da dove iniziano le prime cifre e finisce il secondo. Vorrei implementare la regola come

digits: 
    '0' | 
    digit | 
    digits digit; 

Un altro problema è number: '0' | digit digits; Questo conflitto con digits: '0' e digits: digit;. È un dato di fatto che è duplicato. Vorrei cambiare le regole per (rimozione cifre):

number: 
    '0' | 
    digit | 
    digit zero_digits; 

zero_digits: 
    zero_digit | 
    zero_digits zero_digit; 

zero_digit: 
    '0' | 
    digit; 

Questo rende la grammatica LR1 (sinistra ricorsiva con un solo sguardo in avanti) e il contesto libero. Questo è ciò che normalmente darebbe ad un generatore di parser come il bisonte. E dal momento che il bisonte è in fondo, questo è un input valido per un parser di tipo bottom-up.

Per un approccio top-down, almeno per ricorsivo decente, ricorsivo a sinistra è un po 'un problema. Puoi usare il rollback, se vuoi, ma per questi vuoi una grammatica RR1 (right recursive one look ahead).Per farlo scambia le ricorsioni:

zero_digits: 
    zero_digit | 
    zero_digit zero_digits; 

Non sono sicuro che questo risponda alla tua domanda. Penso che la domanda sia mal formulata e fuorviante; e scrivo parser per vivere ...