Linguaggi e Traduttori
Anno Accademico 2015/2016
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, con
il seguente orario:
mercoledì 15.30-17.30, giovedì 11.30-13.30, via Comelico 39,
aula 5.
Argomenti delle lezioni
- 2 marzo 2016 - Lezione 1
Presentazione del corso. Generalità sulla nascita e l'evoluzione
dei compilatori e sui legami
con le grammatiche introdotte da Chomsky.
- 3 marzo 2016 - 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.
- 9 marzo 2016 - 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.
- 10 marzo 2016 - 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.
- 23 marzo 2016 - 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 e cenni
ai corrispondenti dispositivi riconoscitori.
- 6 aprile 2016 - 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.
- 7 aprile 2016 - 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.
- 20 aprile 2016 - 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.
- 21 aprile 2016 - Lezione 9
JFlex: esempi d'uso di alcune opzioni,
JFlex: uso degli stati.
Un riconoscitore di numeri
romani e convertitore da numeri romani a numeri decimali.
- 27 aprile 2016 - Lezione 10
Richiami sugli automi a pila: definizione, accettazione per stati
finali e per pila vuota.
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.
- 28 aprile 2016 - 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: algoritmi
principali.
- 4 maggio 2016 - Lezione 12
L'algoritmo di Earley
per il riconoscimento e parsing di linguaggi context-free.
- 5 maggio 2016 - Lezione 13
Introduzione al parsing top-down.
Parser predittivi: implementazione mediante tabelle.
Gli insiemi FIRST e FOLLOW.
Grammatiche e linguaggi LL(k).
- 12 maggio 2016 - Lezione 14
Ricorsione a sinistra e sua eliminazione.
Esempio: grammatica LL(1) per le espressioni aritmetiche.
Left-factoring.
Esempio: istruzione if-then-else.
- 18 maggio 2016 - Lezione 15
Implementazione di parser a discesa ricorsiva:
riconoscimento di
espressioni aritmetiche,
una calcolatrice.
- 19 maggio 2016 - Lezione 16
Parsing bottom-up: introduzione.
Le operazioni shift e reduce.
Automa di Knuth e parser LR.
Grammatiche LR(k).
Conflitti e possibili strategie di soluzione.
- 25 maggio 2016 - 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.
- 26 maggio 2016 - 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.
- 1 giugno 2016 - 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.
- 8 giugno 2016 - Lezione 20
Un compilatore
per le espressioni aritmetiche con gli identificatori.
- 9 giugno 2016 - 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:
- S. Crespi Reghizzi, L. Breveglieri, A. Morzenti
Linguaggi formali e compilazione
Società editrice Esculapio, 2015
oppure edizione inglese:
Formal Languages and Compilation
Springer 2013
- A. Aho, M. Lam, R. Sethi, J. Ullman
Compilers
Addison Wesley, 2007
oppure edizione italiana:
Compilatori
Addison Wesley, 2009
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