Compilatori 2009
docente: Fausto Spoto fausto.spoto@univr.it
Il compilatore Kitten versione 26/1/2009 (funziona solo su Java 1.5 o 1.6)
L'analizzatore di grammatiche GRAN, di
Enrico Masserdotti: gran@enricomasserdotti.eu
Documentazione della libreria BCEL
Sito da cui scaricare il graphviz per il formato .dot
Il manuale ufficiale della Java Virtual Machine
Making Compiler Design Relevant for Students who will (Most Likely) Never Design a Compiler di Saumya Debray
Dispensa
Testi d'esame (alcuni sono troppo vecchi per il programma attuale!):
24 giugno 2002 postscript,
pdf
3 luglio 2002 postscript,
pdf
6 settembre 2002 postscript,
pdf
20 dicembre 2002 postscript,
pdf
2 aprile 2003 postscript,
pdf
23 giugno 2003 postscript,
pdf
25 luglio 2003 postscript,
pdf
24 settembre 2003 postscript,
pdf
10 ottobre 2003 postscript,
pdf
12 dicembre 2003 postscript,
pdf
26 marzo 2004 postscript,
pdf
2 aprile 2004 postscript,
pdf
21 giugno 2004 postscript,
pdf
5 luglio 2004 postscript,
pdf
21 settembre 2004 postscript,
pdf
1 aprile 2005 postscript,
pdf
20 giugno 2005 postscript,
pdf,
soluzione esercizi 2-3
4 luglio 2005 postscript,
pdf,
soluzione esercizi 2-3
5 settembre 2005 postscript,
pdf
5 ottobre 2005 postscript,
pdf
12 dicembre 2005 postscript,
pdf
31 marzo 2006 postscript,
pdf
19 giugno 2006 postscript,
pdf
3 luglio 2006 postscript,
pdf
29 settembre 2006 postscript,
pdf
5 ottobre 2006 postscript,
pdf
31 ottobre 2006 postscript,
pdf
15 dicembre 2006 postscript,
pdf
27 giugno 2007 postscript,
pdf
Durante i laboratori, si inizierà a sviluppare il progetto
(si veda in fondo alla pagina)
Lezione 1 (27 gennaio 2009, 16:30-18:30)
i
introduzione al corso
i compilatori
esempi di programmi Kitten
espressioni, comandi, valori, tipi
relazione di sottotipo
analisi lessicale, token, espressioni regolari
JLex: specifica di token e azioni
Laboratorio 1 (29 gennaio 2009, 16:30-18:30)
Lezione 2 (3 febbraio 2009, 16:30-18:30)
da espressioni regolari ad automa finito non deterministico e poi deterministico
automa per più espressioni regolari
grammatiche
grammatica per Kitten
leftvalue e rightvalue
Lezione 3 (4 febbraio 2009, 10:30-12:30)
introduzione al parsing a discesa ricorsiva
forme sentenziali annullabili
definizione composizionale dell'annullabilità
calcolo degli annullabili
inizi di una forma sentenziale
definizione composizionale degli inizi
calcolo degli inizi per i non terminali
definizione dei seguiti
calcolo dei seguiti dei non terminali
insiemi discriminanti per il parsing a discesa ricorsiva
tabella e parsing LL(1)
Laboratorio 2 (5 febbraio 2009, 16:30-18:30)
Lezione 4 (10 febbraio 2009, 16:30-18:30)
esercizi su annullabili, primi, seguiti e parsing LL(1)
automa a pila: azioni di spostamento, riduzione, accettazione
item LR(0)
chiusura di un insieme di item e stati LR(0)
costruzione della tabella LR(0)
esempio di parsing LR(0)
Lezione 5 (11 febbraio 2009, 14:30-16:30)
esercizi sul parsing LR(0)
il parsing SLR
esempio di parsing SLR
Laboratorio 3 (12 febbraio 2009, 16:30-18:30)
Lezione 6 (18 febbraio 2009, 10:30-12:30)
Azioni semantiche associate alle produzioni
Esempi di decorazione di una grammatica con azioni semantiche
Uso delle azioni semantiche per costruire la sintassi astratta del
codice sorgente
Struttura e classi della sintassi astratta Kitten
Laboratorio 4 (19 febbraio 2009, 16:30-18:30)
Lezione 7 (24 febbraio 2009, 16:30-18:30)
item LR(1)
costruzione della tabella LR(1)
Automa e tabella LALR(1)
Gerarchia di parsing delle grammatiche
Lezione 8 (25 febbraio 2009, 10:30-12:30)
Risoluzione dei conflitti con JavaCup
Il parsing con grammatiche ambigue: il caso delle espressioni aritmetiche
Il parsing con grammatiche ambigue: il caso dell'if/then/else
Algoritmi a discesa ricorsiva sulla sintassi astratta
Determinazione delle variabili di un'espressione o comando
Determinazione delle variabili dichiarate ma non usate
Determinazione del codice morto
Laboratorio 5 (26 febbraio 2009, 16:30-18:30)
Lezione 9 (4 marzo 2009, 10:30-12:30)
Analisi semantica: sue funzioni
Classi per i tipi semantici di Kitten
Implementazione della relazione di sottotipaggio
Analisi semantica delle espressioni di tipo Kitten
Analisi semantica delle espressioni Kitten e sua implementazione
Laboratorio 6 (5 marzo 2009, 16:30-18:30)
Lezione 10 (10 marzo 2009, 16:30-18:30)
Analisi semantica dei comandi Kitten e sua implementazione
Esercizi sull'analisi semantica
Lezione 11 (12 marzo 2009, 16:30-18:30 aula B)
Introduzione alla generazione del Kitten bytecode
I bytecode Kitten
I bytecode per la chiamata e il ritorno da metodo e costruttore
La compilazione per continuazione
La compilazione attiva (e quella tipata) delle espressioni
Lezione 12 (17 marzo 2009, 16:30-18:30)
La compilazione condizionale delle espressioni booleane
La compilazione passiva dei leftvalue
Lezione 13 (18 marzo 2009, 10:30-12:30)
La compilazione dei comandi
Esercizi sulla compilazione
Laboratorio 7 (19 marzo 2009, 16:30-18:30)
Primo appello 2 aprile 2009 alle 14:30
Progetto valido fino a fine luglio:
Si definiscano i token e le produzioni grammaticali per il parsing delle
funzioni parziali ricorsive. In dettaglio, le funzioni parziali ricorsive
sono
- N, che rappresenta la funzione f(x)=x+1,
- C(j,n) che rappresenta la funzione f(x1,...,xn)=j,
- U(j,n) che rappresenta la funzione f(x1,...,xn)=xj,
- Sost(g,[h1,...,hn]), con n≥ 1, che rappresenta la funzione
f(x1,...,xm)=g(h1(x1,...,xm),...,hn(x1,...,xm)),
- Mu(g) che rappresenta la funzione f(x1,...,xm)=
min{y|g(x1,...,xm,y)=0 e per ogni i≤y.g(x1,...,xm,y)
è definita},
- Prim(g,h) che rappresenta la funzione f tale che
f(x1,...,xm,y)=g(x1,...,xm) se y=0 ed
f(x1,...,xm,y)=h(x1,...,xm,y-1,f(x1,...,xm,y-1))
se y>0,
dove j,m,n sono numeri
naturali e g,h,h1,...,hn sono funzioni parziali ricorsive.
Si scrivano le classi di sintassi astratta per tale linguaggio,
tutte sottoclassi di una radice comune Absyn, e si faccia
costruire l'albero di sintassi astratta dalle produzioni della grammatica.
Si scriva dentro tali classi un metodo ricorsivo
arity() che restituisce l'arietà
(numero di argomenti) della funzione rappresentata;
poi un metodo ok() che restituisce true se e solo se
la classe astratta e le sue sottocomponenti sono costruite bene,
cioè rispettando le arietà. Infine si aggiunga un metodo
alle classi di sintassi astratta, in modo da generare del Java bytecode
che esegue la funzione parziale ricorsiva. Per la generazione di una classe
di Java bytecode che contiene un metodo che implementa la funzione parziale
ricorsiva si può usare
questa classe: basta
definirne una sottoclasse che implementa il metodo bytecode() e
il cui costruttore è concatenato a quello di questa classe
.
Si provi a scrivere qualche funzione parziale ricorsiva, a compilarla e ad
eseguire il Java bytecode risultante.