Linguaggi e traduttori
Anno Accademico 2010/2011
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
- 14 marzo 2011 - Lezione 1
Presentazione del corso. Generalità sulla nascita e l'evoluzione dei compilatori e sui legami
con le grammatiche introdotte da Chomsky.
- 15 marzo 2011 - Lezione 2
Richiami su alcune nozioni fondamentali: alfabeto, stringa, linguaggio.
Come rappresentare i linguaggi: esempi di rappresentazioni finite
di linguaggi infiniti.
Un semplice esempio di grammatica e di riconoscitore.
- 21 marzo 2011 - Lezione 3
Grammatiche e derivazioni.
Esempi di grammatiche.
Classificazione di Chomsky delle grammatiche e dei linguaggi.
- 22 marzo 2011 - Lezione 4
Ricorsività dei linguaggi dipendenti dal contesto.
Alberi di derivazione per grammatiche libere dal contesto.
Automi deterministici.
Esempi.
- 28 marzo 2011 - Lezione 5
Automi nondeterministici ed equivalenza con automi deterministici.
Eliminazione del nondeterminismo dagli automi: un esempio
vicino al caso peggiore.
Distinguibilità di stringhe.
- 29 marzo 2011 - Lezione 6
Equivalenza e distinguibilità
tra gli stati degli automi deterministici. Minimizzazione
degli automi deterministici.
Automi con epsilon-mosse.
- 4 aprile 2011 - Lezione 7
Equivalenza tra automi a stati finiti e grammatiche di tipo 3.
Espressioni regolari. Costruzione di automi a stati finiti a
partire da espressioni regolari (inizio).
- 5 aprile 2011 - Lezione 8
Costruzione di automi a stati finiti a
partire da espressioni regolari (conclusione).
Costruzione di espressioni regolari a partire da automi a stati
finiti. Complemento e reversal di linguaggi regolari.
Esempi di linguaggi non regolari.
Cenni alle macchine di Mealy e di Moore.
- 11 aprile 2011 - Lezione 9
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.
Cenni all'implementazione di automi a stati finiti mediante
programmi.
Introduzione ai generatori di analizzatori lessicali.
- 12 aprile 2011 - Lezione 10
Il file di specifica lessicale di JFLex.
Comportamento dell'analizzatore lessicale generato:
longest match and rule priority.
Breve richiamo sugli stream di byte e di caratteri
in Java, sulle eccezioni e sul loro utilizzo.
- 18 aprile 2011 - Lezione 11
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.
- 19 aprile 2011 - Lezione 12
La notazione postfissa. Una
calcolatrice in notazione postfissa.
- 2 maggio 2011 - Lezione 13
JFLex: utilizzo degli stati. Esempi: riconoscitore di numeri
romani, convertitore da numeri romani a numeri decimali.
Varianti di automi a stati finiti: cenni agli automi two-way
e alla loro equivalenza con gli automi a stati finiti.
Cenni agli automi limitati linearmente e alle macchine di Turing.
Richiami sugli automi a pila: definizione, accettazione per stati
finali e per pila vuota.
- 3 maggio 2011 - Lezione 14
Automi a pila: 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.
Complessità in tempo dei linguaggi context-free.
- 9 maggio 2011 - Lezione 15
Cenni alle forme normali di Chomsky e Greibach.
Alberi di derivazioni, derivazioni leftmost e rightmost.
Ambiguità. Eliminazione dell'ambiguità
nella grammatica per le espressioni aritmetiche.
Ambiguità nei linguaggi di programmazione:
l'istruzione if.
- 10 maggio 2011 - Lezione 16
Aspetti dei linguaggi di programmazione
non rappresentabili mediante grammatiche context-free.
Introduzione al parsing top-down.
Ricorsione a sinistra e sua eliminazione.
Parser predittivi.
Grammatiche LL(1).
- 16 maggio 2011 - Lezione 17
Parser ricorsivo-discendenti.
Un parser ricorsivo-discendente per le espressioni aritmetiche:
implementazione di un riconoscitore.
- 17 maggio 2011 - Lezione 18
Parser ricorsivo-discendente per le espressioni: dal riconoscitore
alla calcolatrice.
La struttura di un compilatore e l'organizzazione in fasi
di lavoro. Analisi lessicale, sintattica e semantica, generazione di
codice.
L'analisi semantica e il type checking.
Il codice intermedio.
- 23 maggio 2011 - Lezione 19
Java e Bytecode.
Il ruolo del linker e la soluzione dell'ambiente Java.
Alberi di sintassi astratta (AST) e loro implementazione in
Java. Rappresentazione di espressioni aritmetiche mediante AST.
Costruzione di AST per le espressioni aritmetiche.
- 24 maggio 2011 - Lezione 20
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 (inizio).
- 30 maggio 2011 - Lezione 21
Un esempio di macchina a stack
(conclusione). Esempi di traduzione di espressioni. Schemi di traduzione per
assegnamenti e accesso ad array.
Sviluppo di un compilatore per le espressioni
aritmetiche con gli identificatori.
- 31 maggio 2011 - Lezione 22
Schemi di traduzione per cicli while.
Schemi di traduzione per selezione.
Organizzazione della memoria in esecuzione.
Schemi di traduzione per chiamate di sottoprogrammi.
- 6 giugno 2011 - Lezione 23
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.
- 7 giugno 2011 - Lezione 24
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 11, 12, 13)
-
Parser ricorsivo-discendenti
(Lezioni 17, 18, 19, 20)
-
Generazione di codice
(Lezioni 20, 21, 22)
-
Parser bottom-up
(Lezioni 23 e 24)
- Anni precedenti: 2009/2010, 2008/2009, 2007/2008, 2006/2007, 2005/2006,
2004/2005
Ultimo aggiornamento: 7 giugno 2011
© Giovanni
Pighizzini
Università degli Studi di
Milano