Linguaggi Formali e Compilazione

Informazioni generali sull'insegnamento (A.A. 2010/11)

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

Pagina web dell'insegnamento tenuto nell'A.A. 2009/10

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.

Orario delle lezioni

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

Avvisi (in ordine cronologico inverso)

  • 26 agosto 2011 - Appello di settembre
    L'appello si terrà il giorno 15 settembre 2011, con inizio alle ore 9.00, presso l'aula X del Dipartimento di Matematica.
  • 12 luglio 2011 - Risultato dello scritto di ieri
    Nella sezione relativa agli appelli sono stati inseriti i risultati della prova scritta di ieri. La verbalizzazone si terr domani, 13 luglio 2011, alle ore 14.30 presso l'ufficio del docente (primo piano del dipartimenti di Ingegneria dell'informazione).
  • 23 febbraio 2011 - Risultati dello scritto di oggi
    Nella sezione relativa agli appelli sono stati inseriti i risultati della prova scritta. Coloro che hanno superato la prova possono verbalizzare il voto già domani mattina (presso l'ufficio del docente) o altrimenti dopo il 7 marzo.
  • 5 febbraio 2011 - Risultati dell scritto del 2 febbraio 2011
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta di ieri. La verbalizzazione (con gli eventuali orali) avrà luogo il giorno 9 febbraio 2011, alle ore 15, presso lo studio del docente (primo piano del Dipartimento di Ingegneria dell'Informazione). Si prega di avvisare via email in caso di impossibilità (comunicando anche, eventualmente, la volontà di accettare il voto).
  • 24 gennaio 2011 - Verbalizzazione voti e orali
    La verbalizzazione dei voti dello scritto del 19 gennaio u.s. e lo svolgimento delle prove orali (a richiesta) si terranno giovedì 27 gennaio 2011, alle ore 15.00, nello studio del docente presso il Dipartimento di Ingegneria dell'Informazione (primo piano).
  • 20 gennaio 2011 - Risultati dello scritto del 19 gennaio 2011
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta di ieri. Data e ora della verbalizzazione e dell'eventuale prova orale saranno comunicate con successivo avviso.
  • 27 dicembre 2010 - 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 in un anno. Per evitare equivoci, questo vuol dire che dal giorno del primo appello sostenuto fino al giorno del (l'eventuale) quarto "tentativo" devono passare più di 365 giorni.
  • 23 novembre 2010 - Rinvio lezione del 24 novembre 2010
    La lezione di domani, mercoledì 24 Novembre 2010, è sospesa per consentire la partecipazione all'Assemblea di tutte le componenti dell'Ateneo (studenti, ricercatori, personale t.a., docenti, precari) che si terrà presso il rettorato.

Materiale didattico

Libro di testo

A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman,
Compilatori: Principi, tecniche e strumenti - 2/Ed.
Pearson Addison-Wesley.

Lucidi, dispense e altro materiale didattico

Esami

Modalità d'esame

  • È prevista una prova scritta che verte su tutto il programma del corso. Chi abbia superato lo scritto (cioè ottenuto un voto maggiore o uguale a 18/30) può facoltativamente sostenere una prova orale, ovvero verbalizzare direttamente il voto dello scritto.

Iscrizione e risultati

  • È necessario iscriversi alla prova scritta tramite il sistema esse3 tassativamente entro due giorni dalla data dell'appello (il giorno prima le iscrizioni saranno chiuse). Chi riscontri problemi nell'iscrizione all'esame può inviare una mail al docente
  • L'esito della prova scritta viene comunicato su questa pagina web
  • Ci sono 6 appelli nelle sessioni di un anno accademico. Uno studente può iscriversi e partecipare a qualsiasi appello senza obbligo di consegna dell'elaborato. Tuttavia, si può consegnare l'elaborato stesso al più tre volte in un anno accademico.

Elenco degli appelli

Data appello Ora Luogo Esito scritto
19 gennaio 2011 14.30 Dipartimento di Matematica, Aula V Visualizza
2 febbraio 2011 14.30 Dipartimento di Matematica, Aula V Visualizza
23 febbraio 2011 14.30 Dipartimento di Matematica, Aula V Visualizza
11 luglio 2011 14.30 Aula XII Visualizza
15 settembre 2011 9.00 Dip. di Matematica, aula X