Sinistra e destra più Derivazione

Question

Sinistra e destra più Derivazione

#1 da (6 voti)
#2 da (2 voti)
#3 da (2 voti)
#4 da (1 voti)

6

Quindi capisco la semantica delle derivazioni fino a Backus Naur Form. Una cosa che non riesco a trovare in nessun libro di testo o le varie note dei docenti che sono on-line è questa.

Quando una derivazione più giusta sarebbe benefica sulla derivazione più a sinistra? Un compilatore o un generatore userebbe sempre left o right oppure userebbe entrambi?

Quindi ecco un esempio:

Supponiamo di avere la seguente frase linguistica: A = B + C * A

Esempio di grammatica della lingua che consente quanto sopra:

<assign>  <id> = <expr> 
<id>  A | B | C
<expr>  <expr> + <term>
        |<term>
<term> <term> * <factor> 
       |<factor>
<factor>  ( expr )
        | <id>

Left Derivation:

<assign>   => <id> = <expr>
              => A = <expr> + <term>
              => A = <term> + <term>  
              => A = <factor> + <term> 
              => A = <id> + <term> 
              => A = B + <term> 
              => A = B + <term> * <factor>
              => A = B + <factor> * <factor>
              => A = B + <id> * <factor>
              => A = B + C * < term>
              => A = B + C * <factor>
              => A = B + C * <id>
              => A = B + C * A

Right Derivation:

<assign>  => <id> = <expr>
      => <id> = <expr> + <term>
      => <id> = <expr> + <term>   * <factor>
      => <id> = <expr> + <term> * <id>
      => <id> = <expr> + <term> * A
      => <id> = <expr> + <factor> * A
      => <id> = <expr> + <id> * A
      => <id> = <expr> + C * A
      => <id> = <term> + C * A
      => <id> = <id> + C * A
      => <id> = B + C * A
      =>  A = B + C * C

programming-languages theory

posta Andrew S 26.03.2014 - 07:11

fonte

4 risposte

Leggi altre domande sui tag programming-languages theory

Algoritmo per testare l'equivalenza dei file Servizi di dominio rispetto a fabbriche e radici aggregate

score 6 · Answer 1

Il modo in cui è stato spiegato nella mia classe di compilatore, ben oltre trent'anni fa, è che uno schema di derivazione più a sinistra funziona meglio con un parser top-down (ad esempio la discesa ricorsiva), mentre uno schema di derivazione più a destra funziona meglio con un bottom- up (es. parser SLR (1), LALR (1), YACC et al). L'utilizzo dello schema di derivazione più a sinistra con un parser bottom-up richiede al parser di "impilare" l'intera frase, quindi elaborarla dall'estremità destra, piuttosto che riconoscere brevi frasi alla volta. Idem l'abbinamento opposto.

Il mio Green Dragon Book e Red Dragon Book sono attualmente in deposito, o andrei a cercare se hanno esempi o spiegazioni migliori.

Dopo aver riflettuto un po 'su questo argomento, la discussione precedente riguarda le grammatiche ricorsive e di destra ricorsive, ma penso che l'effetto sia lo stesso. A quel tempo, ho trovato il risultato molto soddisfacente, nel senso che diceva che non c'era un modo "migliore" per fare una grammatica, ma piuttosto dipendeva dal modo in cui il parser ha funzionato.

score 2 · Answer 2

Per conto proprio, entrambe le derivazioni più a sinistra e più a destra non sono altro che regole arbitrarie che disambigano quali passi prendere quando si analizzano o generano con un CFG: sono immaginabili molti ordini diversi di espansione non terminale che alla fine portano allo stesso albero e LMD e RMD sono semplicemente due semplici strategie per decidere quale percorso intraprendere.

Per i computer, è fondamentale avere regole così arbitrarie perché non possono prendere decisioni da soli . Tutto quello che possono fare è seguire alcune regole rigide, o provare tutte le possibilità e back-track se necessario. Il back-tracking equivale a una ricerca dello spazio di possibilità, che è uno spreco se una semplice regola farebbe anche il trucco. Praticamente tutti i linguaggi di programmazione sono definiti in modo tale che è necessario solo un parser deterministico e spesso solo un parser deterministico con un ambito di previsione molto limitato.

score 2 · Answer 3

Un parser discendente o discendente ricorsivo (LL (k)) costruisce una derivazione sinistra. Il tuo primo diagramma descrive approssimativamente i passaggi di tale analisi.

Un parser dal basso verso l'alto (SLR (k) o LALR (k)) costruisce una derivazione destra. Il tuo secondo diagramma delinea approssimativamente i passaggi di tale analisi.

Ciò che manca in questa discussione sono le differenze tra grammatiche appropriate. Se la grammatica è simile a questa:

<expr> := <term>
        | <term> + <expr>

La derivazione sinistra ora viene mostrata come backtrack, ed è meno adatta per un parser LL (k). La derivazione destra non è, e si adatta ancora al parsing bottom up. Ci sono altre grammatiche in cui la giusta derivazione presenta problemi.

La ragione principale di questi metodi, come li ho usati in passato, è di mostrare problemi nella grammatica che possono essere risolti con il refactoring, per renderli più adatti a un particolare tipo di parser.

score 1 · Answer 4

Le derivate più sinistre sono facili da costruire e che possono essere utilizzate nell'analisi Top-Down. I parser Top-Down sono facili da implementare ma possono gestire solo un set di grammatiche che non può gestire

grammatiche ambigue
Grammatic di sinistra ricorsive
Grammat non deterministici (factoring sinistro)

quindi la maggior parte delle derivazioni non verranno utilizzate per tutte le classi di grammatiche da analizzare.

Il parser bottom-up può gestire tutte le precedenti grammatiche e BUP utilizza l'RMD al contrario. Le RMD vengono utilizzate per analizzare tutte le classi di grammatiche.

Infine, RMD è più potente ed efficiente di LMD.