B018807 - LINGUAGGI E CODICI

Italiano

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

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.

Corsi raccomandati:
Programmazione
Algoritmi e Strutture Dati

Orario di ricevimento:
Su appuntamento
Recapito:
Viale Morgagni, 65 - 50134 Firenze
Tel: 055 2751482 / 329 2985755
E-mail: elena.barcucci@unifi.it
Web: e-l.unifi.it

Prova scritta e orale

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.