Linguaggi e Traduttori 2

• Il corso è terminato martedì 29 maggio.
  

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

• Per programma, avvisi e ulteriori informazioni, consultare la relativa pagina sul sito del Coordinamento Didattico di Scienze e Tecnologie Informatiche.
  

Argomenti delle lezioni

• 6 marzo 2007 - 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.

• 8 marzo 2007 - Lezione 2
  Traduttori, compilatori e strumenti correlati. Interpreti. Generazione di compilatori a partire da compilatori esistenti. Boostrap di compilatori. Compilatori interpretativi. Pascal e P-code. Java e Bytecode.

• 13 marzo 2007 - Lezione 3
  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. Descrizione generale delle fasi di analisi lessicale, sintattica e semantica.

• 20 marzo 2007 - Lezione 4
  Descrizione generale delle fasi di generazione del codice intermedio, ottimizzazione, generazione dl codice. Gestione degli errori. Front-end e back-end di un compilatore. La fase di analisi lessicale. Esempi di token di un linguaggio di programmazione. La regola del longest match. Alcuni esempi con linguaggi di programmazione reali.

• 22 marzo 2007 - Lezione 5
  Token con attributi. Richiami sugli automi deterministici, non deterministici, con epsilon-mosse e loro equivalenza.

• 27 marzo 2007 - Lezione 6
  Richiami su espressioni regolari ed equivalenza con automi a stati finiti, minimizzazione di automi. Implementazione di automi a stati finiti mediante programmi. Uso degli automi a stati finiti per la costruzione di analizzatori lessicali. Introduzione ai generatori di analizzatori lessicali.

• 29 marzo 2007 - Lezione 7
  Breve richiamo sulle eccezioni e sugli stream di byte e caratteri in Java. Il file di specifica lessicale di JFLex. Struttura dell'analizzatore lessicale generato da JFLex. Utilizzo dell'analizzatore lessicale generato da JFLex. Alcuni esempi di specifica lessicale e d'uso.

• 3 aprile 2007 - Lezione 8
  JFLex: utilizzo degli stati. Esempio: convertitore da numeri romani a decimali. La notazione postfissa.

• 12 aprile 2007 - Lezione 9
  Inadeguatezza dei linguaggi regolari per la descrizione della sintassi dei linguaggi di programmazione. 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. Esempi di linguaggi non accettati da automi a pila. Definizione di grammatica.

• 17 aprile 2007 - Lezione 10
  Classificazione di Chomsky. Alberi di derivazione e derivazioni leftmost. Grammatiche ambigue. Algoritmi generali di riconoscimento e parsing di linguaggi liberi dal contesto.

• 19 aprile 2007 - Lezione 11
  L'algoritmo di Earley. Ambiguità nei linguaggi di programmazione: l'istruzione if. Aspetti dei linguaggi di programmazione non rappresentabili mediante grammatiche libere dal contesto.

• 24 aprile 2007 - Lezione 12
  Eliminazione dell'ambiguità nella grammatica per le espressioni aritmetiche. Introduzione al parsing top-down. Il problema della ricorsione a sinistra e sua eliminazione.

• 26 aprile 2007 - Lezione 13
  Parser predittivi. Grammatiche LL(1). Parser ricorsivo-discendenti.

• 3 maggio 2007 - Lezione 14
  Un parser ricorsivo-discendente per le espressioni aritmetiche: implementazione del riconoscitore, implementazione di una calcolatrice, implementazione di un convertitore in notazione postfissa.

• 8 maggio 2007 - Lezione 15
  Alberi di sintassi astratta (AST) e loro implementazione in Java. Rappresentazione di espressioni aritmetiche mediante AST. Costruzione di AST per le espressioni aritmetiche.

• 10 maggio 2007 - Lezione 16
  Esempio: una calcolatrice con gli identificatori. Un semplice esempio di symbol table. Un esempio di macchina a stack: struttura generale, classi di istruzioni, istruzioni di trasferimento dati, istruzioni aritmetiche.

• 15 maggio 2007 - Lezione 17
  Un esempio di macchina a stack (continuazione): istruzioni di salto e altre istruzioni. Sviluppo di un compilatore per le espressioni aritmetiche con gli identificatori.

• 17 maggio 2007 - Lezione 18
  Parsing bottom-up. Shift-reduce. Struttura di un parser LR. Grammatiche LR(k) e cenni a loro varianti. Conflitti.

• 22 maggio 2007 - Lezione 19
  Generazione automatica di parser: esempi con CUP. Il file di specifica sintattica. Utilizzo delle regole di precedenza e associatività per l'eliminazione dei conflitti. Cenni alle grammatiche con attributi. Calcolo degli attributi sintetizzati. Esempio: implementazione di una calcolatrice mediante il parser generato da CUP.

• 24 maggio 2007 - Lezione 20
  Ulteriori esempi con CUP (costruzione di AST per la calcolatrice, aggiunta degli identificatori). Schemi di traduzione per assegnamenti, accesso ad array, cicli while.

• 29 maggio 2007 - Lezione 21
  Schemi di traduzione per selezione. Organizzazione della memoria in esecuzione. Schemi di traduzione per chiamate di sottoprogrammi. Presentazione del progetto d'esame.

Materiale didattico

• Analizzatori lessicali (Lezioni 7 e 8)
  

• Parser ricorsivo-discendenti (Lezioni 14-17)
  

• Generazione di codice (Lezioni 16-17)
  

• Parser bottom-up (Lezioni 19 e segg.)
  

• Progetto d'esame
  

• Anni precedenti: 2005/2006, 2004/2005
  

WebCounter segnala  accessi a questa pagina dal 22 febbraio 2000