Linguaggi e traduttori
Anno Accademico 2011/2012
In questa pagina potete trovare
Avvisi e informazioni generali
Argomenti delle lezioni
Bibliografia di riferimento
Materiale didattico
Pagine anno precedente
Avvisi e informazioni generali
Argomenti delle lezioni
- 27 febbraio 2012 - Lezione 1
Presentazione del corso. Generalità sulla nascita e l'evoluzione dei compilatori e sui legami
con le grammatiche introdotte da Chomsky.
- 28 febbraio 2012 - Lezione 2
Richiami su alcune nozioni fondamentali: alfabeto, stringa, linguaggio.
Come rappresentare i linguaggi: esempi di rappresentazioni finite
di linguaggi infiniti.
Grammatiche e derivazioni.
Esempi di grammatiche.
Classificazione di Chomsky delle grammatiche e dei linguaggi.
- 12 marzo 2012 - Lezione 3
Ricorsività dei linguaggi dipendenti dal contesto.
Automi deterministici.
Esempi.
- 13 marzo 2012 - Lezione 4
Automi nondeterministici ed equivalenza con automi deterministici.
Eliminazione del nondeterminismo dagli automi: un esempio
vicino al caso peggiore.
Distinguibilità di stringhe.
Equivalenza e distinguibilità
tra gli stati degli automi deterministici.
Cenni alla minimizzazione degli automi deterministici.
Automi con epsilon-mosse.
- 19 marzo 2012 - Lezione 5
Esempi vari sugli automi a stati finiti.
La tecnica del "fooling set" per stabilire
limiti inferiori al numero di stati di automi nondeterministici.
Equivalenza tra automi a stati finiti e grammatiche di tipo 3.
- 20 marzo 2012 - Lezione 6
Equivalenza tra automi a stati finiti e grammatiche di tipo 3.
Espressioni regolari. 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.
- 26 marzo 2012 - Lezione 7
Altezza di star di un linguaggio regolare.
Cenni al problema dell'altezza di star generalizzata.
Esempi di linguaggi non regolari.
Automi two-way: esempi di riconoscimento.
Cenni alla conversione da automi two-way a one-way
e al problema di Sakoda e Sipser
- 27 marzo 2012 - Lezione 8
Cenni alle macchine di Mealy e di Moore.
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.
Implementazione di automi a stati finiti mediante
programmi.
- 2 aprile 2012 - Lezione 9
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.
- 3 aprile 2012 - Lezione 10
Generazione automatica di analizzatori lessicali:
un semplice esempio di riconoscitore di elementi lessicali
all'interno di un testo, costruito utilizzando JFlex.
JFLex: utilizzo degli stati. Esempi: riconoscitore di numeri
romani, convertitore da numeri romani a numeri decimali.
- 16 aprile 2012 - Lezione 11
La notazione postfissa. Una
calcolatrice in notazione postfissa.
Come aumentare la potenza degli automi a stati finiti:
cenni agli automi limitati linearmente e alle macchine di Turing.
- 17 aprile 2012 - Lezione 12
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.
Esempi di linguaggi non accettati da automi a pila.
Equivalenza tra grammatiche context-free e automi a pila:
come trasformare una grammatica in un automa a pila equivalente.
- 23 aprile 2012 - Lezione 13
Alberi di derivazione, derivazioni leftmost e rightmost.
Ambiguità.
Cenni alle forme normali di Chomsky e Greibach.
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.
Proprietà decidibili e indecidibili per i linguaggi context-free.
Cenni agli automi a pila two-way.
- 24 aprile 2012 - Lezione 14
Linguaggi context-free deterministici: chiusura rispetto al complemento.
Cenni alle grammatiche self-embedding e alle grammatiche lineari.
- 7 maggio 2012 - Lezione 15
Riconoscimento e parsing di linguaggi context-free.
L'algoritmo CYK. L'algoritmo di
Earley.
- 8 maggio 2012 - Lezione 16
Ambiguità. Eliminazione dell'ambiguità
nella grammatica per le espressioni aritmetiche.
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
Introduzione al parsing top-down.
- 14 maggio 2012 - Lezione 17
Ricorsione a sinistra e sua eliminazione.
Parser predittivi.
Grammatiche LL(1).
Parser ricorsivo-discendenti.
- 15 maggio 2012 - Lezione 18
Un parser ricorsivo-discendente per le espressioni aritmetiche:
implementazione di un riconoscitore.
Parser ricorsivo-discendente per le espressioni: dal riconoscitore
alla calcolatrice.
La struttura di un compilatore e l'organizzazione in fasi
di lavoro.
- 21 maggio 2012 - Lezione 19
Fasi di lavoro di un compilatore:
Analisi lessicale, sintattica e semantica, generazione di
codice. L'analisi semantica e il type checking.
Il codice intermedio.
Alberi di sintassi astratta (AST) e loro implementazione in
Java.
- 22 maggio 2012 - Lezione 20
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. Un semplice esempio di symbol table.
Un esempio di macchina a
stack.
- 28 maggio 2012 - Lezione 21
La macchina a stack.
Esempi di traduzione di espressioni. Schemi di traduzione per
assegnamenti e accesso ad array.
Schemi di traduzione per cicli while.
Schemi di traduzione per selezione.
Organizzazione della memoria in esecuzione.
Schemi di traduzione per chiamate di sottoprogrammi.
Sviluppo di un compilatore per le espressioni
aritmetiche con gli identificatori.
- 29 maggio 2012 - Lezione 22
Introduzione al parsing bottom-up.
Le operazioni shift e reduce.
Struttura di un parser LR. Grammatiche LR(k) e
cenni a loro varianti.
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.
- 4 giugno 2012 - Lezione 23
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).
Presentazione del progetto d'esame.
Bibliografia di riferimento
I testi di riferimento principali relativi agli argomenti trattati nel corso sono:
- 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
- A. Aho, M. Lam, R. Sethi, J. Ullman
Compilers
Addison Wesley, 2007
oppure edizione italiana:
Compilatori
Addison Wesley, 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
- Analizzatori lessicali
(Lezioni 10 e 11)
-
Parser ricorsivo-discendenti
(Lezioni 17, 18, 20)
-
Generazione di codice
(Lezioni 20, 21)
- Parser bottom-up
(Lezioni 22, 23)
- Anni precedenti: 2010/2011, 2009/2010, 2008/2009, 2007/2008, 2006/2007, 2005/2006,
2004/2005
Ultimo aggiornamento: 4 giugno 2012
© Giovanni
Pighizzini
Università degli Studi di
Milano