Il Corso ha l'obiettivo di introdurre i concetti di base relativi alla sintassi e alla semantica dei linguaggi di programmazione e le loro applicazioni allo sviluppo dei compilatori.

01. Introduzione alla compilazione: 01.01 Architettura e fasi di un compilatore. 01.02 Grammatiche a struttura di frase, linguaggi formali, classificazione di Chomsky. 02. Linguaggi regolari: 02.01 Automi a stati finiti deterministici. 02.02 Automi a stati finiti non deterministici. 02.03 Automi a stati finiti con ε-transizioni. 02.04 Propriet? di chiusura dei linguaggi regolari. 02.05 Espressioni regolari. 02.06 Relazione tra espressioni regolari e automi a stati finiti. 02.07 Pumping lemma per linguaggi regolari. 02.08 Minimizzazione di automi a stati finiti. 02.09 Grammatiche lineari destre. 03. Linguaggi liberi: 03.01 Grammatiche libere. 03.02 Alberi sintattici, ambiguit?, disambiguazione. 03.03 Semplificazione delle grammatiche libere, forma normale di Chomsky. 03.04 Pumping theorem per linguaggi liberi, propriet? di chiusura dei linguaggi liberi. 03.05 Automi a pila non deterministici. 03.06 Relazione tra grammatiche libere e automi a pila non deterministici. 04. Fondamenti di programmazione funzionale: 04.01 Introduzione al λ-calcolo non tipato. 04.02 Codifica di dati: booleani, numeri naturali, coppie, liste. 04.03 Operatore di punto fisso e funzioni ricorsive. 05. Programmazione funzionale in OCaml: 05.01 Introduzione al linguaggio OCaml: valutazione di espressioni, tipi di dato primitivi. 05.02 Funzioni. 05.03 Funzioni ricorsive. 05.04 Dichiarazioni locali e pattern matching. 05.05 Type inference e polimorfismo. 05.06 Funzioni di ordine superiore, currying. 05.07 Programmazione funzionale con side-effects: riferimenti, I/O, tabelle hash. 05.08 Definizione di tipi di dato: alias di tipo e tipi algebrici. 05.09 Programmazione funzionale con tipi algebrici. 05.10 Eccezioni. 05.11 Tipi astratti e sistema dei moduli. 06. Progetto di compilazione: 06.01 Analisi lessicale con ocamllex. 06.02 Analisi sintattica con ocamlyacc. 06.03 Progetto di compilazione: analisi, specifica, implementazione. 07. Analisi sintattica: 07.01 Parsing top-down, parser e grammatiche LL(1). 07.02 Parsing bottom-up. 07.03 Parser e grammatiche SLR. 07.04 Parser e grammatiche LR(1) e LALR(1). 07.05 Alberi attribuiti, alberi di sintassi astratta. 08. Analisi semantica: 08.01 Nomi, regole di scoping e gestione della tabella dei simboli. 08.02 Tipi di dato e type checking. 09. Generazione del codice: 09.01 Organizzazione della memoria e passaggio dei parametri. 09.02 Generazione del codice intermedio. 09.03 Compilazione di espressioni aritmetiche. 09.04 Compilazione di espressioni booleane. 09.05 Compilazione di comandi e costrutti di controllo. 10. Semantica operazionale: 10.01 Semantica operazionale naturale di un semplice linguaggio imperativo (While). 10.02 Semantica operazionale di While con procedure (scoping statico e dinamico). 11. Semantica denotazionale: 11.01 Semantica denotazionale di While. 11.02 Semantica denotazionale di While con procedure (call-by-value e call-by-reference). 12. Attivit? di laboratorio: 12.01 Esercizi di base su OCaml e funzioni non ricorsive. 12.02 Esercizi su funzioni ricorsive. 12.03 Esercizi sulle liste. 12.04 Esercizi su funzioni di ordine superiore. 12.05 Esercizi su tipi algebrici. 12.06 Generazione di analizzatori lessicali con ocamllex. 12.07 Generazione di analizzatori sintattici con ocamlyacc. 12.08 Esercizi sulla generazione di codice intermedio.

Modalità didattiche

Lezioni frontali ed esercitazioni di laboratorio

Obblighi

Nessuno.

Testi di studio

Hopcroft, Motwani, Ullman, "Automi, Linguaggi e Calcolabilit?", Addison-Wesley, 2003 (Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, 2000) (copre le sezioni 01.02, 02, 03 del programma). Nielson, Nielson, "Semantics with Applications: A Formal Introduction", Wiley, 1992 (copre le sezioni 10 e 11 del programma). Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1986 (copre le sezioni 01.01, 07, 08 e 09 del programma). Reade, "Elements of Functional Programming", Addison-Wesley, 1989. Ullman, "Elements of ML Programming (ML97 edition)", 1997. Leroy, "The Objective Caml System", 2002. Gordon, "Introduction to Functional Programming", 1996. Paulson, "Lecture Notes", 1995 (coprono le sezioni 04, 05, 06, 12 del programma).

Modalità di
accertamento

Prova scritta, progetto di laboratorio e prova orale

Disabilità e DSA

Le studentesse e gli studenti che hanno registrato la certificazione di disabilità o la certificazione di DSA presso l'Ufficio Inclusione e diritto allo studio, possono chiedere di utilizzare le mappe concettuali (per parole chiave) durante la prova di esame.

A tal fine, è necessario inviare le mappe, due settimane prima dell’appello di esame, alla o al docente del corso, che ne verificherà la coerenza con le indicazioni delle linee guida di ateneo e potrà chiederne la modifica.