The course is taught in English.
Insegnamento obbligatorio per l'Orientamento Software della Laurea Magistrale in Ingegneria Informatica, collocato al II periodo didattico del I anno.
Il corso ha lo scopo di introdurre gli elementi di base della teoria dei linguaggi formali e di analizzare la loro principale applicazione nel campo dell'Informatica: la progettazione di traduttori per i linguaggi di programmazione (compilatori).

- Conoscenza delle proprietà delle diverse classi di linguaggi formali (linguaggi a struttura di frase, sensibili al contesto, indipendenti dal contesto, regolari)
- Conoscenza delle proprietà dei diversi formalismi (grammatiche e automi) usati per rappresentare i linguaggi
- Capacità di costruire la rappresentazione di un determinato linguaggio mediante grammatiche e automi
- Conoscenza delle varie fasi in cui si articola il processo di traduzione di un linguaggio di programmazione: analisi lessicale, analisi sintattica, analisi semantica, generazione del codice intermedio, generazione e ottimizzazione del codice oggetto
- Conoscenza delle tecniche e degli strumenti di progettazione disponibili per la realizzazione di analizzatori lessicali e sintattici e di traduttori guidati dalla sintassi
- Capacità di progettare e implementare traduttori guidati dalla sintassi per linguaggi di programmazione, anche mediante l'impiego di generatori di analizzatori lessicali e sintattici

Al fine di seguire in modo efficace l'insegnamento lo studente deve possedere le seguenti conoscenze:
- Conoscenza dei concetti base della teoria degli insiemi: operazioni, costruzioni e relazioni insiemistiche
- Conoscenza dell'architettura dei sistemi di elaborazione: struttura del processore e organizzazione della memoria
- Conoscenza delle proprietà dei linguaggi di programmazione e delle tecniche di programmazione
- Conoscenza delle strutture dati (tabelle hash, alberi, grafi) e degli algoritmi fondamentali
- Capacità di sviluppare programmi in linguaggio Java

Linguaggi Formali (1.5 crediti):
- Classificazione
- Linguaggi regolari (Grammatiche regolari, Espressioni regolari, Automi a stati finiti)
- Linguaggi context-free (Grammatiche context-free, Automi pushdown, Grammatiche LR(k), Grammatiche LL(k))
- Macchine di Turing

Compilatori (2.5 crediti):
- Struttura dei compilatori
- Analisi lessicale
- Analisi sintattica (Analisi bottom-up, Analisi top-down)
- Traduzione guidata da sintassi (Definizioni ad attributi, Traduttori bottom-up)
- Analisi semantica e generazione del codice intermedio (Controllo dei tipi, Linguaggi intermedi, Analisi di dichiarazioni ed istruzioni)

Esercitazioni in aula (1 credito):
- Generazione di analizzatori lessicali mediante JFlex
- Generazione di traduttori guidati da sintassi mediante Cup

Esercitazioni in laboratorio (1 credito):
- Realizzazione di componenti base di un compilatore mediante l'impiego di JFlex e Cup

Testi:
- J.E. Hopcroft, R. Motwani, J.D. Ullman - Introduction to Automata Theory, Languages, and Computation 3rd Edition, Pearson - Addison-Wesley, 2007
- A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman - Compilers:Principles, Techniques, and Tools, 2ndEdition, Pearson - Addison-Wesley, 2007

Materiale didattico a disposizione sul portale della didattica
Trasparenze proiettate in aula
Videoregistrazioni di lezioni ed esercitazioni

L'esame è costituito da due prove scritte, che possono essere sostenute anche in appelli diversi.
La prima prova, della durata di 40 minuti, consiste in esercizi e/o domande sugli argomenti svolti a lezione.
Durante lo svolgimento della prova non è possibile consultare testi o appunti.
La seconda prova, della durata di 80 minuti, verte sugli argomenti sviluppati in esercitazioni e laboratori e consiste nello sviluppo di un traduttore mediante JFlex e Cup.
Durante lo svolgimento della prova è consentito consultare testi o appunti.
A seguito della seconda prova, gli studenti sono tenuti a produrre una relazione contenente la versione completa e funzionante del programma, e ad inviarla per posta elettronica al docente entro 3 giorni lavorativi.
Il voto finale è la media aritmetica dei punteggi relativi alle due prove.