Converti la grammatica in una grammatica LL (1) che riconosce la stessa lingua

2

Ho la seguente domanda di esempio per un esame di compilatori e volevo controllare la mia soluzione.

Convert the following grammar into an LL(1) grammar which recognises the same 
language:

E -> E + T  
E -> T  
T -> id 
T -> id() 
T -> id(L) 
L -> E;L 
L -> E

Per la mia risposta ho

E  -> T E'  
E' -> + T | ε  
T  -> id 
T  -> id() 
T  -> id(L) 
L  -> E L' 
L' -> ;E | ε

Qualcuno può verificare la risposta?

Modifica

Ok, sarebbe simile a ...

E  -> T E'  
E' -> + E | ε  
T  -> id 
T  -> id() 
T  -> id(L) 
L  -> E L' 
L' -> ;E | ε
    
posta TomSelleck 15.01.2013 - 22:28
fonte

2 risposte

3

E -> E + T | T
T -> id | id() | id(L)
L -> E;L | E

E - >
TE ' E '- > + TE '| ε

L -> E;L | E

L - >
EL ' L '- > ; L | ε

devi trasformare T come ho fatto con L altrimenti sarà un LL (3)

    
risposta data 16.01.2013 - 15:03
fonte
2

Chiudi, ma non del tutto.

Considera la frase "a + b + c", dove a, b e c sono tutti id.

La grammatica originale lo riconosce, per gentile concessione della ricorsione E + T.

La tua grammatica riconosce "a + b", quindi si blocca, perché non si ripresenta.

[aggiunto più tardi] Ora, considera "a (b; c; d; e)". La grammatica si interrompe dopo "a (b; c", per un motivo simile.

    
risposta data 15.01.2013 - 23:06
fonte

Leggi altre domande sui tag