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 Early.
- 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.
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
Ultimo aggiornamento: 15 maggio 2012
© Giovanni
Pighizzini
Università degli Studi di
Milano
