Compilatori 2006
docente: Fausto Spoto fausto.spoto@univr.it
Il compilatore Kitten versione 13/1/2006 (funziona solo su Java 1.5)
Il compilatore Kitten versione 17/1/2006 (funziona anche su Java 1.4)
L'analizzatore di grammatiche GRAN e la sua
documentazione, di
Enrico Masserdotti: emasse AT jumpy DOT it
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
Dispense
Lucidi:
Testi d'esame:
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
Lezione 1 (13 gennaio 2005)
introduzione al corso
compilatori
esempi di programmi Kitten
espressioni, comandi, valori, tipi
relazione di sottotipo
Laboratorio 1 (17 gennaio 2005)
esempi di programmi Kitten
installazione del compilatore Kitten
esperimenti di programmazione in Kitten
Lezione 2 (18 gennaio 2006)
tipaggio statico e dinamico
rappresentazione boxed e unboxed dei valori
tipaggio forte e debole
Lezione 3 (20 gennaio 2006)
richiamo sul late binding dei metodi
analisi lessicale:
token e valore lessicale
espressioni regolari
automi non deterministici e automi deterministici a stati finiti
priorità sulle regole e longest match
Lezione 4 (24 gennaio 2006)
generazione automatica dell'analizzatore lessicale tramite JLex
specifica dei token Kitten
modalità per commenti e stringhe
introduzione all'analisi sintattica
grammatiche
parsing predittivo
insiemi nullable e first
Lezione 5 (25 gennaio 2006)
insieme follow
esempi di parsing predittivo
Lezione 6 (27 gennaio 2006)
esempi di parsing predittivo
gerarchia LL(k)
una grammatica ricorsiva a sinistra non è LL(k)
relazione di inclusione fra le famiglie LL(k)
automi a pila
Lezione 7 (31 gennaio 2006)
esempio di parsing LR(0)
item LR(0)
chiusura di un insieme di item
costruzione dell'automa LR(0)
costruzione della tabella LR(0)
conflitti sposta/riduci
Lezione 8 (1 febbraio 2006)
esempio di costruzione dell'automa e della tabella LR(0)
parsing SLR
inclusione di LR(0) in SLR
esempio di costruzione della tabella SLR
conflitti riduci/riduci
Lezione 9 (3 febbraio 2006)
esempi di parsing LL(1), LR(0) ed SLR
alberi di parsing
grammatiche ambigue
una grammatica ambigua non è né LL(k) né LR(k) né SLR
Lezione 10 (7 febbraio 2006)
esempi di disambiguazione di grammatiche
associazione di un else all'ultimo then
inclusioni insiemistiche fra le classi di grammatiche
esercizio sul parsing LL(1), LR(0) ed SLR
item LR(1), chiusura di item LR(1), stati LR(1)
costruzione dell'automa a stati finiti LR(1)
Lezione 11 (8 febbraio 2006)
costruzione della tabella LR(1)
esercizio sul parsing LR(1)
Lezione 12 (10 febbraio 2006)
esercizio sul parsing LR(1)
parsing con grammatiche ambigue: esempio dell'if/then/else e delle grammatiche di operatori con precedenze e associatività
Lezione 13 (14 febbario 2006)
parsing LALR(1)
costruzione dell'analizzatore sintattico con JavaCup
grammatica per il linguaggio Kitten
leftvalue
decorazione di una grammatica con azioni semantiche
Laboratorio 2 (15 febbraio 2006)
- Si aggiunga al compilatore Kitten l'espressione condizionale
exp ? exp : exp, che
valuta la prima espressione e, se è vera, valuta e restituisce la
seconda espressione altrimenti valuta e restituisce la terza espressione.
- A tal fine si inizi con l'aggiungere i token per ? e :
nei file lexical/Kitten.lex, syntactical/Kitten.cup
e lexical/Main_lexical.java.
Sia dia make syntactical e poi make lexical e si
provi se i due nuovi token sono riconosciuti
(vi serve una classe Kitten di prova che contenga l'espressione
condizionale. Scrivetela!)
- Si aggiunga quindi una produzione alla grammatica di Kitten contenuta
in syntactical/Kitten.cup, usando come azione semantica,
per adesso, {: RESULT = new IntLiteral(0,0); :}.
Si dia make syntactical
e si provi se l'espressione condizionale viene accettata su un
file di prova che la contiene.
Lezione 14 (17 febbraio 2006)
esercizi sulle azioni semantiche
variabili usabili nelle azioni semantiche
sintassi astratta
classi di sintassi astratta: classe absyn/Absyn.java
e sue sottoclassi
gerarchia di sintassi astratta per le espressioni Kitten
costruzione della sintassi astratta per le espressioni
tramite azioni semantiche
Laboratorio 3 (21 febbraio 2006)
- Si implementi la classe di sintassi astratta per l'espressione
condizionale (nome, superclasse, eventuali campi e costruttore) a
partire da questo schema.
- Si aggiunga un'azione semantica che sintetizza l'albero di sintassi
astratta per la produzione grammaticale dell'espressione condizionale.
- Si completi, nella classe di sintassi astratta
per l'espressione condizionale, il metodo toDot$0(), in modo
da generare il codice dot che rappresenta tale nodo di sintassi astratta.
Lo si provi sul solito esempio di file Kitten che contiene l'espressione
condizionale, vedendo se il file postscript risultante effettivamente
contiene un nodo per il condizionale e i suoi figli.
Lezione 15 (22 febbraio 2006)
introduzione all'analisi semantica: verifica e annotazione
gerarchia dei tipi Kitten dentro al package types
metodi canBeAssignedTo() e leastCommonSupertype()
sui tipi
Lezione 16 (24 febbraio 2006)
regole di analisi semantica per l'annotazione delle espressioni di tipo
implementazione delle regole di analisi semantica delle espressioni di
tipo tramite un metodo Type typeCheck()
regole di analisi semantica per l'annotazione e la verifica delle
espressioni (prima parte): ambiente
implementazione delle regole di analisi semantica delle espressioni
tramite un metodo Type typeCheck(TypeChecker)
Laboratorio 4 (28 febbraio 2006)
- Si scriva una regola di analisi semantica per l'espressioni condizionale.
Il tipo assegnato all'espressione condizionale deve essere un
sovratipo del tipo del valore dell'espressione condizionale, qualsiasi
cosa accada a tempo di esecuzione
- Si implementi la regola di analisi semantica per l'espressione
condizionale dentro la sua classe di sintassi astratta, sotto forma
di un metodo protected Type typeCheck$0(TypeChecker checker)
- Si compili il compilatore Kitten con make semantical
- Si provi a compilare il programma Kitten
Conditioner.kit.
La sua analisi semantica non deve segnalare alcun errore!
Lezione 17 (1 marzo 2006)
regole di analisi semantica per la creazione di un oggetto e per
l'espressioni di chiamata a un metodo: identificazione del costruttore
o del metodo più specifico
regola di analisi semantica per i cast: cast verso il basso
analisi semantica dei comandi
regole di analisi semantica per il comando di dichiarazione di una
variabile, per il comando condizionale e per il ciclo while
Lezione 18 (3 marzo 2006)
le regole di analisi semantica per l'assegnamento, lo scope locale, il
ciclo for e il return
la determinazione del codice morto e dei metodi non void che
non terminano necessariamente con un return
il bytecode Kitten: istruzioni di manipolazione dello stack,
operazioni aritmetiche e di confronto, operazioni sugli oggetti
e operazioni condizionali
Lezione 19 (7 marzo 2006)
il bytecode Kitten: operazioni sugli array
la generazione del bytecode Kitten per le espressioni
la compilazione delle espressioni come test
Laboratorio 5 (8 marzo 2006)
scrittura della regola di generazione del codice per l'espressione condizionale
implementazione della regola di generazione del codice per l'espressione condizionale
Lezione 20 (10 marzo 2006)
la compilazione della creazione di un oggetto, della chiamata di metodo e del cast
la compilazione tipata delle espressioni
la compilazione passiva dei leftvalue
la generazione del codice per i comandi
la traduzione da Kitten bytecode in Java bytecode
Fine del corso
Progetto valido fino a fine luglio
Il progetto consiste in primo luogo nei laboratori svolti durante il corso, ovvero nell'analisi lessicale, sintattica, semantica e nella generazione del bytecode Kitten per l'espressione condizionale.
Una seconda parte del progetto consiste nell'aggiungere all'analisi semantica di Kitten la verifica che una variabile, quando è utilizzata, è già stata sicuramente inizializzata. L'idea è di aggiungere ai comandi un metodo
Env intCheck(Env env)
che calcola l'insieme delle variabili sicuramente inizializzate dopo un comando, conoscendo lo stesso insieme prima del comando. Occorrerà aggiungere qualcosa anche alle espressioni Kitten, dal momento che un'espressione può usare una variabile e in tal caso tale variabile deve essere stata inizializzata.
L'implementazione di Env è libera. È essenzialmente un insieme o, equivalentemente, una funzione dalle variabili nei booleani.
Progetto valido dal primo agosto
(10 punti fino a tutto agosto, 9 per settembre, 8 ottobre, 7 novembre e dicembre)
Aggiungete a Kitten il comando
do com exp times
che valuta exp ed esegue com exp volte. Se
exp contiene un numero negativo o zero allora non esegue mai
com. L'espressione exp deve essere valutata una e una sola volta.
Si implementi quindi un metodo sign() per le espressioni Kitten
che restituisce il segno del valore contenuto dentro ogni espressione
di un programma a tempo di esecuzione. Le tre possibilità saranno
positivo, non positivo e non so. Si usi quindi questa informazione nella
compilazione della divisione, generando quando possibile un bytecode
checkeddiv (da scrivere)
piuttosto che div, il quale non controlla
la non-nullità del divisore a tempo di esecuzione.