Conversione di una grammatica in LL (1) grammatica: alcuni problemi

Question

Questo non è esattamente i compiti a casa, ma è legato ai miei studi:

Una grammatica per esempio è come:

E -> E + E | E * E | -E | (E) | id

Dopo aver rimosso l'ambiguità diventa (a partire dal più basso precedenza degli operatori)

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

E dopo aver rimosso la ricorsione sinistra e factoring di sinistra (non necessario in questo caso) la grammatica finale LL1 è:

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

che dà una tabella di parser privo di errori che funziona bene. Ora circa il problema che sto affrontando, si supponga che la grammatica è come questo:

E -> E + E | E * E | id = E | (E) | id

Ora non sono in grado di generare una tabella di analisi senza conflitti, il che significa che la mia grammatica finale non è LL1. Ecco i passaggi:

dopo la rimozione ambiguità:

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

e dopo la rimozione della ricorsione sinistra e factoring sinistra, la grammatica diventa:

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Ma c'è un conflitto nella tabella Parser che non sono in grado di rimuovere, il che significa che c'è un passo che ho perso, o c'è qualche errore nei passaggi che non sono in grado di trovare. Per favore dimmi cosa ho fatto di sbagliato e come risolvere questo problema. Ho lavorato su questo problema da molto tempo ormai.

Answer 1

Diciamo che:

E -> E+E|E*E|id=E|(E)|id 

diventerà:

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

allora si può andare con la rimozione ambiguità e sinistra ricorsione e ottenere:

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

Naturalmente, il problema è che perdi la precedenza dell'operatore.

La grammatica non sarà LL (1) se per ogni non terminale N, ci sarà eventuali elementi comuni in FIRST(N -> a) e FIRST(N -> b) per N -> a, N -> b essendo produzioni differenti da N.

Come si vede, l'aggiunta di una produzione N -> id= in in qualsiasi altro luogo interromperà tale regola.

È possibile creare una grammatica LL(2) (ma probabilmente non è ciò che si desidera), che può avere produzione id=E in qualsiasi luogo. (I set FIRST2 sono costituiti da stringhe a 2 elementi).

Inoltre, se si guarda alla grammatica presentata ancora una volta:

E -> E+E|E*E|id=E|(E)|id 

E 'un'alta probabilità, che la precedenza degli operatori che ho fatto nella soluzione di cui sopra è quello giusto per l'applicazione vera e propria. Controlla!