Linguaggi e Traduttori
Anno Accademico 2014/2015
Corso di Laurea in Informatica - Milano
In questa pagina potete trovare
Avvisi e informazioni generali
Argomenti delle lezioni
Bibliografia di riferimento
Materiale didattico
Pagine anno precedente
Avvisi e informazioni generali
- Il corso è previsto come complementare dal manifesto degli studi
delle Laurea Triennali in Informatica e in Informatica Musicale.
Gli studenti degli altri corsi di laurea e delle lauree magistrali possono inserire
il corso nel proprio piano di studi
tra i crediti a scelta libera dello studente.
- È necessaria la conoscenza dei contenuti del corso di
linguaggi formali e automi.
-
Il corso si tiene nel secondo semestre, a partire dal 2 di marzo.
L'orario delle lezioni è lunedì e
mercoledì, dalle 16.30 alle 18.30 in via Comelico, aule Beta
(lunedì) e Alfa (mercoledì).
Argomenti delle lezioni
- 2 marzo 2015 - Lezione 1
Presentazione del corso. Generalità sulla nascita e l'evoluzione
dei compilatori e sui legami
con le grammatiche introdotte da Chomsky.
- 4 marzo 2015 - Lezione 2
Traduttori, compilatori e strumenti correlati.
Interpreti.
Cross compiler.
Bootstrap di compilatori.
Costruzione di compilatori a partire da compilatori esistenti.
Compilatori interpretativi. Pascal e P-code. Java e Bytecode.
- 11 marzo 2015 - Lezione 3
Il ruolo del linker e la soluzione dell'ambiente Java.
Requisiti di un compilatore e organizzazione in fasi di lavoro.
Descrizione generale delle fasi di analisi lessicale e sintattica.
- 16 marzo 2015 - Lezione 4
Descrizione generale delle fasi di analisi semantica,
generazione di codice intermedio, ottimizzazione, generazione di
codice. Gestione degli errori.
Alcuni esempi con linguaggi di programmazione reali.
- 18 marzo 2015 - Lezione 5
Richiami su alcune nozioni fondamentali: alfabeto, stringa, linguaggio.
Come rappresentare i linguaggi: esempi di rappresentazioni finite
di linguaggi infiniti.
Grammatiche e derivazioni.
Alcuni esempi di grammatiche.
Classificazione di Chomsky delle grammatiche e dei linguaggi.
- 23 marzo 2015 - Lezione 6
Richiami su: automi deterministici, nondeterministici e con
epsilon-mosse e loro equivalenza; espressioni regolari;
teorema di Kleene. Costruzione di automi corrispondenti
alle operazioni di unione, prodotto, chiusura, intersezione
e complemento.
- 25 marzo 2015 - Lezione 7
La fase di analisi lessicale. Esempi di token di un
linguaggio di programmazione. La regola del longest match.
Token con attributi.
Uso degli automi a stati finiti per la costruzione di
analizzatori lessicali.
Generatori di analizzatori lessicali: introduzione
- 1 aprile 2015 - Lezione 8
Generatori di analizzatori lessicali.
Il file di specifica lessicale di JFLex.
Comportamento dell'analizzatore lessicale generato:
longest match and rule priority.
Struttura dell'analizzatore lessicale generato da JFLex.
Generazione automatica di analizzatori lessicali:
un semplice esempio di
riconoscitore di elementi lessicali all'interno di un testo,
costruito utilizzando JFlex.
- 13 aprile 2015 - Lezione 9
JFlex: uso degli stati.
Un riconoscitore di numeri
romani e convertitore da numeri romani a numeri decimali.
Richiami sugli automi a pila: definizione, accettazione per stati
finali e per pila vuota.
- 20 aprile 2015 - Lezione 10
Determinismo, nondeterminismo e ambiguità negli automi a pila.
Esempi di linguaggi accettati da automi a pila deterministici
e nondeterministici.
Esempi di linguaggi per cui è necessario il nondeterminismo.
Come trasformare una grammatica context-free in un automa a pila equivalente.
Alberi di derivazione, derivazioni leftmost e rightmost.
Ambiguità. Ambiguità inerente.
Cenni alle forme normali di Chomsky e Greibach e al
pumping lemma per i linguaggi context-free.
Chiusura della classe dei linguaggi context-free rispetto a
unione e non chiusura rispetto a intersezione e complemento.
- 22 aprile 2015 - Lezione 11
Eliminazione dell'ambiguità
dalla grammatica per le espressioni aritmetiche.
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
Riconoscimento e parsing di linguaggi context-free.
L'algoritmo CYK.
- 27 aprile 2015 - Lezione 12
L'algoritmo di Earley
per il riconoscimento e parsing di linguaggi context-free.
- 29 aprile 2015 - Lezione 13
Introduzione al parsing top-down.
Parser predittivi: implementazione mediante tabelle.
Gli insiemi FIRST e FOLLOW.
Grammatiche e linguaggi LL(k).
- 4 maggio 2015 - Lezione 14
Ricorsione a sinistra e sua eliminazione.
Left-factoring.
Parser a discesa ricorsiva.
- 6 maggio 2015 - Lezione 15
Implementazione di parser a discesa ricorsiva:
riconoscimento di
espressioni aritmetiche,
una calcolatrice.
Parsing bottom-up: introduzione.
Le operazioni shift e reduce.
- 11 maggio 2015 - Lezione 16
Automa di Knuth e parser LR.
Grammatiche LR(k).
Conflitti e possibili strategie di soluzione.
- 13 maggio 2015 - Lezione 17
Generazione automatica di parser: il generatore CUP.
Il file di specifica sintattica.
Utilizzo delle regole di precedenza e
associatività per l'eliminazione dei conflitti.
Esempio: un
riconoscitore di
espressioni.
Cenni alle grammatiche con attributi: attributi sintetizzati e
attributi ereditati.
Utilizzo degli attributi in CUP.
Esempio: implementazione di una
calcolatrice.
- 18 maggio 2015 - Lezione 18
Esempio: implementazione di un
interprete per
le espressioni con gli identificatori.
Alberi di sintassi astratta (AST) e loro implementazione in Java.
Rappresentazione di espressioni aritmetiche mediante AST.
Costruzione di AST per le espressioni aritmetiche.
Esempio: costruzione
di AST per le espressioni.
- 20 maggio 2015 - Lezione 19
Un esempio di macchina a
stack.
Esempi di traduzione di espressioni. Schemi di traduzione per
assegnamenti e accesso ad array.
Schemi di traduzione per cicli while.
- 25 maggio 2015 - Lezione 20
Un compilatore
per le espressioni aritmetiche con gli identificatori.
- 27 maggio 2015 - Lezione 21
Linguaggi con sottoprogrammi.
Organizzazione della symbol table.
Organizzazione della memoria in esecuzione.
Schemi di traduzione per chiamate e rientro da sottoprogrammi.
Presentazione del progetto d'esame.
Bibliografia di riferimento
I testi di riferimento principali relativi agli argomenti trattati nel
corso sono:
- A. Aho, M. Lam, R. Sethi, J. Ullman
Compilers
Addison Wesley, 2007
oppure edizione italiana:
Compilatori
Addison Wesley, 2009
- S. Crespi Reghizzi, L. Breveglieri, A. Morzenti
Formal Languages and Compilation
Springer 2013
Altri riferimenti bibliografici:
- A. Appel
Modern Compiler Implementation in Java
Oxford University Press, 2002
(oppure dello stesso autore ed editore: Modern Compiler
Implementation in C, 1998)
Materiale didattico