Linguaggi e compilatori - primo modulo

Corso di laurea magistrale in Informatica


Questa pagina vuole fornire una serie di informazioni specifiche al primo modulo del corso di Linguaggi e compilatori. Si rimanda alla pagina principale del corso per una prentazione complessiva.

Docenti

Finalità del modulo

Nel primo modulo vengono presentati due argomenti, tra loro non strettamente connessi. Il primo è il formalismo dei sistemi di riscrittura, formalismo che permette la descrizione della computazione nei linguaggi funzionali e più in generale nei linguaggi logici dichiartivi. La seconda parte del modulo è dedicata alla teoria dei compilatori, in particolare agli analizzatori sintattici, ossia quella parte dei compilatori che riconoscono la struttura sintattica del programma, passo necessario per la successiva generazione del codice intermedio.

Programma

Modelli computazionali: sistemi di riscrittura.
Sistemi di riscrittura su termini del primo ordine. Matching - unificazione. Sistemi di riscrittura di ordine superiore.
Compilatori: analisi sintattica.
Parsing top-down. Automi a pila. Linguaggi LL(n). Error recovering. Parsing bottom-up. Automi SLR, LR, LALR.

Libri di testo e pagine svolte

Sistemi di Riscrittura
[Ter06] Terese. TERESE LITE . Vrije Universiteit, 2006. (estratto dal libro Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003)
Sezioni (e sottosezioni) svolte: Con n.0 si indica la prima parte del capitolo n, prima dell'inizio della sezione n.1.
Compilatori
[ALSU07] Aho A.V., Lam M.S., Sethi R. , Ullman J.D. Compilers. Principles, Techniques and Tools - 2nd Edition Pearson Addison Wesley, 2007.
Edizione italiana: Compilatori Principi, tecniche e strumenti - 2/Ed. Pearson Education, 2009.
Il capitolo 4 contiene il materiale relativo agli analizzatori sintattici.

LUCIDI presentati a lezione

Sistemi di riscrittura
Lucidi in formato pdf.
Analisi sintatittica.
Lucidi in formato pdf.

MODALITÀ di svolgimento dell'esame

Si rimanda alla pagina web del corso su elearning per una descrizione completa delle modalità d'esame. Si riassumo qui solo alcune informazioni relative al primo modulo del corso.
L'esame consiste in un progetto da sviluppare in gruppo e da una parte orale. Ogni gruppo è formato da 2-4 persone, preferibilmente 3.
Il progetto può essere svolto come un unico progetto globale, oppure diviso in 3 sottoprogetti da svolgere durante l'anno. Per ciascun sottoprogetto è previsto un limitato intervallo di tempo entro il quale il progetto può essere ritirato. Mentre per il progetto globale non ci sono restrizioni specifiche sui tempi di ritiro.
Il primo sottoprogetto, relativo agli argomenti trattati nel primo modulo, può essere ritirato per tutto il periodo della sessione d'esami di gennaio-febbraio, oppure durante il secondo periodo didattico, ma in questo caso, limitatamente ai fine settimana, ossia ritiro del testo dal venerdì pomeriggio, consegna dell'elaborato entro il lunedì mattina. Il ritiro del primo sottoprogetto è fatto su appuntamento, eventualmente per email. L'appuntamento può essere preso da un singolo componente del gruppo che dovrà anche fornire nome, numero di matricola e indirizzo e-mail di ciascun altro componente.
Per quanto riguarda la consegna, questa dovrà avvenire per email fornendo la soluzione in formato pdf. Sono accettate anche soluzioni, o parti di soluzioni, scritte a penne scannarizzate, a condizione che queste siano chiare e svolte con un certo ordine. I tempi di consegna dipendono dal numerosità del gruppo secondo questo schema: gruppo di 2 persone: 56 ore dopo il ritiro; gruppo di 3 persone 48 ore dopo il ritiro; gruppo di 4 persone 36 dopo il ritiro. I tempi di consegna sono rigidi e in ogni caso va inviata entro i tempi stabiliti e soluzione, anche incompleta, del progetto assegnato.

ESEMPI DI PROGETTI proposti negli anni passati e lista di esercizi con soluzione