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 Grammatiche lineari destre.
  02.05 Proprietà di chiusura dei linguaggi regolari.
  02.06 Espressioni regolari.
  02.07 Relazione tra espressioni regolari e automi a stati finiti.
  02.08 Pumping lemma per linguaggi regolari.
  02.09 Minimizzazione di automi a stati finiti.

03. Linguaggi liberi:
  03.01 Grammatiche libere e alberi sintattici.
  03.02 Semplificazione delle grammatiche libere, forma normale di Chomsky.
  03.03 Pumping lemma per linguaggi liberi, proprietà di chiusura dei linguaggi liberi.
  03.04 Automi a pila non deterministici.
  03.05 Relazione tra grammatiche libere e automi a pila non deterministici.

04. Analisi sintattica:
  04.01 Parsing top-down, parser e grammatiche LL(1).
  04.02 Parsing bottom-up.
  04.03 Parser e grammatiche SLR.
  04.04 Parser e grammatiche LR(1) e LALR(1).

05. Analisi semantica:
  05.01 Alberi attribuiti, alberi di sintassi astratta.
  05.02 Nomi e regole di scoping.
  05.03 Tipi di dato e type checking.

06. Generazione del codice:
  06.01 Organizzazione della memoria e passaggio dei parametri.
  06.02 Generazione del codice intermedio.
  06.03 Compilazione di espressioni aritmetiche.
  06.04 Compilazione di espressioni booleane.
  06.05 Compilazione di comandi e costrutti di controllo.

07. Semantica operazionale:
  07.01 Semantica operazionale naturale di un semplice linguaggio imperativo (While).
  07.02 Semantica operazionale di While con procedure (scoping statico e dinamico).

08. Semantica denotazionale:
  08.01 Semantica denotazionale di While.
  08.02 Semantica denotazionale di While con procedure (call-by-value e call-by-reference).

09. Programmazione funzionale in Haskell:
  09.01 Introduzione al linguaggio Haskell: espressioni, valori, tipi di dato primitivi.
  09.02 Funzioni e ricorsione.
  09.03 Polimorfismo.
  09.04 Coppie, tuple e liste.
  09.05 Funzioni di ordine superiore, specializzazione e currying.
  09.06 Definizione di tipi di dato: alias di tipo e tipi algebrici.
  09.07 Moduli.
  09.08 Monadi e input/output.

10. Attività di laboratorio:
  10.01 Esercizi di base su espressioni, valori e tipi.
  10.02 Esercizi su funzioni e ricorsione.
  10.03 Esercizi su coppie, tuple e liste.
  10.04 Esercizi su funzioni di ordine superiore.
  10.05 Esercizi su tipi algebrici.
  10.05 Esercizi su input/output in Haskell.
  10.06 Analisi lessicale in Haskell.
  10.07 Analisi sintattica in Haskell.

Logica Matematica, Programmazione degli Elaboratori, Architettura degli Elaboratori, Algoritmi e Strutture Dati.

Modalità didattiche

Lezioni frontali ed esercitazioni di laboratorio

Obblighi

Nessuno.

Testi di studio

Hopcroft, Motwani, Ullman, "Automi, Linguaggi e Calcolabilità", Addison-Wesley, 2009

Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, 2007

Aho, Lam, Sethi, Ullman, "Compilers: Principles, Techniques, and Tools", Addison-Wesley, 2007

Nielson, Nielson, "Semantics with Applications: An Appetizer", Springer, 2007

Thompson, "The Craft of Functional Programming", Addison-Wesley, 1999.

Hutton, "Programming in Haskell", Cambridge University Press, 2007.

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.

Il corso è erogato sia nel "percorso in presenza" che nel "percorso online" del Corso di Laurea di Informatica Applicata.