Compilatori 2003/2004
docente: Fausto Spoto fausto.spoto@univr.it
Dispense in linea:
postscript,
pdf
Progetto fino all'analisi semantica, ed esempio di programma Tiger con eccezioni
Progetto per la generazione del codice
Progetto per la generazione del codice senza documentazione bcel (molto piu' piccolo)
Il manuale della libreria BCEL
Il manuale ufficiale della Java Virtual Machine
Making Compiler Design Relevant for Students who will (Most Likely) Never Design a Compiler di Saumya Debray
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
Lezione 1 (12 gennaio 2004)
compilatori, fasi di compilazione.
esempi di programma Tiger
analisi lessicale
token, valore lessicale
alfabeto, linguaggio, espressioni regolari
lista di regole, trasformazione in automa non deterministico a stati finiti
Lezione 2 (14 gennaio 2004)
da automa non deterministico ad automa deterministico
esempi di espressioni regolari e trasformazioni in automi
priorità sulle regole e longest match
Lezione 3 (15 gennaio 2004)
esempi di programmi Tiger
esempi di errori in programmi Tiger
l'interfaccia Parse.Lexer
la classe java_cup.runtime.Symbol
la classe ErrorMsg.ErrorMsg
la specifica Parse/Tiger.lex dell'analizzatore lessicale
uso di JLex
uso dell'analizzatore lessicale
il makefile
Lezione 4 (19 gennaio 2004)
grammatiche libere dal contesto, terminali, non terminali
alberi di parsing, ambiguità
parsing a discesa ricorsiva
funzione NULLABLE
funzione FIRST
Laboratorio 1 (21 gennaio 2004)
aggiunta dei token try, throw, throws e catch al linguaggi Tiger
file modificati: Parse/sym.java, Parse/Tiger.lex, Parse/Main_lexical.java
Lezione 5 (22 gennaio 2004)
funzione FOLLOW
tabella LL(1)
gerarchia di grammatiche e linguaggi LL(k)
Lezione 6 (26 gennaio 2004)
automa a pila
item LR(0)
chiusura di un insieme di items LR(0)
costruzione dell'automa LR(0)
costruzione della tabella LR(0)
grammatiche LR(0)
conflitti shift/reduce
esempi di costruzione dell'automa e della tabella LR(0)
tabella e grammatiche SLR
Lezione 7 (28 gennaio 2004)
esercizi di parsing LR(0) ed SLR
conflitti riduci/riduci
Lezione 8 (29 gennaio 2004)
parsing LR(1)
parsing LALR(1)
gerarchia di grammatiche non ambigue
esercizi di parsing LR(1)
Lezione 9 (2 febbraio 2004)
esercizi di parsing LR(1)
parsing LR(1) con grammatiche ambigue:
il caso dell'if_then/if_then_else
il caso degli operatori binari con associatività e priorità
Lezione 10 (4 febbraio 2004)
uso di CUP
il file Parse/Grm.cup
esempi di programmi Tiger con eccezioni
Laboratorio 2 (5 febbraio 2004)
aggiunta dei costrutti di eccezione alla sintassi Tiger: prima parte
file modificati: Parse/Grm.cup
Lezione 11 (5 febbraio 2004)
classi per la rappresentazione degli alberi di sintassi astratta
costruzione degli alberi di sintassi astratta col parsing LL
costruzione degli alberi di sintassi astratta nel parsing LR
Laboratorio 3 (9 febbraio 2004)
aggiunta dei costrutti di eccezione alla sintassi Tiger: seconda parte
file modificati: Parse/Grm.cup
Lezione 12 (11 febbraio 2004)
classi astratte per la rappresentazione della sintassi astratta di Tiger: gerarchia Absyn
classe Symbol/Symbol.java
Lezione 13 (12 febbraio 2004)
esempi di alberi astratti per Tiger
introduzione all'analisi semantica
classe Symbol/Table.java
Laboratorio 4 (16 febbraio 2004)
definizione delle classi astratte per la sintassi delle eccezioni
aggiunta delle azioni semantiche alla grammatica Tiger
aggiunta dei metodi di stampa delle nuove classi di sintassi astratta
file modificati: le opportune classi aggiunte in Absyn/,
Parse/Grm.cup e Absyn/Print.java
Lezione 14 (18 febbraio 2004)
ambienti tenv e venv per il controllo dei tipi
gerarchia Type per la rappresentazione dei tipi Tiger
gerarchia Entry per la denotazione di variabili e funzioni Tiger
tipi e identificatori predefiniti
funzioni di controllo dei tipi e generazione del codice dentro
Semant/Semant.java
Lezione 15 (19 febbraio 2004)
controllo dei tipi per espressioni
controllo dei tipi per leftvalue
controllo dei tipi per le dichiarazioni di variabile
codice di controllo dei tipi dentro Semant/Semant.java
Lezione 16 (23 febbraio 2004)
controllo dei tipi ricorsivi
controllo della legalità del break
esercizio sul controllo dei tipi di uno switch
Java, Java bytecode, verifica delle classi, javac,
java e javap
Lezione 17 (25 febbraio 2004)
esercizi di controllo dei tipi
specifica della parte di controllo dei tipi del progetto:
- throw exp: l'exp non deve avere tipo VOID
- function...throws idlist: gli identificatori nella
lista devono denotare tipi definiti
- try
exp
catch var v1:t1 exp1
:
catch var vn:tn expn :
Gli identificatori t1,...,tn devono denotare
tipi definiti.
Il controllo di expi va fatto in un ambiente in cui la variabile
vi ha tipo ti. I tipi di exp, exp1, ..., expn
devono essere unificabili (anche tra VOID e NIL)
e il risultato dell'unificazione è il tipo del try
- function...throws idlist = exp:
tutti i tipi che possono essere gettati da exp devono appartenere
ai tipi denotati dagli identificatori in idlist. Per questo
controllo, occorre calcolare l'insieme dei tipi gettabili da
un'espressione, aggiungendo un campo di tipo
java.util.HashSet alla struttura ExpTy.
Non si dimentichi di chiamare .actual() sui tipi!
- si assuma che le dichiarazioni non gettino mai eccezioni.
Laboratorio 5 (26 febbraio 2004)
implementazione del controllo dei tipi per i costrutti di eccezione
file modificati: Semant/Semant.java
Lezione 18 (1 marzo 2004)
descrizione di alcune istruzioni del Java bytecode
esempi di codice Java bytecode
tipi di codice: Nx, Ex, Cx(t,f) e Vx
trasformazioni fra tipi di codice
Lezione 19 (3 marzo 2004)
sottoclassi di Cx(t,f): CxEQ(t,f),
CxLT(t,f) ecc.
generazione del codice per interi, stringhe e nil
generazione del codice per le espressioni binarie
generazione del codice per la sequenza di espressioni
Laboratorio 6 (4 marzo 2004)
implementazione del controllo dei tipi per i costrutti di eccezione
(continuazione)
file modificati: Semant/Semant.java
Lezione 20 (8 marzo 2004)
generazione del codice per le strutture di controllo
generazione della classe Java derivata dai record
stack di attivazione
catena statica
coordinate di accesso delle variabili
stack di attivazione per le funzioni Tiger
Laboratorio 7 (10 marzo 2004)
implementazione del controllo dei tipi per i costrutti di eccezione
(continuazione)
file modificati: Semant/Semant.java
Lezione 21 (11 marzo 2004)
generazione del codice per la chiamata di funzione
generazione del codice per l'accesso alle variabili: codice
VxSimple
esercizi sulla generazione del codice
Lezione 22 (15 marzo 2004)
esercizi di analisi semantica
Lezione 22 (18 marzo 2004)
esercizi di generazione del codice
Parte di laboratorio da sviluppare autonomamente:
implementazione della generazione del codice per il ciclo for
non si implementi la compilazione del break dentro al for