Principles and Implementation of Programming Languages (Laurea Magistrale LM-18)
Docente: Elena Zucca
ENGLISH VERSION
Obiettivo
Il corso si propone di insegnare a comprendere e implementare le descrizione formali di sintassi, sistemi di tipo e modelli di esecuzione dei linguaggi.
Programma
- Sintassi e riconoscimento
- Richiami da FdI: linguaggi regolari e context free, automi a stati finiti, automi push down, gerarchia di Chomsky, linguaggi context-sensitive.
- Analisi lessicale.
- Analisi sintattica (parsing), parsing top-down, grammatiche LL(k), parsing bottom-up, grammatiche LR(k)
- Sintassi astratta. Rappresentazione interna (AST).
- Uso di ANTLR per analisi lessicale, parsing e costruzione AST.
- Modelli di esecuzione
- Macchine astratte (semantica small-step), esempio espressioni naturali e booleane.
- Lambda calcolo, estensione imperativa, estensione con eccezioni.
- Featherweight Java.
- Uso di ANTLR per costruzione di interpreti/generazione di codice.
- Sistemi di tipo
- Sistema di tipo per espressioni naturali e booleane, soundness, progress e preservazione del tipo.
- Lambda calcolo tipato semplice, sistema di tipo per estensioni.
- Sistema di tipo per Featherweight Java.
- Uso di ANTLR per costruzione di type checker.
Testi e link di riferimento
- Note delle lezioni (disponibili su Aulaweb).
Per approfondimenti:Introduction to Automata Theory, Languages, and Computation di Hopcroft, Motwani, Ullman.
Compilers: principles, techniques, and tools di Aho, Lam, Sethi, Ullman. Prima edizione disponibile in biblioteca.
- The Definitive ANTLR reference: building domain-specific languages, di Parr.
Types and Programming Languages di Pierce, disponibile in biblioteca.
Modalità d'esame
L'esame consta di prova scritta, prova orale e svolgimento e presentazione di un piccolo progetto. Per sostenere l'orale occorre aver superato lo scritto (almeno 18) e svolto il progetto. Il voto dello scritto viene conservato per i due appelli successivi.
Esempi di esercizi d'esame
Fate riferimento all'archivio esami. Inoltre:
Per la seconda e terza parte del corso (modelli di esecuzione e sistemi di tipo) potete trovare degli esercizi risolti nell' archivio esami del corso disattivato di Informatica Teorica.
Ritorno alla pagina precedente
Ultima modifica: 27 novembre 2015