INFORMAZIONI SU

Linguaggi e compilatori

Programma dell'insegnamento di Linguaggi e compilatori - Corso di laurea magistrale in Informatica (2013/14)

Docente

Prof. Marco Comini

Crediti

9 CFU

Finalità

Questo corso, in congiunzione con il corso di Linguaggi di Programmazione, intende fornire una conoscenza delle caratteristiche dei vari paradigmi di programmazione, concentrandosi sui principi “universali” che guidano la progettazione, realizzazione e implementazione dei moderni linguaggi di programmazione.
A questa visione generale si giunge attraverso la descrizione dei principali paradigmi di programmazione: imperativo, funzionale, logico e logico-funzionale. Questi paradigmi, oltre a essere esaminati nei loro aspetti pragmatici più immediati, sono analizzati e confrontati sulla base dei principi generali, in modo tale da permettere una comprensione critica della maggior parte dei linguaggi di uso comune. In questo modo si intende 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).
Questo corso, in particolare, complementa il corso di Linguaggi di Programmazione, relativo ai paradigmi imperativo e funzionale, mostrando i paradigmi logico e logico-funzionale. Si completa quindi la presentazione dei paradigmi dichiarativi che, grazie alla loro espressività, si prestano naturalmente quale base di sviluppo di software corretto. Si mostrerà come caratteristiche quali ordine superiore e non-determinismo possano essere sfruttate per scrivere codice compatto, elegante e flessibile (direttamente riutilizzabile in diversi contesti, agevolmente manutenibile e facilmente estensibile).
Inoltre in questo corso vengono introdotte approfonditamente le principali problematiche, soluzioni e tecniche concernenti il front-end di un compilatore. Innanzitutto, si presentano gli algoritmi per l’analisi lessicale e sintattica, fondamenti concettuali della realizzazione dei più diffusi strumenti come flex/alex e bison/happy. Successivamente, si presentano i principali metodi per l'analisi statica dei programmi, mediante grammatiche con attributi e sistemi di tipi. Infine viene introdotta la generazione del codice intermedio.

Programma

Paradigma Logico
• Non-deterministic Programming.
• Il linguaggio Prolog.
• Warren Abstract Machine.
Paradigma Logico-Funzionale
• High-order Non-deterministic Programming.
• Il linguaggio Curry.
Modelli di esecuzione dei linguaggi dichiarativi
• Paradigma funzionale: Sistemi di riscrittura e Pattern Matching
• Paradigma logico: Unificazione, SLD-derivations, semantica denotazionale della Programmazione Logica.
• Paradigma Logico Funzionale: full narrowing e needed narrowing.
Teoria dei compilatori
• Parsing top-down (implementazione a programma e parser LL).
• Parsing bottom-up (parser SLR, LR, LALR).
• Syntax Directed Translation.
• Grammatiche ad Attributi.
• S-attributed e L-attributed SDD.
• Semantica Statica.
• Type Checking via Grammatiche ad Attributi.
• 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; backpatching; gestione break/continue.
• Traduzione di dichiarazioni e chiamate di procedure/funzioni.
• Continuation Passing-Style con linguaggi funzionali.
• Cenni alla generazione di codice intermedio di linguaggi funzionali.

Bibliografia

• M. Gabbrielli e S. Martini. Linguaggi di Programmazione - Principi e Paradigmi. McGraw-Hill. ISBN 88-386-6261-4
Paradigma imperativo
• D. W. Barron (Ed). PASCAL: The Language and Its Implementation. John Wiley & Sons Ltd, 1981
• F. W. Schröer The GENTLE Compiler Construction System. R. Oldenbourg Verlag, 1997, ISBN 3-486-24703-4
• L. Cardelli. Type Systems. Handbook of Computer Science and Engineering. CRC Press, 1997.
Paradigma funzionale
• 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.
• B. Wadler. Introduction to Functional Programming using Haskell. ISBN: 0134843460, Prentice Hall PTR, 1998
• Terese. TERESE LITE. Vrije Universiteit, 2006. (estratto dal libro Term Rewriting Systems. Cambridge Tracts in Theoretical Computer Science, Vol. 55, Cambridge University Press, 2003)
Paradigma Logico
• L. Sterling, E. Shapiro. The art of Prolog, MIT Press, 1986.
• K. R. Apt, From Logic Programming to Prolog, International Series in Computer Science, Prentice Hall, 1997.
• Hassan Aït-Kaci. Warren's Abstract Machine: A Tutorial Reconstruction, MIT Press, 1991, ISBN 0-262-01123-9. FUORI STAMPA
Paradigma Logico-Funzionale
• M. Hanus, S. Antoy. Curry: A Tutorial Introduction, 2004
• M. Hanus. The Integration of Functions into Logic Programming: From Theory to Practice, Journal of Logic Programming, 19&20:583-628, 1994.
• S. Antoy, R. Echahed, M. Hanus. A Needed Narrowing Strategy, Journal of the ACM, 2000.

Modalità d'esame

Progetto a gruppi, orale individuale