Linguaggi e Traduttori 2

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 dai manifesti degli studi delle lauree triennali in Informatica e Informatica per le Telecomunicazioni e delle lauree magistrali in Informatica e Tecnologie dell'Informazione e della Comunicazione.
  

• È necessaria la conoscenza dei contenuti del corso di Linguaggi Formali e Automi.
  

• Il corso si tiene il martedì e il giovedì dalle 14.30 alle 16.30, nell'aula 5 di via Comelico, a partire dal 3 marzo 2009, sino ai primi di giugno.

• 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 2007/08.

Argomenti delle lezioni

• 3 marzo 2009 - Lezione 1
  Presentazione del corso. Generalità sulla nascita e l'evoluzione dei compilatori e sui legami con le grammatiche introdotte da Chomsky. Panoramica su alcune applicazioni dei linguaggi formali e strumenti per la manipolazione di testi.

• 5 marzo 2009 - 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.

• 10 marzo 2009 - Lezione 3
  Classificazione di Chomsky delle grammatiche e dei linguaggi. Alberi di derivazione per grammatiche libere dal contesto. Enumerazione di stringhe. Esistenza di linguaggi non ricorsivamente numerabili.

• 12 marzo 2009 - Lezione 4
  Automi deterministici, nondeterministici e loro equivalenza. Esempi.

• 17 marzo 2009 - Lezione 5
  Eliminazione del nondeterminismo dagli automi: un esempio vicino al caso peggiore. Equivalenza e distinguibilità tra gli stati degli automi deterministici. Minimizzazione degli automi deterministici. Automi con epsilon-mosse.

• 19 marzo 2009 - Lezione 6
  Espressioni regolari. Equivalenza tra automi a stati finiti, espressioni regolari e grammatiche di tipo 3. Cenni alle macchine di Mealy e di Moore.

• 24 marzo 2009 - Lezione 7
  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.

• 31 marzo 2009 - Lezione 8
  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. Struttura dell'analizzatore lessicale generato da JFLex.

• 16 aprile 2009 - Lezione 9
  Generazione automatica di analizzatori lessicali: un semplice esempio di riconoscitore di elementi lessicali all'interno di un testo, costruito utilizzando JFlex.

• 21 aprile 2009 - Lezione 10
  La 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.

• 23 aprile 2009 - Lezione 11
  Traduttori, compilatori e strumenti correlati. Compilatori interpretativi. Pascal e P-code. Java e Bytecode. Il ruolo del linker e la soluzione dell'ambiente Java. Requisiti di un compilatore. La struttura di un compilatore e l'organizzazione in fasi di lavoro.

• 28 aprile 2009 - Lezione 12
  Fasi di lavoro di un compilatore (conclusione). Front-end e back-end di un compilatore. Alcuni esempi con linguaggi di programmazione reali.

• 30 aprile 2009 - Lezione 13
  Richiami sugli automi a pila. Determinismo e non determinismo. Esempi di linguaggi accettati da automa a pila deterministici e non deterministici. Esempi di linguaggi per cui è necessario il nondeterminismo.

• 5 maggio 2009 - Lezione 14
  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. L'algoritmo di Earley per il riconoscimento dei linguaggi context-free.

• 7 maggio 2009 - Lezione 15
  Complessità in tempo dei linguaggi context-free. 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. Aspetti dei linguaggi di programmazione non rappresentabili mediante grammatiche context-free.

• 12 maggio 2009 - Lezione 16
  Introduzione al parsing top-down. Ricorsione a sinistra e sua eliminazione. Parser predittivi. Grammatiche LL(1).

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

• 19 maggio 2009 - Lezione 18
  Alberi di sintassi astratta (AST) e loro implementazione in Java. Rappresentazione di espressioni aritmetiche mediante AST. Costruzione di AST per le espressioni aritmetiche. Esempio: una calcolatrice con gli identificatori (inizio). Un semplice esempio di symbol table.

• 21 maggio 2009 - Lezione 19
  La calcolatrice con gli identificatori (conclusione). Un esempio di macchina a stack: struttura generale e istruzioni.

• 26 maggio 2009 - Lezione 20
  Schemi di traduzione per assegnamenti, accesso ad array, cicli while e selezione.

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

• 4 giugno 2009 - 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. Conflitti.

• 9 giugno 2009 - Lezione 23
  Generazione autoatica di parser: il generatore CUP. Il file di specifica sintattica. Utilizzo delle regole di precedenza e associatività per l'eliminazione dei conflitti. Cenni alle grammatiche con attributi.

• 11 giugno 2009 - Lezione 24
  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). 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

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 e 10)
  

• L'algoritmo di Earley (Lezione 14)
  

• Parser ricorsivo-discendenti (Lezioni 17, 18, 19 e 21)
  

• Generazione di codice (Lezioni 19, 20 e 21)
  

• Parser bottom-up (Lezioni 23 e 24)
  

• Progetto d'esame
  

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

WebCounter segnala  accessi a questa pagina dal 22 febbraio 2000