LINGUAGGI DI PROGRAMMAZIONE E COMPILATORI

Obiettivi formativi:

Questo insegnamento ha lo scopo di introdurre i concetti di base relativi alla sintassi e alla semantica dei linguaggi di programmazione e le loro applicazioni allo sviluppo dei compilatori.

Settori scientifico-disciplinari:

INF/01, ING-INF/05.

Crediti:

12.

Modulo:

Unico.

Durata:

Annuale, 112 ore (80 di lezione frontale + 32 di esercitazione guidata).

Frequenza:

Non sono previsti obblighi di frequenza.

Docente:

Dott. Alessandro Aldini.

Programma:

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, ricorsione e polimorfismo.
      09.03 Coppie, tuple e liste.
      09.04 Funzioni di ordine superiore, specializzazione e currying.
      09.05 Definizione di tipi di dato: alias di tipo e tipi algebrici.
      09.06 Moduli.
      09.07 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.

Testi di riferimento:

  • Hopcroft, Motwani, Ullman, "Automi, Linguaggi e Calcolabilitą", Addison-Wesley, 2009
               (Hopcroft, Motwani, Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, 2007)
               (copre le sezioni 01.02, 02, 03 del programma).
  • Aho, Lam, Sethi, Ullman, "Compilatori: Principi, Tecniche e Strumenti", Addison-Wesley, 2009
               (Aho, Lam, Sethi, Ullman, "Compilers: Principles, Techniques, and Tools", Addison-Wesley, 2007)
               (copre le sezioni 01.01, 04, 05 e 06 del programma).
  • Nielson, Nielson, "Semantics with Applications: An Appetizer", Springer, 2007
               (copre le sezioni 07 e 08 del programma).
  • Thompson, "The Craft of Functional Programming", Addison-Wesley, 1999.
  • Hutton, "Programming in Haskell", Cambridge University Press, 2007.
               (coprono le sezioni 09 e 10 del programma).
  • Propedeuticitą:

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

    Modalitą didattiche:

    Lezioni frontali ed esercitazioni di laboratorio (materiale didattico).

    Modalitą di accertamento:

    Prova scritta e prova orale (prove d'esame).

    Commissione d'esame:

    Dott. Alessandro Aldini e Prof. Marco Bernardo (supplente: Prof. Alessandro Bogliolo).

    Note:

    La prova scritta viene valutata in trentesimi ed è ritenuta sufficiente se il relativo voto, che rimane valido per tutti gli appelli dell'a.a. in cui la prova viene sostenuta, è di almeno 16/30. La prova scritta include una verifica al computer di programmazione funzionale in Haskell.
    La prova orale può essere sostenuta solo previo superamento della prova scritta. Se sufficiente, il relativo esito comporta un aggiustamento per eccesso o per difetto di al più 5/30 del voto della prova scritta, determinando così il voto finale.

    Ultima modifica: 24/02/2011 Approvato da: Presidente CCdL