Linguaggi e traduttori
Anno Accademico 2013/2014
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
della Laurea Magistrale in Informatica (F94 - nuovo ordinamento).
Gli studenti della laurea triennale in Informatica (F1X) e degli altri
corsi di laurea possono inserire il corso nel proprio piano di studi
tra i crediti a scelta libera dello studente.
-
Il corso si tiene nel secondo semestre, il lunedì dalle 11.30 alle
13.30 e il martedì dalle
14.30 alle 16.30, presso l'aula 6 di via Comelico.
- Per ulteriori informazioni, consultate il
sito del Collegio
Didattico Dipartimentale di Informatica.
- Il programma dettagliato di quanto svolto a lezione
verrà aggiornato su questa pagina durante lo svolgimento
del corso. È disponibile anche il
programma svolto nell'anno accademico
2008/09 per il corso Linguaggi e Traduttori 2 dell'ordinamento
precedente.
- Informazioni per gli studenti dei vecchi
ordinamenti.
Argomenti delle lezioni
- 3 marzo 2014 - Lezione 1
Presentazione del corso. Generalità sulla nascita e l'evoluzione
dei compilatori e sui legami
con le grammatiche introdotte da Chomsky.
- 4 marzo 2014 - 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.
- 10 marzo 2014 - 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.
- 11 marzo 2014 - Lezione 4
Descrizione generale delle fasi di analisi sintattica, semantica,
generazione di codice intermedio, ottimizzazione, generazione di
codice. Gestione degli errori.
Alcuni esempi con linguaggi di programmazione reali.
- 18 marzo 2014 - 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.
Semidecidibilà dei linguaggi di tipo 0.
Decidibilità dei linguaggi dipendenti dal contesto.
- 24 marzo 2014 - Lezione 6
Alberi di derivazione per grammatiche libere dal contesto.
Richiami su automi deterministici e nondeterministici e
sulla loro equivalenza.
Eliminazione del nondeterminismo dagli automi: un esempio
vicino al caso peggiore.
Distinguibilità di stringhe. Esempi.
- 25 marzo 2014 - Lezione 7
Equivalenza e distinguibilità
tra gli stati degli automi deterministici.
Cenni alla minimizzazione degli automi deterministici.
Automi con epsilon-mosse.
Equivalenza tra automi a stati finiti e grammatiche di tipo 3.
Espressioni regolari.
- 31 marzo 2014 - Lezione 8
Costruzione di automi a stati finiti a
partire da espressioni regolari.
Costruzione di espressioni regolari a partire da automi a stati.
Costruzione dell'automa prodotto per l'unione e l'intersezione
di linguaggi. Complemento di linguaggi regolari.
Considerazioni sul numero di stati degli automi ottenuti nelle
varie costruzioni.
Pumping lemma per i linguaggi regolari.
- 1º aprile 2014 - Lezione 9
Cenni alle macchine di Mealy e di Moore.
Automi two-way: esempi di riconoscimento.
Implementazione di automi a stati finiti mediante
programmi.
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.
- 7 aprile 2014 - Lezione 10
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 (inizio).
- 8 aprile 2014 - Lezione 11
Esempio d'uso di riconoscitore di JFLex (conclusione).
JFlex: alcune opzioni.
Un riconoscitore di numeri
romani e convertitore da numeri romani a numeri decimali.
- 14 aprile 2014 - Lezione 12
La notazione postfissa.
Una calcolatrice in
notazione postfissa:
versione base.
Esempio di definizione di una semplice symbol table e di descrittori
per l'introduzione degli identificatori.
- 15 aprile 2014 - Lezione 13
La calcolatrice in notazione postfissa: introduzione degli
identificatori.
- 28 aprile 2014 - Lezione 14
Richiami sugli automi a pila: definizione, accettazione per stati
finali e per pila vuota, determinismo e nondeterminismo.
Esempi di linguaggi accettati da automa a pila deterministici
e nondeterministici.
Esempi di linguaggi per cui è necessario il nondeterminismo.
Equivalenza tra grammatiche context-free e automi a pila:
come trasformare una grammatica context-free in un automa a pila equivalente.
- 5 maggio 2014 - Lezione 15
Alberi di derivazione, derivazioni leftmost e rightmost.
Ambiguità. Ambiguità inerente.
Eliminazione dell'ambiguità
dalla grammatica per le espressioni aritmetiche.
Cenni alle forme normali di Chomsky e Greibach.
Pumping lemma per i linguaggi context-free.
Chiusura della classe dei linguaggi context-free rispetto a
unione, prodotto chiusura di Kleene, intersezione con linguaggi
regolari; non chiusura rispetto a intersezione e complemento.
Cenni alla chiusura rispetto al complemento della classe dei
linguaggi context-free deterministici.
- 6 maggio 2014 - Lezione 16
Proprietà decidibili e indecidibili per i linguaggi context-free.
Riconoscimento e parsing di linguaggi context-free.
L'algoritmo CYK. L'algoritmo di
Earley.
- 12 maggio 2014 - Lezione 17
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
Introduzione al parsing top-down.
Parser predittivi.
Ricorsione a sinistra e sua eliminazione.
- 13 maggio 2014 - Lezione 18
Gli insiemi FIRST e FOLLOW.
Parser predittivi: implementazione mediante tabelle.
Grammatiche LL(1).
Parser ricorsivi-discendenti.
Esempio: riconoscimento di
espressioni aritmetiche.
Espressioni: dal riconoscitore alla calcolatrice.
- 19 maggio 2014 - Lezione 19
Alberi di sintassi astratta (AST) e loro implementazione in Java.
Rappresentazione di espressioni aritmetiche mediante AST.
Costruzione di AST per le espressioni aritmetiche.
Esempio: la calcolatrice
realizzata utilizzanto gli AST.
La calcolatrice estesa
con gli identificatori.
- 3 giugno 2014 - Lezione 20
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.
- 9 giugno 2014 - Lezione 21
Un compilatore
per le espressioni aritmetiche con gli identificatori.
Organizzazione della memoria in esecuzione.
Schemi di traduzione per chiamate e rientro da sottoprogrammi.
Introduzione al parsing bottom-up e ai parser LR.
Le operazioni shift e reduce, conflitti e loro soluzione.
Grammatiche LR(k).
- 10 giugno 2014 - Lezione 22
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
mediante il parser generato da CUP.
Ulteriori esempi con CUP
(costruzione di AST
per la calcolatrice, aggiunta
degli identificatori, compilatore per espressioni).
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
- J. Hopcroft, R. Motwani, J. Ullman
Introduction to Automata Theory, Languages and Computation
Addison Wesley, 2a ed. 2001, 3a ed. 2007, o 1a ed. 1979 (autori Hopcroft e Ullman)
oppure edizione italiana:
Automi, linguaggi e calcolabilità
Addison Wesley, 2003 o nuova edizione 2009
Altri riferimenti bibliografici:
- M. Harrison
Introduction to Formal Language Theory
Addison Wesley, 1978
- J. Shallit
A Second Course in Formal Languages and Automata Theory
Cambridge University Press, 2009
- 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
Ultimo aggiornamento: 10 giugno 2014
© Giovanni
Pighizzini
Università degli Studi di
Milano