LINGUAGGI E TRADUTTORI

Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita all’anno accademico di tuo interesse? Ecco come fare >>
English course description
Anno accademico
2017/2018
Docente
MARCO GAVANELLI
Crediti formativi
6
Periodo didattico
Secondo Semestre
SSD
ING-INF/05

Obiettivi formativi

Nel corso si affrontano i principali aspetti della teoria dei linguaggi di programmazione, della definizione formale dei linguaggi e degli aspetti teorici e computazionali necessari per effettuare la traduzione ed esecuzione di un programma scritto in un linguaggio ad alto livello su un calcolatore elettronico.
Si affronta anche l'argomento dei paradigmi di programmazione, ponendo particolare enfasi sulla programmazione funzionale e utilizzando il linguaggio Haskell come esempio.

Le principali conoscenze acquisite saranno:
- definizione e classificazione delle grammatiche
- concetto di computabilita`
- principali metodologie di sviluppo di riconoscitori, interpreti e compilatori per linguaggi regolari e indipendenti dal contesto
- programmazione funzionale, valutazione "lazy" degli argomenti di una funzione, funzioni di ordine superiore

Le principali abilità (ossia la capacità di applicare le conoscenze acquisite) saranno:
- definire formalmente una grammatica e classificarla nella gerarchia di Chomsky
- riconoscere le relazioni fra grammatiche e linguaggi generati
- progettare riconoscitori per grammatiche regolari
- progettare riconoscitori per grammatiche indipendenti dal contesto con metodologie LL(1) e LR(0)
- progettare interpreti e bozze di compilatori per una semplice grammatica
- sviluppare programmi in un linguaggio funzionale utilizzando funzioni di ordine superiore e valutazione "lazy" degli argomenti

Prerequisiti

Conoscenza di linguaggi di programmazione imperativa e ad oggetti.

Automi a stati finiti

Contenuti del corso

Fornire una descrizione ragionata sui concetti essenziali dei linguaggi di programmazione, correlandoli ai diversi modelli computazionali alla base dei diversi linguaggi e al problema del loro riconoscimento.

Contenuti di dettaglio: Descrizione formale e implementazione dei linguaggi: grammatiche formali e loro proprietà, classificazione di Chomsky. Relazione fra grammatiche e automi riconoscitori. Analisi lessicale e tecniche di analisi sintattica top-down e bottom-up per linguaggi regolari e context-free. Cenni sulla descrizione formale della semantica. Organizzazione e costruzione di interpreti e compilatori e relativi supporti a tempo di esecuzione. Strumenti semi-automatici per la generazione di analizzatori lessicali e sintattici.

Introduzione agli stili di programmazione non imperativi.

Programmazione funzionale e linguaggio Haskell. Tipi di dato e typeclasses in Haskell. Lambda expressions, Currying, funzioni di ordine superiore. Pattern-matching, list comprehensions. Valutazione eager e lazy degli argomenti. Tecniche di graph reduction per migliorare la valutazione lazy degli argomenti. Memory leaks in Haskell.

Metodi didattici

Il corso viene erogato mediante proiezione in aula di diapositive (delle quali lo studente può liberamente scaricare gli stampati prima delle lezioni). Lezioni ed esercitazioni sono intercalate, alternando l'esposizione di un concetto o costrutto linguistico con i relativi esempi. Ulteriori approfondimenti ed esercizi sono svolti in aula e in laboratorio.

Modalità di verifica dell'apprendimento

L'esame si compone di

una prova di laboratorio, in cui viene valutata la capacità dello studente di utilizzare i linguaggi di programmazione appresi durante il corso e viene verificata la conoscenza degli strumenti software utilizzati nel corso;
una prova scritta, in cui vengono svolti esercizi su grammatiche ed altri aspetti teorici del corso;
Le prove si svolgono lo stesso giorno, ad esempio una la mattina e l'altra il pomeriggio.

Il voto finale è dato dalla somma dei voti delle prove.

Nelle prove, non è ammesso utilizzare materiale cartaceo, appunti, ecc. Nella prova di laboratorio, lo studente può accedere alla documentazione associata ai vari pacchetti software utilizzati, installati nei computer del laboratorio.

Il superamento dell'esame è prova di aver acquisito le conoscenze e le abilità specificate negli obiettivi formativi dell'insegnamento.

Su richiesta, l'esame può essere sostenuto in lingua Inglese.

Testi di riferimento

MATERIALE DI RIFERIMENTO:
- lucidi proiettati a lezione e resi disponibili sul sito web del corso

TESTI PER APPROFONDIMENTI SU TEORIA DEI LINGUAGGI E COMPILAZIONE
Maurizio Gabbrielli, Simone Martini. Linguaggi di programmazione - Principi e paradigmi. McGraw-Hill, 2001.
A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman. Compilatori: principi, tecniche e strumenti seconda edizione, Pearson/Addison-Welsley, 2009.
J. E. Hopcroft, R. Motwani, J. D. Ullman. Automi, Linguaggi e calcolabilita', terza edizione, Pearson/Addison-Wesley, 2009.
S. Crespi Reghizzi, L. Breveglieri, A. Morzenti. Linguaggi formali e compilazione. Società editrice Esculapio 2015.

TESTI PER APPROFONDIMENTI SUL LINGUAGGIO HASKELL
Graham Hutton. Programming in Haskell. Cambridge University Press, 2007
Bryan O'Sullivan, Don Stewart, and John Goerzen. Real World Haskell. O'Reilly Media, 2008.
Miran Lipovača. Learn You a Haskell for Great Good!: A Beginner's Guide. 2011