Linguaggi e traduttori

Anno Accademico 2009/2010

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).

• Il corso si tiene il lunedì e il martedì dalle 14.30 alle 16.30, pressa l'aula 6 di via Comelico, dal 1º marzo al 1º giugno 2010.

• Per ulteriori informazioni, consultate il sito del Coordinamento Didattico di Scienze e Tecnologie Informatiche.
  

• 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

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

• 2 marzo 2010 - Lezione 2
  Richiami su alcune nozioni fondamentali: alfabeto, stringa, linguaggio. Come rappresentare i linguaggi: esempi di rappresentazioni finite di linguaggi infiniti. Semplici esempi di grammatiche e di riconoscitori di linguaggi.

• 8 marzo 2010 - Lezione 3
  Grammatiche e derivazioni. Esempi di grammatiche. Classificazione di Chomsky delle grammatiche e dei linguaggi.

• 9 marzo 2010 - Lezione 4
  Ricorsività dei linguaggi dipendenti dal contesto. Alberi di derivazione per grammatiche libere dal contesto. Automi deterministici. Esempi.

• 15 marzo 2010 - Lezione 5
  Automi nondeterministici ed equivalenza con automi deterministici. Eliminazione del nondeterminismo dagli automi: un esempio vicino al caso peggiore. Distinguibilità di stringhe.

• 16 marzo 2010 - Lezione 6
  Equivalenza e distinguibilità tra gli stati degli automi deterministici. Minimizzazione degli automi deterministici. Automi con epsilon-mosse. Equivalenza tra automi a stati finiti e grammatiche di tipo 3.

• 22 marzo 2010 - Lezione 7
  Espressioni regolari. Costruzione di automi a stati finiti a partire da espressioni regolari

• 23 marzo 2010 - Lezione 8
  Costruzione di espressioni regolari a partire da automi a stati finiti. Complemento e reversal di linguaggi regolari. Esempi di linguaggi non regolari.

• 29 marzo 2010 - Lezione 9
  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. Cenni all'implementazione di automi a stati finiti mediante programmi.

• 30 marzo 2010 - Lezione 10
  Introduzione ai generatori di analizzatori lessicali. 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.

• 12 aprile 2010 - 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.

• 13 aprile 2010 - Lezione 12
  La notazione postfissa. Una calcolatrice in notazione postfissa. Inadeguatezza dei linguaggi regolari per la descrizione di espressioni in notazione infissa. JFLex: utilizzo degli stati. Esempi: riconoscitore di numeri romani, convertitore da numeri romani a numeri decimali.

• 26 aprile 2010 - Lezione 13
  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.

• 27 aprile 2010 - 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.

• 3 maggio 2010 - 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.

• 4 maggio 2010 - 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).

• 10 maggio 2010 - Lezione 17
  Parser ricorsivo-discendenti. Un parser ricorsivo-discendente per le espressioni aritmetiche: implementazione del riconoscitore, implementazione di una calcolatrice.

• 11 maggio 2010 - Lezione 18
  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. Java e Bytecode. Il ruolo del linker e la soluzione dell'ambiente Java.

• 17 maggio 2010 - 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.

• 18 maggio 2010 - Lezione 20
  La calcolatrice estesa con gli identificatori. Un semplice esempio di symbol table. Un esempio di macchina a stack: struttura generale e istruzioni. Esempi di traduzione di espressioni. Schemi di traduzione per assegnamenti.

• 24 maggio 2010 - Lezione 21
  Sviluppo di un compilatore per le espressioni aritmetiche con gli identificatori. Schemi di traduzione per accesso ad array, cicli while.

• 25 maggio 2010 - Lezione 22
  Schemi di traduzione per selezione. Organizzazione della memoria in esecuzione. Schemi di traduzione per chiamate di sottoprogrammi. Introduzione al parsing bottom-up. Le operazioni shift e reduce. Struttura di un parser LR. Grammatiche LR(k) e cenni a loro varianti.

• 31 maggio 2010 - Lezione 23
  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.

• 1º giugno 2010 - Lezione 24
  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 e 12)
  

• Parser ricorsivo-discendenti (Lezioni 17, 19, 20)
  

• Generazione di codice (Lezioni 20, 21, 22)
  

• Parser bottom-up (Lezioni 23 e 24)
  

• Anni precedenti: 2008/2009, 2007/2008, 2006/2007, 2005/2006, 2004/2005
  

WebCounter segnala accessi a queste pagine dal 23 febbraio 2010