Linguaggi Formali e Compilazione

Informazioni generali sull'insegnamento (A.A. 2008/09)

Nome dell'insegnamento:Linguaggi Formali e Compilazione
Docente:Mauro Leoncini
Corso di Studio:Laurea triennale in Informatica
Periodo Didattico:Secondo anno, primo ciclo semestrale
SSD:INF/01
CFU:6

Obiettivi formativi e contenuti

Obiettivi formativi

L'insegnamento ha due obiettivi. Il primo è di tipo culturale. Si vuole cioè introdurre una teoria, quella alla base della realizzazione dei compilatori per i linguaggi di programmazione, che rappresenta probabilmente il più importante contributo scientifico allo sviluppo e alla diffusione delle tecnologie informatiche. Il secondo obiettivo è pratico. Infatti, anche qualora lo studente non venga mai coinvolto (nella propria carriera lavorativa) nel progetto di un nuovo compilatore, è comunque altamente probabile che egli/ella si trovi spesso ad utilizzare metodologie e tecniche che di tale teoria fanno parte: dagli automi e le grammatiche come formalismi per definire il comportamento di un sistema, alle tecniche per realizzare traduttori molto più semplici di un compilatore vero e proprio (ad esempio, l'interprete di un file di configurazione).
L'insegnamento è conseguentemente strutturato in due parti. Nella prima parte verranno introdotti i principali concetti e le tecniche relative ai linguaggi formali. Verranno studiati gli automi a stati finiti e gli automi a pila, verranno introdotte le grammatiche regolari e libere dal contesto, collocandole nella più ampia gerarchia di Chomsky. Automi e grammatiche saranno messi in relazione attraverso i due momenti di generazione e di riconoscimento di frasi. Nella seconda parte verrà studiata la struttura generale di un compilatore, ponendo poi particolare enfasi agli aspetti di analisi lessicale e di parsing. Verranno studiati parser di tipo top-down (a discesa ricorsiva, predittivi e LL(1)) e di tipo bottom-up (LR e LALR). Infine, saranno esaminati esempi di traduttori per semplici linguaggi.

Contenuti

  • Alfabeti e linguaggi. Operazioni sui linguaggi. Espressioni e linguaggi regolari. Grammatiche generative libere dal contesto.
  • Algoritmi e automi. Automi finiti deterministici e non deterministici. Eliminazione del non determinismo. Dalle espressioni regolari agli automi.
  • Linguaggi liberi e automi a pila. Parsing di tipo top-down. Grammatiche e riconoscitori LL(1).
  • Parsing di tipo bottom-up. Linguaggi e grammatiche LR(k). Parsing LR, SLR e LALR.
  • Struttura di un compilatore. Analisi lessicale e analisi sintattica. Generazione del codice intermedio e ottimizzazione (cenni). Tabelle dei simboli.
  • Strumenti per la realizzazione di compilatori. Semplici casi di studio di traduttori.

Modalità d'esame

Scritto (orale solo su richiesta).

Orario delle lezioni

  • Mercoledì 11 - 13 (Aula V Dip. Matematica)
  • Giovedì 9 - 11 (Aula V Dip. Matematica)

Avvisi (in ordine cronologico inverso)

  • 9 settembre 2009 - Risultati dello scritto di oggi
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La registrazione e gli eventuali orali (su richiesta) si terranno mercoledì prossimo (16 settembre 2009), con inizio alle ore 12.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 14 agosto 2009 - Data appello di settembre
    L'appello di settembre (ultimo per l'anno accademico in corso) è previsto per il giorno 9, alle ore 10.00 presso l'aula IX del dipartimento di Matematica. Si ricorda agli studenti che è necessario prenotarsi utilizzando il sistema esse3.
  • 6 maggio 2009 - Date appelli
    Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione estiva. Si ricorda agli studenti che è necessario prenotarsi utilizzando il sistema esse3.
  • 27 febbraio 2009 - Risultati del compito del 25 febbraio 2009
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli studenti che hanno ottenuto la sufficienza possono registrare direttamente il voto (o sostenere la prova orale, se lo desiderano). Chi non Ŕ presente nell'elenco deve comunque nuovamente sostenere la prova scritta. La registrazione dei voti e gli eventuali esami orali si terranno martedì prossimo (3 marzo 2009), con inizio alle ore 14.30, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 6 febbraio 2009 - Risultati del compito del 4 febbraio 2009
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli studenti che hanno ottenuto la sufficienza possono registrare direttamente il voto (o sostenere la prova orale, se lo desiderano). Chi non Ŕ presente nell'elenco deve comunque nuovamente sostenere la prova scritta. La registrazione dei voti e gli eventuali esami orali si terranno giovedì prossimo (12 febbraio 2009), con inizio alle ore 9.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 16 gennaio 2009 - Risultati del compito del 14 gennaio 2009
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. Gli studenti che hanno ottenuto la sufficienza possono registrare direttamente il voto (o sostenere la prova orale, se lo desiderano). Chi ha ottenuto insufficiente pu˛ sostenere la prova orale. Chi non Ŕ presente nell'elenco deve comunque nuovamente sostenere la prova scritta. La registrazione dei voti e gli eventuali esami orali si terranno martedì prossimo (20 gennaio 2009), con inizio alle ore 15.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 5 dicembre 2008 - Date appelli
    Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione invernale. Si ricorda agli studenti che è necessario prenotarsi utilizzando il sistema esse3. Si ricorda altresì che è possibile iscriversi un massimo di tre volte per anno solare.
  • 5 agosto 2008 - Data inizio lezioni
    La data di inizio lezioni è fissata per mercoledì 1 ottobre.

Materiale didattico

L'insegnamento affronta argomenti standard, ormai da molti anni trattati (a vari livelli di profondità) in più di un testo universitario. Per preparare adeguatamente l'esame, lo studente deve avere come primo riferimento l'elenco degli argomenti affrontati. Potrà quindi utilizzare (parte de) il materiale didattico elencato di seguito per formare o completare (nel caso di studenti frequentanti) la propria preparazione.

Esami

Data appello Ora Luogo Esito scritto
14 gennaio 2009 15.00 Dipartimento di Matematica, Aula V Visualizza
4 febbraio 2009 15.00 Dipartimento di Matematica, Aula V Visualizza
25 febbraio 2009 15.00 Dipartimento di Matematica, Aula V Visualizza
10 giugno 2009 15.00 Dipartimento di Matematica, Aula V
14 luglio 2009 14.30 Dipartimento di Matematica, Aula V
9 settembre 2009 10.00 Dipartmento di Matematica, Aula IX Visualizza