Linguaggi e traduttori II/2006-2007

News

 La lezione di giovedì 15 marzo è sospesa.

Appelli

 29/1/2007 - 27/2/2007 - 12/4/2007 - 11/6/2007 - 9/7/2007 - 21/9/2007

Informazioni generali

Docenti

 Prof. Giovanni Pighizzini
  Email: pighizzi [AT] dico [DOT] unimi [DOT] it
  Pagina personale: http://pighizzini.dico.unimi.it/

Modalità d'esame

• L'esame consisterà nello svolgimento e discussione di un progetto per chi vuole presentarsi ai primi appelli (il progetto sarà in linea con gli esercizi svolti a lezione, di conseguenza questa è la modalità consigliata per i frequentanti), altrimenti consisterà in una prova orale sugli argomenti del corso.

Prerequisiti al corso

 Linguaggi formali e automi.

Orari e luogo delle lezioni

 Martedì: 14:30-16:30, auletta 5, via Comelico
 Giovedì: 14:30-16:30, auletta 5, via Comelico

Orario di ricevimento studenti

 Martedì dalle 11:00 alle 13:00, stanza P118 via Comelico 39

Informazioni specifiche

Sito del corso

 http://pighizzini.dico.unimi.it/linguaggi/

Materiale didattico

Programma del corso

1. Generalità

Introduzione alla struttura e al disegno di un compilatore. Fasi di lavoro di un compilatore. Front-end e back-end. Interpreti, assemblatori e altri strumenti per la manipolazione dei linguaggi di programmazione.

2. Manipolazione automatica di linguaggi regolari

Richiami su linguaggi regolari, espressioni regolari e automi a stati finiti. Implementazione di programmi per il riconoscimento di linguaggi regolari. Analizzatori lessicali. Strumenti per la generazione automatica di analizzatori lessicali (lex, flex, jflex, ...).

3. Manipolazione automatica di linguaggi liberi dal contesto

Richiami sui linguaggi liberi dal contesto. Algoritmi generali di parsing (CYK e algoritmo di Earley). Analizzatori sintattici: tecniche generali di parsing (top down e bottom up). Strumenti per la generazione automatica di analizzatori sintattici (yacc, CUP, ...).

4. Analisi semantica e generazione di codice

Grammatiche ad attributi. Type checking Schemi di traduzione diretta dalla sintassi e loro implementazione. Symbol table. Gestione degli errori. Codice intermedio. Generazione e ottimizzazione del codice.

Testi

 A. Aho, M. Lam, R. Sheti, J. Ullman, Compilers. Principles, techniques and tools, 2/E, Addison-Wesley, 2007
 (oppure prima edizione 1986).
 A.W. Appel, Modern Compiler Implementation in Java, Cambridge University Press, 1998.

Diario del corso

Lezione di Martedì 06 marzo 2007

• Introduzione al corso e informazioni generali.
• Nozioni di base per definire un compilatore:
  • Definizione di alfabeto, stringa, linguaggio
  • Rappresentazione riconoscitiva (=automi) vs generativa (grammatiche)
  • Classificazione delle grammatiche di Chomsky e relazione con i riconoscitori (automi a stati finiti/a pila, macchine di Turing)
  • Concetto di distanza fra due stringhe (distanza di Hamming, edit distance) e di distanza fra una stringa e un linguaggio.

Lezione di Giovedì 08 marzo 2007

• Ancora introduzione ai compilatori:
  • Differenza tra compilatori, assemblatori, interpreti, compilatori interpretativi (Pascal e P-code, Java e Bytecode), editor e formattatori
  • Distinzione tra sintassi e semantica, accenno alle grammatiche con attributi (di cui parleremo più avanti)
  • Definizione formale di traduttore
  • Compilatori just-in-time, Java HotSpot, concetto di portabilità (tutto ciò solo accennato senza entrare nei dettagli)
  • Tecniche di bootstrap e cross compiling.

Lezione di Martedì 13 marzo 2007

• Linker
  • Fase di verifica
  • Fase di collegamento.
• Requisiti per un buon compilatore.
• Struttura generale di un compilatore:
  • Panoramica ad alto livello sulle fasi del compilatore
  • Gestione della symbol table
  • Analisi lessicale (tokens)
  • Analisi sintattica (parse tree)
  • Analisi semantica (type checking)
  • Generazione di codice intermedio (passate).

Lezione di Martedì 20 marzo 2007

• Generazione del codice intermedio
  • Codice per macchina a stack / Codice a 3 indirizzi
  • Ottimizzazione del codice intermedio.
• Problema dell'organizzazione della memoria.
• Compilatori front-end e back-end.
• Analizzatore lessicale
  • Definizione dei token
  • Problemi nel riconoscimento dei token (longest match + parole riservate)
  • Esempi di scomposizione in token su alcuni linguaggi.

Lezione di Giovedì 22 marzo 2007

• Token con attributi.
• Automi a stati finiti
  • Ripasso dei concetti base necessari a definire i linguaggi e gli automi
  • Equivalenza tra automi deterministici, non deterministici e con $\varepsilon$-mosse.

Lezione di Martedì 27 marzo 2007

• Espressioni regolari e relazione con gli automi a stati finiti.
• Minimizzazione di automi, definizione di stati indistinguibili.
• Macchine di Moore e di Mealy.
• Simulazione di automi tramite un programma.
• Implementazione di analizzatori lessicali con l'uso di automi a stati finiti.
• Struttura generale della specifica lessicale.

Lezione di Giovedì 29 marzo 2007

• Gestione delle eccezioni e degli stream di byte/caratteri in Java.
• Generazione dell'analizzatore lessicale con JFlex:
  • Opzioni della specifica lessicale
  • Esempi scaricabili da qui.