Linguaggi e traduttori

Anno Accademico 2012/2013

Docente: Giovanni Pighizzini

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 5 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

• 4 marzo 2013 - Lezione 1
  Presentazione del corso. Generalità sulla nascita e l'evoluzione dei compilatori e sui legami con le grammatiche introdotte da Chomsky.

• 5 marzo 2013 - Lezione 2
  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.

• 11 marzo 2013 - Lezione 3
  Classificazione di Chomsky delle grammatiche e dei linguaggi. Esistenza di linguaggi non rappresentabili mediante grammatiche. Semidecidibilà dei linguaggi di tipo 0. Decidibilità dei linguaggi dipendenti dal contesto. Automi deterministici.

• 12 marzo 2013 - Lezione 4
  Automi nondeterministici ed equivalenza con automi deterministici. Esempi di automi deterministici e nondeterministici. Eliminazione del nondeterminismo dagli automi: un esempio vicino al caso peggiore. Distinguibilità di stringhe.

• 18 marzo 2013 - Lezione 5
  Distinguibilità di stringhe: esempi. La tecnica del "fooling set" per stabilire limiti inferiori al numero di stati di automi nondeterministici. 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.

• 19 marzo 2013 - 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. Pumping lemma per i linguaggi regolari.

• 25 marzo 2013 - Lezione 7
  Altezza di star di un linguaggio regolare. Cenni al problema dell'altezza di star generalizzata. Cenni alle macchine di Mealy e di Moore. Automi two-way: esempi di riconoscimento. Cenni alla conversione da automi two-way a one-way. Implementazione di automi a stati finiti mediante programmi.

• 26 marzo 2013 - Lezione 8
  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. Generatori di analizzatori lessicali.

• 8 aprile 2013 - Lezione 9
  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.

• 9 aprile 2013 - Lezione 10
  La notazione postfissa. Una calcolatrice in notazione postfissa. JFLex: utilizzo degli stati.

• 15 aprile 2013 - Lezione 11
  Esempi (JFlex): riconoscitore di numeri romani, convertitore da numeri romani a numeri decimali. Come aumentare la potenza degli 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.

• 16 aprile 2013 - Lezione 12
  Richiami sugli 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. Equivalenza tra grammatiche context-free e automi a pila: come trasformare una grammatica in un automa a pila equivalente.

• 22 aprile 2013 - Lezione 13
  Alberi di derivazione, derivazioni leftmost e rightmost. Ambiguità. 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.

• 23 aprile 2013 - Lezione 14
  Linguaggi context-free deterministici: chiusura rispetto al complemento. Proprietà decidibili e indecidibili per i linguaggi context-free.

• 29 aprile 2013 - Lezione 15
  Riconoscimento e parsing di linguaggi context-free. L'algoritmo CYK. L'algoritmo di Earley.

• 30 aprile 2013 - Lezione 16
  Algoritmo di Earley: esempio con ambiguità. Eliminazione dell'ambiguità nella grammatica per le espressioni aritmetiche. Aspetti dei linguaggi di programmazione non rappresentabili mediante grammatiche context-free.

• 6 maggio 2013 - Lezione 17
  Ambiguità nei linguaggi di programmazione: l'istruzione if. Introduzione al parsing top-down. Parser predittivi. Ricorsione a sinistra e sua eliminazione. Gli insiemi FIRST e FOLLOW. Grammatiche LL(1).

• 7 maggio 2013 - Lezione 18
  Un parser ricorsivo-discendente per le espressioni aritmetiche: Parser ricorsivo-discendenti. implementazione di un riconoscitore. Parser ricorsivo-discendente per le espressioni: dal riconoscitore alla calcolatrice.

• 13 maggio 2013 - Lezione 19
  Genralità sui compilatori. La struttura di un compilatore e l'organizzazione in fasi di lavoro. Analisi lessicale e sintattica.

• 14 maggio 2013 - Lezione 20
  L'analisi semantica e il type checking. Il codice intermedio. Alberi di sintassi astratta (AST) e loro implementazione in Java. Rappresentazione di espressioni aritmetiche mediante AST. Costruzione di AST per le espressioni aritmetiche.

• 20 maggio 2013 - Lezione 21
  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. Esempi di traduzione di espressioni. Schemi di traduzione per assegnamenti e accesso ad array.

• 21 maggio 2013 - Lezione 22
  Schemi di traduzione per cicli while. Organizzazione della memoria in esecuzione. Schemi di traduzione per chiamate di sottoprogrammi. Sviluppo di un compilatore per le espressioni aritmetiche con gli identificatori.

• 27 maggio 2013 - Lezione 23
  Introduzione al parsing bottom-up. Le operazioni shift e reduce. Struttura di un parser LR. Grammatiche LR(k). 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.

• 28 maggio 2013 - 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 9, 10 e 11)
  

• Parser ricorsivo-discendenti (Lezioni 18 e 21)
  

• Generazione di codice (Lezioni 21 e 22)
  

• Parser bottom-up (Lezioni 23 e 24)
  

• Progetto d'esame