Linguaggi e Traduttori
Anno Accademico 2016/2017
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 28 febbraio, con
il seguente orario:
martedì 8.30-10.30, giovedì 11.30-13.30, via Comelico 39,
aula 5.
Argomenti delle lezioni
- 28 febbraio 2017 - Lezione 1
Presentazione del corso.
- 7 marzo 2017 - 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.
Il ruolo del linker e la soluzione dell'ambiente Java.
- 23 marzo 2017 - Lezione 3
Requisiti di un compilatore e organizzazione in fasi di lavoro.
Descrizione generale dela fasi di analisi lessicale.
Il ruolo della symbol table.
- 28 marzo 2017 - 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.
- 30 marzo 2017 - 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.
Richiami su automi deterministicie nondeterministici.
- 4 aprile 2017 - Lezione 6
Richiami su 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.
Cenni all'implementazione di automi finiti mediante programmi.
La fase di analisi lessicale: introduzione. Analizzatore lessicale
e analizzatore sintattico come produttore e consumatore.
- 6 aprile 2017 - Lezione 7
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.
Il file di specifica lessicale.
Comportamento dell'analizzatore lessicale generato:
longest match and rule priority.
- 11 aprile 2017 - Lezione 8
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.
JFlex: esempi d'uso di alcune opzioni,
JFlex: uso degli stati.
Un riconoscitore di numeri
romani e convertitore da numeri romani a numeri decimali.
- 20 aprile 2017 - Lezione 9
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à.
- 27 aprile 2017 - Lezione 10
Eliminazione dell'ambiguità
dalla grammatica per le espressioni aritmetiche.
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
Cenni all'amiguità inerente.
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
- 2 maggio 2017 - Lezione 11
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.
- 4 maggio 2017 - Lezione 12
Introduzione al parsing top-down.
Parser predittivi: implementazione mediante tabelle.
Grammatiche e linguaggi LL(k).
L'insieme FIRST.
- 9 maggio 2017 - Lezione 13
L'insieme FOLLOW.
Ricorsione a sinistra e sua eliminazione.
Esempio: grammatica LL(1) per le espressioni aritmetiche.
Left-factoring.
Esempio: istruzione if-then-else.
- 11 maggio 2017 - Lezione 14
Implementazione di parser a discesa ricorsiva:
riconoscimento di
espressioni aritmetiche.
- 16 maggio 2017 - Lezione 15
Implementazione di parser a discesa ricorsiva:
una calcolatrice
per le espressioni aritmetiche.
Parsing bottom-up: introduzione.
Le operazioni shift e reduce.
Automa di Knuth e parser LR.
- 18 maggio 2017 - Lezione 16
Grammatiche LR(k).
Conflitti e possibili strategie di soluzione.
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.
- 25 maggio 2017 - Lezione 17
Cenni alle grammatiche con attributi: attributi sintetizzati e
attributi ereditati.
Utilizzo degli attributi in CUP.
Esempio: implementazione di una
calcolatrice.
Esempio: implementazione di un
convertitore da notazione infissa a
notazione postfissa.
Un interprete per le espressioni con gli identificatori: introduzione.
- 30 maggio 2017 - 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 2017 - 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 (inizio).
- 6 giugno 2017 - Lezione 20
Schemi di traduzione per cicli while (conclusione): gestione dei salti
in avanti.
Un compilatore
per le espressioni aritmetiche con gli identificatori.
- 8 giugno 2017 - 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