Corsi di Laurea Corsi di Laurea Magistrale Corsi di Laurea Magistrale
a Ciclo Unico
Scuola di Ingegneria
INGEGNERIA INFORMATICA
Insegnamento
COMPILATORI
INP6075737, A.A. 2019/20

Informazioni valide per gli studenti immatricolati nell'A.A. 2018/19

Principali informazioni sull'insegnamento
Corso di studio Corso di laurea magistrale in
INGEGNERIA INFORMATICA
IN0521, ordinamento 2009/10, A.A. 2019/20
N0
porta questa
pagina con te
Crediti formativi 6.0
Tipo di valutazione Voto
Denominazione inglese COMPILERS
Dipartimento di riferimento Dipartimento di Ingegneria dell'Informazione (DEI)
Sito E-Learning https://elearning.dei.unipd.it/course/view.php?idnumber=2019-IN0521-000ZZ-2018-INP6075737-N0
Obbligo di frequenza No
Lingua di erogazione ITALIANO
Sede PADOVA
Corso singolo È possibile iscriversi all'insegnamento come corso singolo
Corso a libera scelta È possibile utilizzare l'insegnamento come corso a libera scelta

Docenti
Responsabile GIORGIO SATTA ING-INF/05

Dettaglio crediti formativi
Tipologia Ambito Disciplinare Settore Scientifico-Disciplinare Crediti
CARATTERIZZANTE Ingegneria informatica ING-INF/05 6.0

Organizzazione dell'insegnamento
Periodo di erogazione Secondo semestre
Anno di corso II Anno
Modalità di erogazione frontale

Tipo ore Crediti Ore di
didattica
assistita
Ore Studio
Individuale
LEZIONE 6.0 48 102.0

Calendario
Inizio attività didattiche 02/03/2020
Fine attività didattiche 12/06/2020
Visualizza il calendario delle lezioni Lezioni 2019/20 Ord.2009

Commissioni d'esame
Commissione Dal Al Membri
3 A.A. 2019/2020 01/10/2019 15/03/2021 SATTA GIORGIO (Presidente)
MORO MICHELE (Membro Effettivo)
PIZZI CINZIA (Supplente)
2 A.A. 2018/2019 01/10/2018 15/03/2020 SATTA GIORGIO (Presidente)
MORO MICHELE (Membro Effettivo)
PIZZI CINZIA (Supplente)

Syllabus
Prerequisiti: Per poter seguire l'insegnamento con profitto è necessario un buon livello di comprensione degli argomenti tradizionalmente svolti in un corso di automi e linguaggi formali, in particolare delle espressioni regolari, degli automi a stati finiti, delle grammatiche context-free e degli automi push-down. È inoltre richiesta una conoscenza solida della programmazione di un computer e dei linguaggi di programmazione procedurali in genere, e del linguaggio di programmazione C in particolare. Si assume infine una conoscenza generale degli algoritmi e delle strutture dati più comuni, quali gli alberi ed i grafi.
Conoscenze e abilita' da acquisire: Il corso ha tre obiettivi chiave: (i) l’apprendimento di tecniche di traduzione da un linguaggio di programmazione ad alto livello ad un linguaggio macchina; (ii) l’acquisizione della capacità di progettare e realizzare un semplice compilatore; (iii) lo sviluppo delle soft skills necessarie al lavoro di gruppo.

Più specificatamente, le conoscenze teoriche da acquisire riguardano:
1. il funzionamento del front-end di un compilatore, nei suoi principali aspetti lessicale, sintattico e semantico
2. le tecniche di traduzione guidata dalla struttura sintattica
3. alcune tecniche per l’analisi statica dei programmi e l’ottimizzazione del codice

Mediante il lavoro in piccoli gruppi per il progetto e la realizzazione di un mini-compilatore, lo studente sviluppa inoltre le seguenti abilità tecniche e soft skills:
1. familiarità tecnica con strumenti pratici (Flex e Bison) per la realizzazione di traduttori di software
2. capacità di individuare le soluzioni in base alle conoscenze acquisite (problem solving)
3. attitudine al team-working

Aggiungo un breve commento sulle motivazioni per lo studio delle tecniche di compilazione. In primo luogo questa materia occupa un ruolo fondazionale nel campo dell’informatica: in fatti, la teoria dei compilatori rappresenta probabilmente il più importante contributo scientifico allo sviluppo e alla diffusione delle tecnologie informatiche. In secondo luogo, questa materia offre importanti sviluppi applicativi. Anche se lo studente non verrà mai coinvolto nella propria carriera lavorativa nel progetto di un nuovo compilatore (pochissime aziende al mondo si occupano di ciò) è comunque altamente probabile che egli/ella si trovi ad impiegare metodologie e tecniche che di tale teoria fanno parte: dagli automi e le grammatiche come formalismi per definire il comportamento di un sistema software, alle tecniche per realizzare traduttori molto più semplici di un compilatore vero e proprio, come ad esempio un interprete per un file di configurazione, per un linguaggio di interfaccia, o per un linguaggio di comandi diretti ad una app oppure ad un qualsiasi dispositivo elettronico.
Modalita' di esame: La verifica delle conoscenze apprese e delle abilità attese è effettuata mediante due prove:
1. prova scritta obbligatoria, che prevede l’esposizione delle nozioni teoriche apprese nel corso e la soluzione di esercizi che richiedono l’applicazione di tecniche di traduzione
2. progetto obbligatorio (in gruppi di max due persone) che prevede la specifica di un semplice linguaggio di programmazione di alto livello e la progettazione di un relativo compilatore; il progetto viene seguito con continuità dal docente, e si conclude con una presentazione ed colloquio finale
Criteri di valutazione: I criteri di valutazione utilizzati per la verifica delle conoscenze apprese all’esame scritto finale sono:
1. completezza delle conoscenze teoriche acquisite
2. capacità di risolvere problemi di traduzione

I criteri utilizzati durante i colloqui intermedi e finale nella valutazione del progetto, al fine di verificare l’acquisizione delle abilità tecniche e delle soft-skills richieste, sono:
1. familiarità con i tool utilizzati
2. capacità di sviluppare e comunicare le proprie idee nell’ambito del progetto
3. capacità di team working

Ai fini della valutazione complessiva verrà inoltre considerata la partecipazione attiva alle discussioni tecniche sul forum elettronico durante il periodo di svolgimento del corso, ed i meriti acquisiti nella soluzione dei contest proposti a lezione.
Contenuti: Introduzione: Linguaggi di programmazione e processori di linguaggi. Linguaggi macchina, linguaggi assembler ed evoluzione dei linguaggi di programmazione. Compilatori, interpreti e macchina virtuale. Struttura di un compilatore e fasi della compilazione. Front end e back end. Passate di un compilatore.

Analisi lessicale: Operazioni preliminari, token e lessemi. Espressioni regolari e definizioni regolari. Eliminazioni dell'ambiguità. Automi a stati finiti deterministici e nondeterministici, loro implementazione e simulazione. Generazione automatica di un analizzatore lessicale: il programma Flex.

Analisi sintattica: Grammatiche context-free, alberi di derivazione e ambiguità. Automi a pila deterministici e non deterministici. Errori sintattici e metodi di gestione degli errori. Parser top-down: parser a discesa ricorsiva e parser LL(1). Eliminazione della ricorsione sinistra; fattorizzazione sinistra, insiemi First e Follow. Parser bottom-up: parser shift-reduce, item LR(0) e parser SLR. Generazione automatica di parser e di traduttori: il programma Bison.

Analisi semantica: Semantica statica e dinamica. Grammatiche con attributi. Traduzione guidata dalla sintassi. Albero sintattico annotato, calcolo degli attributi e grafo delle dipendenze. Grammatiche con S-attributi e grammatiche con L-attributi. Ordinamento topologico del grafo delle dipendenze. Type checking, equivalenza d tipi e type coercion. Tabella dei simboli.

Generazione del codice: Codice intermedio e codice a tre indirizzi. Strutture dati per l’implementazione del codice a tre indirizzi. Generazione del codice per i più frequenti costrutti di programmazione: definizioni, array, if, while. Esempi di ottimizzazione del codice indipendente dalla macchina.
Attivita' di apprendimento previste e metodologie di insegnamento: Il corso viene erogato mediante lezioni frontali che utilizzano materiale didattico digitale (testuale e video) distribuito agli studenti in anticipo rispetto alle lezioni. Sono inoltre previsti colloqui intermedi tra il docente ed i gruppi di lavoro per guidare lo sviluppo dei progetti. Al fine di favorire la discussione, la collaborazione, e l'auto-verifica del processo di apprendimento da parte degli studenti, sulla piattaforma moodle vengono messi a disposizione due forum elettronici supervisionati dal docente, in cui poter rispettivamente discutere aspetti teorici della materia ed aspetti pratici legati allo sviluppo dei progetti. Infine, per incoraggiare la partecipazione attiva degli studenti allo svolgimento delle lezioni e motivare gli stessi a mantenere il passo con gli argomenti svolti, vengono proposti con continuità dal docente dei piccoli contest, premiati con dei bonus di cui si tiene conto nella valutazione finale.
Eventuali indicazioni sui materiali di studio: Gli argomenti del corso sono trattati nel libro di testo di riferimento. Viene inoltre fornito mediante la piattaforma moodle materiale didattico aggiuntivo a sostegno del corso, nella forma dei lucidi svolti a lezione, di esercizi svolti, e di video di esperti della materia.
Testi di riferimento:
  • A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman, Compilatori: Principi, tecniche e strumenti. --: Pearson Education Italia, 2009. seconda edizione Cerca nel catalogo

Didattica innovativa: Strategie di insegnamento e apprendimento previste
  • Lecturing
  • Problem based learning
  • Working in group
  • Problem solving
  • Flipped classroom
  • Active quiz per verifiche concettuali e discussioni in classe
  • Utilizzo di video disponibili online o realizzati
  • Files e pagine caricati online (pagine web, Moodle, ...)

Didattica innovativa: Software o applicazioni utilizzati
  • Moodle (files, quiz, workshop, ...)

Obiettivi Agenda 2030 per lo sviluppo sostenibile
Istruzione di qualita'