Linguaggi e traduttori II/2006-2007

News

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