en
Politecnico di Torino
Anno Accademico 2011/12
02JEUOV
Formal languages and compilers
Corso di Laurea Magistrale in Ingegneria Informatica (Computer Engineering) - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Rivoira Silvano ORARIO RICEVIMENTO     40 10 10 0 12
SSD CFU Attivita' formative Ambiti disciplinari
ING-INF/05 6 B - Caratterizzanti Ingegneria informatica
Esclusioni:
02BMW; 01NVY; 02LVN; 02BHI; 01NRE
Presentazione
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).
Risultati di apprendimento attesi
- 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
Prerequisiti / Conoscenze pregresse
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
Programma
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)
Organizzazione dell'insegnamento
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 richiesti o raccomandati: letture, dispense, altro materiale didattico
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
Criteri, regole e procedure per l'esame
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.
Orario delle lezioni
Statistiche superamento esami

Programma definitivo per l'A.A.2011/12
Indietro