Linguaggi e Traduttori
Anno Accademico 2017/2018
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
- Corso anno accademico 2018/2019
A partire dall'anno accademico 2018/2019 il corso di Linguaggi e
Traduttori sarà tenuto dal dott. Massimo Santini.
Le informazioni vengono pubblicate sulla nuovo sito web del corso.
- 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.
Argomenti delle lezioni
- 27 febbraio 2018 - Lezione 1
Presentazione del corso.
- 1º marzo 2018 - 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.
- 8 marzo 2018 - Lezione 3
Il ruolo del linker e la soluzione dell'ambiente Java.
Requisiti di un compilatore e organizzazione in fasi di lavoro.
Descrizione generale della fase di analisi lessicale.
Il ruolo della symbol table.
- 13 marzo 2018 - Lezione 4
Descrizione generale delle fasi di analisi sintattica, semantica,
generazione di codice intermedio, ottimizzazione, generazione di
codice. Gestione degli errori.
Passate di un compilatore.
Alcuni esempi con linguaggi di programmazione reali.
- 15 marzo 2018 - 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.
- 20 marzo 2018 - Lezione 6
Richiami su automi deterministici, nondeterministici, con epsilon-mosse ed
equivalenze tra vari tipi di automi
finiti; espressioni regolari;
teorema di Kleene. Costruzione di automi corrispondenti
alle operazioni di unione, prodotto, chiusura, intersezione
e complemento.
- 22 marzo 2018 - Lezione 7
Cenni all'implementazione di automi finiti mediante programmi.
La fase di analisi lessicale: introduzione. Analizzatore lessicale
e analizzatore sintattico come produttore e consumatore.
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.
Struttura del file di specifica lessicale.
- 27 marzo 2018 - Lezione 8
Il generatore di analizzatori lessicali JFLex.
Il file di specifica lessicale.
Comportamento dell'analizzatore lessicale generato:
longest match and rule priority.
Struttura dell'analizzatore lessicale generato da JFLex.
JFlex: alcune opzioni.
Un semplice esempio di
riconoscitore di elementi lessicali all'interno di un testo
costruito utilizzando JFlex.
- 5 aprile 2018 - Lezione 9
JFlex: uso degli stati.
Un riconoscitore di numeri
romani e convertitore da numeri romani a numeri decimali.
- 10 aprile 2018 - 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.
- 17 aprile 2018 - Lezione 11
Alberi di derivazione, derivazioni leftmost e rightmost. Ambiguità.
Cenni all'amiguità inerente.
Come trasformare una grammatica context-free in un automa a pila equivalente.
Eliminazione dell'ambiguità
dalla grammatica per le espressioni aritmetiche.
- 19 aprile 2018 - Lezione 12
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
Cenni alle forme normali di Greibach e di Chomsky.
Riconoscimento e parsing di linguaggi context-free: algoritmi
principali.
L'algoritmo di Earley
per il riconoscimento e parsing di linguaggi context-free.
- 24 aprile 2018 - Lezione 13
L'algoritmo di Earley: esempio, complessità in tempo.
Introduzione al parsing top-down.
- 26 aprile 2018 - Lezione 14
Parser predittivi: implementazione mediante tabelle.
Grammatiche e linguaggi LL(k).
L'insieme FIRST.
L'insieme FOLLOW.
Ricorsione a sinistra e sua eliminazione.
- 3 maggio 2018 - Lezione 15
Esempio: grammatica LL(1) per le espressioni aritmetiche.
Left-factoring.
Esempio: istruzione if-then-else.
Parser a discesa ricorsiva: introduzione.
Carte sintattiche
- 8 maggio 2018 - Lezione 16
Implementazione di parser a discesa ricorsiva:
riconoscimento di
espressioni aritmetiche,
una calcolatrice
per le espressioni aritmetiche.
- 10 maggio 2018 - Lezione 17
Parsing bottom-up: introduzione.
Le operazioni shift e reduce.
Automa di Knuth e parser LR.
Grammatiche LR(k).
Conflitti e possibili strategie di soluzione.
- 17 maggio 2018 - Lezione 18
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.
- 22 maggio 2018 - Lezione 19
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.
- 24 maggio 2018 - Lezione 20
Un esempio di macchina a
stack.
Esempi di traduzione di espressioni.
Schemi di traduzione per assegnamenti.
- 29 maggio 2018 - Lezione 21
Schemi di traduzione per accesso ad array.
Schemi di traduzione per cicli while. Gestione dei salti in avanti.
Un compilatore
per le espressioni aritmetiche con gli identificatori.
- 31 maggio 2018 - Lezione 22
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