Anno accademico 2021-2022

LINGUAGGI E COMPILATORI

Docenti

Marco Comini
Marina Lenisa
Totale crediti
9
Periodo didattico
Secondo Periodo
Tipologia
Caratterizzante
Prerequisiti. Un corso sui linguaggi di programmazione. Conoscenza di base di un linguaggio funzionale moderno.
Metodi didattici. Lezioni frontali ed esercitazioni.
Modalità di verifica. L’esame consiste di vari micro-progetti da svolgere singolarmente e a gruppi, con esercizi da implementare al computer, usando i vari strumenti introdotti nel corso. Infine prevede lo sviluppo di un front-end di un compilatore da un linguaggio imperativo opportunamente semplificato a three-address code.

Seguirà una prova orale individuale in cui discutere i progetti e gli argomenti trattati a lezione.

Obiettivi formativi
Obiettivi formativi specifici

Questo corso intende fornire una conoscenza delle caratteristiche dei vari paradigmi di programmazione, concentrandosi sui principi “universali” che guidano la progettazione, realizzazione e implementazione dei linguaggi, ponendo particolare enfasi nello studio delle relazioni tra tecniche di progetto, semantica ed implementazione dei linguaggi.

Questo corso complementa i corsi base sui linguaggi di programmazione delle lauree triennali in informatica relativi ai paradigmi imperativo e funzionale analizzando i principi operazionali che stanno alla base dei due paradigmi e come questi principi guidino nella implementazione delle relative macchine astratte. In particolare vengono affrontate le principali problematiche, soluzioni e tecniche concernenti il front-end di un compilatore: si presentano gli algoritmi per l’analisi lessicale e sintattica che sono alla base di tool come Lex e Bison (per il linguaggio C) o Alex e Happy (per il linguaggio Haskell). Inoltre si presentano i principali metodi per l’analisi di semantica statica dei programmi, mediante grammatiche di attributi e sistemi di tipi. Infine viene illustrata la generazione del codice intermedio (senza ottimizzazioni).

Il corso ha come scopo ultimo quello di sviluppare uno spirito critico che permetta di arrivare ad una programmazione consapevole in cui saper scegliere il paradigma più adatto a seconda del problema applicativo da risolvere, sapendo quali costrutti di un linguaggio usare, e a quale costo (in termini di risorse impiegate in tutta la pipeline di implementazione).

1.1 Conoscenza e capacità di comprensione

Lo studente conosce i principali concetti della programmazione nei principali paradigmi. Conosce inoltre i principi operazionali che stanno alla base delle implementazioni dei linguaggi. Conosce infine le principali problematiche, soluzioni e tecniche concernenti il front-end di un compilatore.

1.2 Conoscenza e capacità di comprensione applicate

Lo studente impara nuovi linguaggi di programmazione dichiarativi e impara a scrivere codice nei vari paradigmi usando lo stile e le tecniche appropriate. Inoltre impara a conoscere ed usare degli strumenti che tipicamente vengono usati per scrivere un compilatore ma hanno ricadute applicative in moltissimi altri ambiti informatici.

L’attività di progetto permette allo studente di consolidare le conoscenze teoriche presentate attraverso il loro utilizzo in casi reali, promettendogli quindi di sviluppare autonomamente un front-end di un semplice linguaggio imperativo.

2.1 Autonomia di giudizio

Obiettivo del corso è principalmente quello di sviluppare uno spirito critico che permetta di saper scegliere il linguaggio di programmazione più adatto a seconda del problema applicativo da risolvere, sapendo quali costrutti di un linguaggio usare, e a quale costo. Inoltre si intende migliorare la capacità dello studente di identificare le soluzioni più pratiche e semplici nell’implementazione di sistemi software.

2.2 Abilità comunicative

Lo studente impara l’esatto significato dei termini usati nella programmazione e nella implementazione dei linguaggi.

Attraverso l’attività di progetto di gruppo lo studente migliora le proprie capacità comunicative e di interazione.

2.3 Capacità di apprendere

Le conoscenze apprese permettono allo studente muoversi con una certa disinvoltura tra la miriade di linguaggi di programmazione riuscendo a inquadrare velocemente le caratteristiche di nuovo linguaggio, e a impararlo in breve tempo.

Grazie all’interazione con i compagni del gruppo di progetto lo studente impara a valutare il proprio grado di apprendimento mediante il confronto con gli altri.

https://www.uniud.it/it/didattica/info-didattiche/regolamento-didattico-del-corso/LM-informatica/all-B2

Contenuti
Paradigma Funzionale

* Il linguaggio Haskell

* utilizzo della programmazione di ordine superiore per scrivere codice compatto e flessibile

* Modelli di esecuzione dei linguaggi funzionali: Sistemi di riscrittura e Pattern Matching

Teoria base dei compilatori

* Parsing top-down con error recovery

* Parsing bottom-up (SLR,LR,LALR) con error recovery

* Syntax Directed Translation

* Grammatiche Attributate

* SDD S-attributed e L-attributed

* Semantica statica/type checking via Grammatiche Attributate

* Generazione di Codice Intermedio (three address code)

– Traduzione espressioni con accessi in array

– Traduzione Control flow: eager/lazy conditionals

– Control flow non ottimizzato. Tecnica fall-through. Back Patching. Gestione break/continue.

– traduzione di dichiarazioni e chiamate di Procedure/Funzioni

* Cenni alla generazione di codice intermedio di linguaggi funzionali

Testi di riferimento
* Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques, and Tools. Pearson, 2007

* M. Gabbrielli e S. Martini. Linguaggi di Programmazione – Principi e Paradigmi. McGraw-Hill. ISBN 88-386-6261-4

* F. W. Schröer The GENTLE Compiler Construction System. R. Oldenbourg Verlag, 1997, ISBN 3-486-24703-4

* P. Hudak, J. Peterson, J. Fasel. A Gentle Introduction to Haskell 98. 1999

* B. O’Sullivan, D. Stewart, J. Goerzen. Real World Haskell. O’Reilly Media, 2008.

* Terese. TERESE LITE. Vrije Universiteit, 2006. (estratto dal libro Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003)