Skip to main content.
May 17th, 2004

Un Compilatore Scritto In Java!

Spim ConsoleEcco qui che vi presento un laboratorio, anzi forse il laboratorio più interessante, che ho fatto nel 2003 all’universita di Informatica a La Sapienza di Roma.

Il laboratorio di compilatori: Ossia creare un compilatore per un semplice linguaggio funzionale di nome Tiger, per creare del codice macchina eseguibile da processori MIPS.

Il corso mirava a dare le basi di teoria dei linguaggi formali, di parsing, di gestione mediante azioni semantiche sia degli aspetti context-sensitive della definizione dei linguaggi di programmazione, sia della loro semantica, necessarie alla realizzazione di compilatori e traduttori per linguaggi di programmazione, sia di tipo general-purpose, sia specializzati.

Il programma:

Analisi Lessicale
Richiami su linguaggi regolari. Passaggi da espressioni regolari a automi finiti non deterministici, ad automi finiti deterministici, ad automi minimi. Derivazione di un analizzatore lessicale da un insieme di espressioni regolari. Rappresentazione sotto forma di tabella e rappresentazione sotto forma di programma. Costruzione delle tabelle di simboli.

Analisi Sintattica
Pumping lemma per linguaggi regolari. Richiami su linguaggi liberi dal contesto. Grammatiche libere dal contesto. Forme normali per grammatiche libere dal contesto. Equivalenza fra linguaggi liberi dal contesto e linguaggi riconosciuti da automi a pila.
Processo di analisi come processo di costruzione di alberi di derivazione. Sintassi astratta e sintassi concreta.
Processi di analisi discendenti: analisi a discesa ricorsiva, analisi LL.
Processi di analisi risalenti: analisi con precedenza degli operatori, analisi LR.

Analisi semantica
Vincoli non esprimibili con grammatiche libere dal contesto. Pumping lemma per grammatiche libere dal contesto. Grammatiche ad attributi. Analisi semantica guidata dalla sintassi. Controllo sulla correttezza dei tipi. Costruzione del codice intermedio: alberi intermedi di rappresentazione.

Generazione del codice.XSpim Debbugger
Organizzazione della memoria. Selezione delle istruzioni. Grafo di flusso. Analisi di vivezza. Allocazione dei registri. Ottimizzazione.

Testi
A.W.Appel, Modern Compiler Implementation in C, Cambridge University Press, 1998.
A. Aho, R. Sethi, J. D. Ullman, Compilers. Principles, Techniques, and Tools, Addison Wesley, 1986

La Realizzazione del progetto è stata in collaborazione con Vassilios Zafiropoulos, grande amico e collega!

Le tecnologie usate nel progetto:
JDK Java 2
JLex: A Lexical Analyzer Generator for Java(TM)
CUP Parser Generator for Java
SPIM MIPS32 Simulator
LaTeX - TexLive Documentazione
GNU Emacs - IDE di sviluppo
GNU Make

Qui potete scaricare il progetto

Download del progetto
Relazione del progetto

Utilizzo:
make
java Main tiger/testcases/helloworld.tig
spim -quiet tiger/testcases/helloworld.tig.s

Esempi
Hello world - Tiger, MIPS
Merge Sort - Tiger, MIPS

Posted by Simone Federici as Post at 2:31 PM CEST