Come determinare se una lingua è LL (1) LR (0) SLR (1)

StackOverflow https://stackoverflow.com/questions/475949

Domanda

Esiste un modo semplice per determinare se una grammatica è LL (1), LR (0), SLR (1) ... solo guardando la grammatica senza fare alcuna analisi complessa?

Ad esempio: per decidere se una grammatica BNF è LL (1) devi calcolare i set First e Follow, che in alcuni casi possono richiedere molto tempo.

Qualcuno ha idea di come farlo più velocemente? Qualsiasi aiuto sarebbe davvero apprezzato!

È stato utile?

Soluzione

Prima di tutto, un po 'di pedanteria. Non puoi determinare se una lingua è LL (1) dall'ispezione di una grammatica per essa, puoi solo fare dichiarazioni sulla grammatica stessa. È perfettamente possibile scrivere grammatiche non LL (1) per le lingue per le quali esiste una grammatica LL (1).

A parte questo:

  • Potresti scrivere un parser per la grammatica e far calcolare prima un programma e seguire insiemi e altre proprietà per te. Dopotutto, questo è il grande vantaggio delle grammatiche BNF, sono comprensibili automaticamente.

  • Ispeziona la grammatica e cerca violazioni dei vincoli di vari tipi di grammatica. Ad esempio: LL (1) consente la ricorsione a destra ma non a sinistra, quindi una grammatica che contiene la ricorsione a sinistra non è LL (1). (Per altre proprietà grammaticali dovrai passare un po 'di tempo con le definizioni, perché non riesco a ricordare nient'altro al di sopra della mia testa in questo momento :).

Altri suggerimenti

In risposta alla tua domanda principale: per una grammatica molto semplice, potrebbe essere possibile determinare se è LL (1) senza costruire i set FIRST e FOLLOW, ad es.

  

A & # 8594; A + A | un

     

non è LL (1), mentre

     

A & # 8594; a | b

è.

Ma quando diventerai più complesso di così, dovrai fare alcune analisi.

  

A & # 8594; B | un
  B & # 8594; A + A

Questo non è LL (1), ma potrebbe non essere immediatamente ovvio

Le regole grammaticali per l'aritmetica diventano rapidamente molto complesse:

  

expr & # 8594; termine {'+' termine}
  termine & # 8594; factor {'*' factor}
  fattore & # 8594; numero | '(' expr ')'

Questa grammatica gestisce solo la moltiplicazione e l'aggiunta, e già non è immediatamente chiaro se la grammatica è LL (1). È ancora possibile valutarlo guardando attraverso la grammatica, ma man mano che la grammatica cresce diventa meno fattibile. Se stiamo definendo una grammatica per un intero linguaggio di programmazione, quasi sicuramente prenderà alcune analisi complesse.

Detto questo, ci sono alcuni evidenti segni rivelatori che la grammatica non è LL (1) & # 8212; come l'A & # 8594; A + A sopra & # 8212; e se riesci a trovare uno di questi nella tua grammatica, saprai che deve essere riscritto se stai scrivendo un parser di discesa ricorsivo. Ma non ci sono scorciatoie per verificare che la grammatica sia LL (1).

Un aspetto, "è la lingua / grammatica ambigua", è una domanda indecidibile conosciuta come Pubblica corrispondenza e arresto problemi.

Direttamente dal libro "Compilatori: principi, tecniche e amp; Strumenti " di Aho, et. al.

Pagina 223:

Una grammatica G è LL (1) se e solo se ogni volta che A - > alfa | beta sono due produzioni distinte di G, valgono le seguenti condizioni:

  1. Per nessun terminale "a" entrambi alpha e beta derivano stringhe che iniziano con " a "
  2. Al massimo una delle alpha e beta può derivare la stringa vuota
  3. Se beta può raggiungere la transizione vuota tramite zero o più transizioni, allora alpha non deriva alcuna stringa che inizia con un terminale in FOLLOW (A). Allo stesso modo, se alfa può raggiungere la transizione vuota tramite zero o più transizioni, allora beta non deriva alcuna stringa che inizia con un terminale in FOLLOW (A)

Essenzialmente si tratta di verificare che la grammatica superi il test di disgiunzione di coppia e che non implichi anche la ricorsione a sinistra. O più succintamente una grammatica G che è ricorsiva a sinistra o ambigua non può essere LL (1).

Controlla se la grammatica è ambigua o no. In tal caso, la grammatica non è LL (1) perché nessuna grammatica ambigua è LL (1).

ya ci sono scorciatoie per ll (1) grammatica

1) se A- > B1 | B2 | ....... | Bn     quindi prima (B1) prima intersezione (B2) intersezione .first (Bn) = set vuoto quindi sarà ll (1) grammatica

2) se A- > B1 | epsilon      quindi seguire l'intersezione B1 (A) è vuoto impostato

3) se G è una grammatica tale che ogni non terminale deriva solo una produzione, allora la grammatica è LL (1) 

p0 S' → E
p1 E → id
p2 E → id ( E )
p3 E → E + id
  • Costruisci il DFA LR (0), il FOLLOW impostato per E e le tabelle action / goto SLR.
  • È una grammatica LR (0)? Dimostra la tua risposta.
  • Utilizzando le tabelle SLR, mostra i passaggi (turni, riduzioni, accetta) di un'analisi del parser LR:
    id (id + id)
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top