Linguaggi e grammatiche; insiemi regolari; grammatiche context-free; forme normali di Chomsky e di Greibach. Automi a stati finiti e linguaggi regolari; pumping lemma per linguaggi regolari e linguaggi context-free; proprietà dei linguaggi context-free. Gerarchia di Chomsky; macchine di Turing.
Struttura di un compilatore. Analisi lessicale, analisi sintattica. Traduzione guidata dalla sintassi. Generazione del codice intermedio. Organizzazione della memoria.
- Thomas A. Sudkamp
Languages and Machines
Addison-Wesley, 1997
- John E. Hopcroft, Rajeev Sethi, Jeffrey D. Ullman
Automi, linguaggi e calcolabilità
Pearson, 2009
- Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
Compilatori: Principi, tecniche e strumenti
Pearson, 2009
Obiettivi Formativi
Conoscenze:
Proprietà dei linguaggi formali, relazioni con grammatiche e automi; struttura e funzioni dei compilatori, strumenti per le fasi di analisi e traduzione.
Competenze acquisite:
competenze nella teoria dei linguaggi formali in relazione con grammatiche, automi e fasi di analisi e traduzione nei compilatori.
Capacità acquisite (al termine del corso):
Al termine del corso gli studenti dovrebbero aver acquisito la capacità di affrontare e risolvere problemi relativi ai linguaggi, alla definizione di grammatiche, alla progettazione di automi e all’applicazione di queste tecniche nella progettazione di compilatori.
Prerequisiti
Corsi raccomandati:
Programmazione
Algoritmi e Strutture Dati
Metodi Didattici
Numero di ore per studio personale e altre attività formative di tipo individuale: 135
Numero di ore relative alle attività in aula: 72
Numero di ore relative ad attività di laboratorio: 12
Numero di ore relative a prove in itinere: 6
Altre Informazioni
Orario di ricevimento:
Lunedì e giovedì 14-15.30 oppure su appuntamento
Recapito:
Viale Morgagni, 65 - 50134 Firenze
Tel: 055 2751482 / 329 2985755
E-mail: elena.barcucci@unifi.it
Web: e-l.unifi.it
Modalità di verifica apprendimento
Prova scritta con esercizi per verificare la capacità di applicare i metodi illustrati e domande sugli aspetti teorici.
Prova orale facoltativa.
La prova scritta può essere suddivisa in due parti (in novembre e alla fine delle lezioni).
Programma del corso
Linguaggi e grammatiche: insiemi regolari; grammatiche regolari; grammatiche context-free; derivazioni e ambiguità; analisi sintattica; forme normale di Chomsky e di Greibach. Automi a stati finiti e linguaggi regolari: automi a stati finiti deterministici e non deterministici; pumping lemma per linguaggi regolari; proprietà dei linguaggi regolari. Automi a pila e linguaggi context-free: automi a pila e linguaggi contextfree; pumping lemma per linguaggi context-free; proprietà dei linguaggi context-free. Gerarchia di Chomsky: linguaggi contestuali, ricorsivi e ricorsivamente enumerabili; macchine di Turing.
Struttura di un compilatore, analisi lessicale, sintattica e semantica. Analisi top-down e bottom up. Grammatiche LL(1), LR(0) e LR(1). Traduzione guidata dalla sintassi, attributi ereditati e sintetizzati. Generazione del codice intermedio, tipi e dichiarazioni, tavola dei simboli, traduzione di espressioni. Organizzazione della memoria, heap e stack.