Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Ciao a tutti sto studiando il libro: Compilatori Princpi tecniche e strumenti, e sono arrivato allo studio dei parser predittivi.
Ho implementato il seguente algoritmo scritto sul libro:
Nello stack dell'algoritmo c'è già E$ con E alla cima.
Codice sorgente - presumibilmente Delphi
ip punta al primo simbolo in ingresso
assegna a X il simbolo alla cima dello stack
a=input[ip]
while(X!=$)
{
if(X è a)Rimuovi l'elemento dalla cima dello stack e avanza il puntatore ip
else if(X è un terminale) errore();
else if(m[x,a]=X--> Y1,Y2....Yk)
{
produci come uscita la produzione X--> Y1,Y2....Yk;
rimuovi l'elemento dalla cima dello stack;
poni Yk,Yk-1.... Y1 sullo stack, con y1 in cima;
}
assegna a X il simbolo alla cima dello stack;
}
m sarebbe la tabella(creata con le funzioni first e follow) che serve al parser per l'analisi della stringa in input, e contiene:
i + * ( ) $
E TE' TE'
E' +TE' ε ε
T FT' FT'
T' ε *FT' ε ε
F i (E)
L'algorimo, data la tabella della precedente grammatica, deve riconoscere la stringa in input(riconosciuta attraverso la sua grammatica) , in modo da dire se ci sono errori sintattici.
Eseguendo l'algoritmo noto che:
1)Se all'algoritmo do in input($ lo sarebbe il terminatore di stringa): i+i*i$ // nessun problema, infatti è sintatticamente corretta.
2)Se do in input: ((i)*(i)$ // l'algoritmo segnala un errore di sintassi,infatti manca )
3)Se invece do in input: i)$ //non ricevo nessun errore(ma dovrebbe esserci)
Anche se analizzo la stringa a mano non mi risultano esserci errori se applico quell'algoritmo.
Come posso fare affinchè dando in input: i)$ riceva un errore sintattico?
Grazie in anticipo!.
Ultima modifica effettuata da dmr il 05/01/2013 alle 17:15
x piccola non è definita. Se anche fosse X, la condizione non viene mai soddisfatta.
Cosa significa "produrre una produzione come uscita"? Le produzioni non sono dati di output.
Non capisco bene la tabella. Per i parser LL dovresti avere semplicemente una stringa di lookahead.
Grazie per la risposta!
Produrre una produzione come uscita nel senso di far vedere in output che tipo di produzione sceglie il parser dalla tabella.
La tabella è nell'immagine allegata.
L'algoritmo che ho postato(l'ho copiato dal libro) l'ho tradotto in java e funziona bene solo che:se do in input: i)$ non ricevo nessun errore, ma dovrebbe esserci perchè la parentesi tonda non ne chiude nessun altra. Secondo me il problema è nell'algoritmo del libro perchè anche se eseguo a mano l'algoritmo con la stringa i)$ in input trovo gli stessi outputs del mio programma e cioè:
Stack= E$
a=i
X=E
OUT=TE' Stack=TE'$
X=T
OUT= FT' Stack=FT'E'$
X=F
OUT= i Stack= iT'E'$
X=i Stack=T'E'$ // viene verificata la condizione dell'if alla riga 6
a=)
X= T'
OUT= ε Stack= E'$
X=E'
OUT= ε Stack=$ // e la stringa viene accettata lo stesso!!!
Per esserci un errore il parser deve andare in una casella della tabella vuota.
Penso di aver capito. La stringa viene accettata, ma l'ultimo carattere non viene consumato. Quindi, di fatto, accetti semplicemente la stringa "i", che è producibile dalla grammatica.