Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Problema parser predittivo
Forum - Algoritmi - Problema parser predittivo

Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 16:16
Sabato, 05/01/2013
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

  1. ip punta al primo simbolo in ingresso
  2. assegna a X il simbolo alla cima dello stack
  3. a=input[ip]
  4. while(X!=$)
  5. {
  6.   if(X è a)Rimuovi l'elemento dalla cima dello stack e avanza il puntatore ip
  7.   else if(X è un terminale) errore();
  8.   else if(m[x,a]=X--> Y1,Y2....Yk)
  9.   {
  10.     produci come uscita la produzione X--> Y1,Y2....Yk;
  11.     rimuovi l'elemento dalla cima dello stack;
  12.     poni Yk,Yk-1.... Y1 sullo stack, con y1 in cima;
  13.   }
  14.   assegna a X il simbolo alla cima dello stack;
  15. }



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)

La grammatica è:

E--> TE'
E'--> +TE'| ε
T--> FT'
T'--> *FT'| ε
F--> (E)|i

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!.:k:

Ultima modifica effettuata da dmr il 05/01/2013 alle 17:15
PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 21:49
Domenica, 06/01/2013
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.

PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 8:47
Lunedì, 07/01/2013
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.


dmr ha allegato un file: ParserTable.gif (9588 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da dmr il 07/01/2013 alle 8:54
PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 11:09
Lunedì, 07/01/2013
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.

PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
Postato alle 12:31
Lunedì, 07/01/2013
Ah,ok adesso ho capito. Grazie mille!:k:

PM Quote