Obiettivi formativi
Lo studente verrà introdotto alle problematiche principali relative allo sviluppo di un compilatore per un linguaggio di programmazione. Per ognuna di esse verranno mostrati i risultati teorici, gli strumenti e le tecniche che consentono di arrivare alla definizione di una corrispondente soluzione algoritmica.
Con riferimento agli Indicatori di Dublino:
Conoscenza e capacità di comprensione:
La suddivisione del processo di compilazione nelle varie fasi porta ad una maggiore comprensione delle difficoltà specifiche per ognuna di esse e ad apprezzarne i corrispondenti risultati teorici e tecniche implementative.
Capacità di applicare conoscenza e comprensione:
I principi e le tecnologie della compilazione trovano applicazione anche in aree diverse rispetto alla traduzione dei linguaggi formali, come l’analisi dei linguaggi naturali e il controllo di correttezza, l’analisi e la trasformazione di documenti (semi-) strutturati.
Autonomia di giudizio:
la complessità dei problemi trattati si presta a sviluppare e mettere a confronto strumenti e tecniche risolutive distinte; la necessità di effettuare una scelta consapevole per individuare l’opzione più adatta per un contesto specifico è di stimolo allo sviluppo dell’autonomia di giudizio.
Abilità comunicative:
la presentazione, in forma di seminario, di un approfondimento individuale su uno degli argomenti del corso fornisce un’ottima occasione per affinare le proprie abilità comunicative (sia nella forma scritta che in quella orale) in un contesto tecnico-specialistico.
Capacità di apprendimento:
lo studio di una problematica complessa come quella della compilazione dei linguaggi formali costituisce un esempio eccellente di applicazione sinergica di importanti risultati teorici e sofisticate tecniche algoritmiche.
Prerequisiti
Conoscenza di almeno un linguaggio di programmazione (imperativo); conoscenza delle principali tecniche algoritmiche per la risoluzione di problemi e per lo sviluppo di strutture dati efficienti.
Contenuti dell'insegnamento
Introduzione: interpreti e compilatori
Analisi lessicale
Analisi sintattica
Analisi di semantica statica
Rappresentazioni intermedie (IR)
Analisi e ottimizzazione della IR
Programma esteso
Introduzione: interpretazione vs compilazione di linguaggi formali; struttura di un compilatore (front-end, middle-end, back-end).
Analisi lessicale: linguaggi regolari, automi a stati finiti e scanner.
Analisi sintattica: specifica della sintassi mediante grammatiche libere da contesto; parser top-down e bottom-up.
Analisi di semantica statica: aspetti della sintassi dipendenti dal contesto; alberi di sintassi astratta, tabelle dei simboli, controllo dei tipi.
Strumenti per la generazione di lexer, parser e analizzatori di semantica statica.
Rappresentazioni intermedie (IR): definizione e generazione.
Analisi e ottimizzazione della IR: analisi locali, analisi intraprocedurali e interprocedurali; alcuni esempi di ottimizzazioni. Cenni alla generazione del codice oggetto.
Bibliografia
Keith Cooper, Linda Torczon
Engineering a Compiler, 2nd Edition
Morgan Kaufmann, 2011
Metodi didattici
Lezioni frontali e esercitazioni passive
Modalità verifica apprendimento
Risultati dell'apprendimento e modalità di verifica
Conoscere le varie componenti che formano un compilatore, i risultati teorici e le tecniche algoritmiche utilizzate nelle varie fasi del processo di compilazione, nonché alcuni strumenti di supporto alla generazione di scanner e parser per linguaggi di programmazione.
Modalità di verifica/esame.
Ad ogni studente verrà assegnato (almeno 21 giorni prima della data prevista per l’appello) un argomento tra quelli presentati durante le lezioni sul quale preparare un seminario di approfondimento, basato su materiale didattico supplementare fornito dal docente. L'esame consisterà in un colloquio orale durante il quale lo studente presenterà il lavoro svolto (massimo 15 minuti) per poi rispondere a domande aperte, sia sull’argomento del seminario, sia su altri argomenti compresi nel programma del corso.
Altre informazioni
