04/11/12 16:11
dmr
Ciao a tutti,sto studiando da autodidatta Il libro "Compilatori Principi, tecniche e strumenti", e sono arrivato all'analisi sintattica.
Studiando le grammatiche mi sono fermato in un problema che non capisco cioè la rimozione della ricorsione sinistra in una grammatica.
Il mio libro spiega questo algoritmo per eliminare la ricorsione sinistra:
ordina arbitrariamente i non terminali come A1,A2 ....... An.
for(ogni i fino a n)
{
for(ogni j da 1 a i-1)
{
sostituisci ogni produzione nella forma Ai--> Ajγ
con le produzioni Ai--> δ1γ | δ1γ | ... | δkγ in cui Aj--> δ1 | δ2 | ... | δk
sono tutte le produzioni per il non terminale Aj in esame
}
elimina la ricorsione sinistra immediata delle produzioni per Ai
}
Per esempio se ho questa grammatica con ricorsione sinistra:
S--> Aa|b
A--> Ac|Sd|ε
dandola in input all'algoritmo dovrebbe diventare:
S--> Aa|b
A--> bdA'|A'
A'-->cA'|adA'|ε
Perchè?
Quello che non capisco è il funzionamento dell'algoritmo. Me lo potreste spiegare meglio?
Grazie mille in anticipo.
Studiando le grammatiche mi sono fermato in un problema che non capisco cioè la rimozione della ricorsione sinistra in una grammatica.
Il mio libro spiega questo algoritmo per eliminare la ricorsione sinistra:
ordina arbitrariamente i non terminali come A1,A2 ....... An.
for(ogni i fino a n)
{
for(ogni j da 1 a i-1)
{
sostituisci ogni produzione nella forma Ai--> Ajγ
con le produzioni Ai--> δ1γ | δ1γ | ... | δkγ in cui Aj--> δ1 | δ2 | ... | δk
sono tutte le produzioni per il non terminale Aj in esame
}
elimina la ricorsione sinistra immediata delle produzioni per Ai
}
Per esempio se ho questa grammatica con ricorsione sinistra:
S--> Aa|b
A--> Ac|Sd|ε
dandola in input all'algoritmo dovrebbe diventare:
S--> Aa|b
A--> bdA'|A'
A'-->cA'|adA'|ε
Perchè?
Quello che non capisco è il funzionamento dell'algoritmo. Me lo potreste spiegare meglio?
Grazie mille in anticipo.
Ultima modifica effettuata da dmr 04/11/12 16:13
aaa