PDA

Visualizza la versione completa : [ALGORITMO] LALR: propagazione dei "look ahead"


bako
31-01-2007, 11:46
Allora, spero che chi entri qui sappia già cos'è.
Il mio problema, più che per LALR in se è per la propagazione dei look ahead. non l'ho proprio capita. E' la funzione che serve per creare la tabella ottimizzata, e non quella partendo da clr e poi riducendo le entry della tabella.
qualcuno sa darmi un aiuto??

murder eyes
01-02-2007, 13:31
è probabile anche che questo algoritmo LALR sia chiamato in diversi modi.
Magari lo hai visto a scuola e te l hanno presentato con un altro nome.
Spiegaci in cosa consiste l'algoritmo e casomai anche l'acronimo LALR per cosa sta.

ricciare
01-02-2007, 14:25
Bako, in pratica il parser LALR(1) e' di facile comprensione se sai come funziona LR(1).
Spiego: il parser LR(1) per ogni item prende in cosiderazione non tutti i simboli follow, cosi' come invece accadeva per SLR, bensi' solo i seguiti effettivi. In questo modo i conflitti sono drasticamente ridotti (in particolare i conflitti riduci/riduci). Il numero degli stati aumenta notevolmente, ma questo perche' vai a lavorare sui singoli simboli di lookahead.
La struttura di LALR puoi farla cosi': ti costruisci il parser LR(1) e poi unisci in un unico item tutti gli item che hanno lo stesso core ma lookahead diversi (im pratica LALR e SLR hanno lo stesso numero di stati). Ovvio che se grammatica e' LR(1) non e' detto che sia anche LALR(1): l'accorpamento degli stati potrebbe reintrodurre dei conflitti, in particolare quei conflitti riduci/riduci che LR(1) aveva eliminato.

Se ho tirato troppo veloce su qualche parte .. a disposizione.


LALR = Lookahead LR

bako
01-02-2007, 15:18
praticamente:
posso fare clr(1) e accorpare gli stati uguali. così facendo però, potrei avere dei conflitti dove applicando la propagazione dei lookahead per generare lalr direttamente, non avrei?
hai qualcosa che spiega come funziona la propagazione dei Look ahead?

ricciare
01-02-2007, 17:08
puoi fare LR(1) ... CLR(1) non so cosa sia.
Si, in pratica prendi tutti gli stati che hanno lo stesso core e lookahead diverrso e li consideri come un unico stato. Ovviamente anche le funzioni goto che in LR puntavano a stati diversi perche' si aveva lookahead diverso, adesso invece punta ad un solo stato per questa unificazione di stati. Questa unificazione potrebbe si comportare dei rischi di conflitti riduci/riduci perche' con LR(1) non si avevano (qui interveniva il lookahed a creare piu' stati e quindi impossibile avere conflitto riduci/riduci) invece con la LALR(1), unificando gli stati .. bhe' ... il rischio di riavere questi conflitti esiste.

Vedi questo link .. http://web.unicam.it/matinf/Dispense/diberardini/Linguaggi_di_Programmazione_Compilatori/09(Tabelle_LALR).pdf

adesso provo a cercarti la dispensa, fatte bene, che fece a suo tempo il mio prof .. appena la trovo ti passo il link.

.. come promesso ecco i links (attento: il prof si e' dimenticato di aggiungere le estensioni, se non le scrivi tu non fungono):
questo alla pagina del corso: http://www.di.unipi.it/~bellia/FormaliWeb/FormaliWeb/materiale2004/Accesso.htm
invece questo e' relativo ai parsing LR,LALR: http://www.di.unipi.it/~bellia/FormaliWeb/FormaliWeb/materiale2004/materiale/SINT3.pdf

bako
01-02-2007, 17:12
ok. quello che dici tu noi lo chiamaiamo CLR, canonical LR. grazie per l'aiuto intanto.
Quel metodo l'ho capito, però sul libro c'è anche quello ottimizzato che crea in automatico gli stati usando la propagazione/generazione degli stati.

altra domand:
una grammatica ricorsiva a sinistra è ambigua?
LR si può fare su grammatiche ambigue? e ricorsive a sinistra?

Loading