PDA

View Full Version : [Linguaggi Formali] Aiuto con algoritmo LR(1)


_Claudio
13-09-2009, 10:58
Come da titolo, ho un problema abbastanza complicato con l'algoritmo di costruzione della macchina pilota LR(1), chiunque ne sa qualcosa mi contatti in pvt perchè la descrizione del problema è complessa e devo inviare un file .doc con diagrammi e formule.

Vincenzo1968
13-09-2009, 14:25
Nel corso online della Stanford University l'algoritmo è ben spiegato:

http://www.stanford.edu/class/cs143/

Per i parser di grammatiche LR(1), vedi in particolare questo(par. Constructing LR(1) parsing tables pag.5):

http://www.stanford.edu/class/cs143/handouts/12-SLR-Parsing.pdf

_Claudio
13-09-2009, 18:16
Anche nella descrizione fornita nei documenti che mi hai consigliato il problema che ho riscontrato sussiste.

Forse lo applico male io ma quando un non terminale ha regole di derivazione sinistre o categorizzazioni quell'algoritmo ha dei problemi.

costruendo le macchine relative a (es.):
S->(alfa)A(beta) |...
A->Ca | B

con alfa e beta stringhe di terminali e non terminali qualsiasi.

Eseguendo l'algoritmo quando si arriva sui non terminali B e C non vengono prese in considerazione le relative macchine perchè la computazione della funzione di transizione dell'automa riconoscitore "salta" allo stato seguente B e C sulla macchina Ma.

Spiegato così può sembrare complicato, difatti ho pronto un .doc per chiunque voglia risolvere l'arcano mistero.

Può essere, anzi sicuramente è così, che sono io a sbagliare l'applicazione dell'algoritmo.