Linguaggi e Traduttori 2

In questa pagina potete trovare

Informazioni generali
Argomenti delle lezioni
Materiale didattico

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.
  

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

Argomenti delle lezioni

• 4 marzo 2008 - 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.

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

• 11 marzo 2008 - 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.

• 13 marzo 2008 - Lezione 4
  Descrizione generale delle fasi di analisi lessicale, analisi sintattica, analisi semantica, generazione del codice intermedio, ottimizzazione, generazione dl codice. Gestione degli errori. Front-end e back-end di un compilatore. Alcuni esempi con linguaggi di programmazione reali.

• 18 marzo 2008 - Lezione 5
  La fase di analisi lessicale. Esempi di token di un linguaggio di programmazione. La regola del longest match. Token con attributi.

• 27 marzo 2008 - Lezione 6
  Richiami sugli automi deterministici, non deterministici, con epsilon-mosse e loro equivalenza. Richiami su espressioni regolari.

• 1° aprile 2008 - Lezione 7
  Richiami su equivalenza tra espressioni regolari e automi a stati finiti. Implementazione di automi a stati finiti mediante programmi. Uso degli automi a stati finiti per la costruzione di analizzatori lessicali.

• 3 aprile 2008 - Lezione 8
  Introduzione ai generatori di analizzatori lessicali. Il file di specifica lessicale di JFLex. Breve richiamo sugli stream di byte e di caratteri in Java. Struttura dell'analizzatore lessicale generato da JFLex.

• 8 aprile 2008 - Lezione 9
  Breve richiamo sulle eccezioni in Java. Utilizzo dell'analizzatore lessicale generato da JFLex. Alcuni esempi di specifica lessicale e d'uso. Utilizzo degli stati.

• 10 aprile 2008 - Lezione 10
  Esempio (JFLex): convertitore da numeri romani a decimali. La notazione postfissa. Inadeguatezza dei linguaggi regolari per la descrizione della sintassi dei linguaggi di programmazione.

• 15 aprile 2008 - Lezione 11
  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 ed esempi.

• 17 aprile 2008 - Lezione 12
  Classificazione di Chomsky. Alberi di derivazione e derivazioni leftmost. Grammatiche ambigue. Eliminazione dell'ambiguità nella grammatica per le espressioni aritmetiche. Algoritmi generali di riconoscimento e parsing di linguaggi liberi dal contesto.

• 22 aprile 2008- Lezione 13
  Ambiguità nei linguaggi di programmazione: l'istruzione if. Aspetti dei linguaggi di programmazione non rappresentabili mediante grammatiche libere dal contesto. Introduzione al parsing top-down.

• 24 aprile 2008 - Lezione 14
  Eliminazione dell'ambiguità nella grammatica per le espressioni aritmetiche. Introduzione al parsing top-down. Il problema della ricorsione a sinistra e sua eliminazione. Parser predittivi. Grammatiche LL(1).

• 29 aprile 2008 - Lezione 15
  Parser ricorsivo-discendenti. Un parser ricorsivo-discendente per le espressioni aritmetiche: implementazione del riconoscitore, implementazione di una calcolatrice, implementazione di un convertitore in notazione postfissa.

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

• 8 maggio 2008 - Lezione 17
  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.

• 13 maggio 2008 - Lezione 18
  Un esempio di macchina a stack (continuazione): istruzioni di salto e altre istruzioni. Schemi di traduzione per assegnamenti, accesso ad array, cicli while e selezione.

• 15 maggio 2008 - Lezione 19
  Sviluppo di un compilatore per le espressioni aritmetiche con gli identificatori. Organizzazione della memoria in esecuzione. Schemi di traduzione per chiamate di sottoprogrammi. Introduzione al parsing bottom-up, shift-reduce.

• 20 maggio 2008 - Lezione 20
  Struttura di un parser LR. Grammatiche LR(k) e cenni a loro varianti. Conflitti. 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.

• 22 maggio 2008 - Lezione 21
  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.

Materiale didattico

• Analizzatori lessicali (Lezioni 9 e 10)
  

• Parser ricorsivo-discendenti (Lezioni 15 - 19)
  

• Generazione di codice (Lezioni 17 - 19)
  

• Parser bottom-up (Lezioni 20 e 21)
  

• Progetto d'esame
  

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

WebCounter segnala  accessi a questa pagina dal 22 febbraio 2000