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.

English version: The objective is to illustrate the main concepts related to the syntax and semantics of programming languages, and their applications for the development of compilers.

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.

English version:

01. Introduction to compiling:
  01.01 Architecture and phases of a compiler.
  01.02 Grammars, formal languages, Chomsky hierarchy.

02. Regular languages:
  02.01 Deterministic finite-state automata.
  02.02 Non-deterministic finite-state automata.
  02.03 Finite-state automata with ε-transitions.
  02.04 Right-linear grammars.
  02.05 Closure properties of regular languages.
  02.06 Regular expressions.
  02.07 Regular expressions and finite-state automata.
  02.08 Pumping lemma for regular languages.
  02.09 Minimization of finite-state automata.

03. Context-free languages:
  03.01 Context-free grammars.
  03.02 Simplification of context-free grammars, Chomsky normal form.
  03.03 Pumping theorem for context-free languages, closure properties of context-free languages.
  03.04 Non-deterministic push-down automata.
  03.05 Context-free grammars and non-deterministic push-down automata.

04. Syntax analysis:
  04.01 Top-down parsing, LL(1) parsers and grammars.
  04.02 Bottom-up parsing.
  04.03 SLR parsers e grammars.
  06.04 LR(1) and LALR(1) parsers and grammars.

05. Semantic analysis:
  05.01 Attributed syntax trees, abstract syntax trees.
  05.02 Names, scope rules, management of the symbol table.
  05.03 Data types and type checking.

06. Code generation:
  06.01 Run-time environments.
  06.02 Intermediate code generation.
  06.03 Compilation of arithmetic expressions.
  06.04 Compilation of boolean expressions.
  06.05 Compilation of statements and control structures.

07. Operational semantics:
  07.01 Natural operational semantics for a simple imperative language (While).
  07.02 Operational semantics for While with procedure (static and dynamic scope).

08. Denotational semantics:
  08.01 Denotational semantics for While.
  08.02 Denotational semantics for While with procedures (call-by-value and call-by-reference).

09. Functional programming in Haskell:
  09.01 Introduction to Haskell: expressions, values, primitive data types.
  09.02 Functions, recursion, and polymorphism.
  09.03 Pairs, tuples, and lists.
  09.04 Higher-order functions.
  09.05 Datatypes.
  09.06 Modules.
  09.07 Monads and input/output.

10. Laboratory activity:
  10.01 Practice on expressions, values, primitive data types.
  10.02 Practice on functions and recursion.
  10.03 Practice on pairs, tuples, and lists.
  10.04 Practice on higher-order functions.
  10.05 Practice on datatypes.
  10.06 Practice on input/output.

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

Modalità didattiche

Lezioni teoriche ed esercitazioni di laboratorio, sia in presenza che a distanza.

English version: Theory lectures and laboratory exercises, both face-to face and on-line.

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, prova al terminale e prova orale.

English version: Written exam, lab exam, and oral exam.

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.

L'insegnamento è erogato sia in presenza che a distanza nel Corso di Laurea in Informatica Applicata.

English version: The course is offered both face-to-face and on-line within the Laurea Degree Program in Applied Computer Science.