Linguaggi Formali e Compilazione

Informazioni generali sull'insegnamento (A.A. 2011/12)

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. 2010/11

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 (SLR). 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.
  • Strumenti per la manipolazione di testi in cui un ruolo importante è giocato dalle espressioni regolari: Sed e AWK.
  • Linguaggi liberi. Parsing di tipo top-down. Grammatiche e riconoscitori LL(1).
  • Parsing di tipo bottom-up. Linguaggi e grammatiche LR(k). Parsing SLR.
  • Cenni alla struttura di un compilatore. Analisi lessicale e analisi sintattica. Tabelle dei simboli.
  • Strumenti per la realizzazione di compilatori: Lex e Yacc

Orario delle lezioni

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

Avvisi (in ordine cronologico inverso)

  • 19 febbraio 2012 - Risultati della prova scritta del 15 febbraio 2012
    Dalla sezione relativa agli esami è scaricabile il file dei risultati, con elencati i soli studenti che hanno superato la prova scritta. La verbalizzazione e gli eventuali orali si terrano martedì prossimo (21 febbraio 2012) alle ore 15.00 presso l'ufficio del docente.
  • 1 febbraio 2012 - Rinvio data della verbalizzazione
    A causa del maltempo la verbalizzazione e gli eventuali orali (previsti per domani) sono rinviati a mercoledì prossimo (8 febbraio 2012) alle ore 9.00, presso l'ufficio del docente.
  • 27 gennaio 2012 - Risultati della prova scritta del 25 gennaio 2012
    Dalla sezione relativa agli esami è scaricabile il file dei risultati, con elencati i soli studenti che hanno superato la prova scritta. La verbalizzazione e gli eventuali orali si terrano giovedì prossimo (2 febbraio 2012) alle ore 9.00 presso l'ufficio del docente.
  • 14 gennaio 2012 - Risultati della prova scritta dell'11 gennaio 2012
    Dalla sezione relativa agli esami è scaricabile il file dei risultati, con elencati i soli studenti che hanno superato la prova scritta. La verbalizzazione e gli eventuali orali si terrano mercoledì prossimo (18 gennaio 2012) alle ore 9.00 presso l'ufficio del docente.
  • 19 dicembre 2011 - Recupero lezione
    Come da accordi presi in aula, domani mattina (ore 11-13) si terrà il recupero della lezione persa la scorsa settimana per impegni del docente.
  • 15 novembre 2011 - Rinvio lezione del 16 novembre 2011
    La lezione di domani, 16 novembre 2011, non si terrà, causa impegni del docente. La lezione verrà recuperata il giorno successivo (giovedì 17 novembre 2011) dalle ore 14.00 alle ore 16.00). Il docente si scusa per gli eventuali inconvenienti causati.

Materiale didattico

Trasparenze proiettate a lezione

Verranno rese disponibili su questo sito (in formato pdf) con il progredire del corso.

Altro materiale fornito dal docente.

Reso disponibile come indicato sopra.

Libri di riferimento che coprono gran parte delle tematiche del corso.

  • A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilatori: Principi, tecniche e strumenti - 2/Ed.
  • S. Crespi Reghizzi, Linguaggi formali e compilazione, Pitgora Editrice Bologna.
  • G. Bruno, Linguaggi formali e compilatori, Utet Libreria.
  • J. R. Levine, T. Mason e D. Brown, Lex e Yacc, O'Reilly, collana Unix Programming Tools

Libri disponibili in rete.

Possono essere utili soprattutto per la parte relativa ai compilatori, ad eccezione del primo, di natura più generale, che tratta anche approfonditamente i linguaggi formali, le grammatiche e gli automi):

Materiale on line di alcuni insegnamenti analoghi.

Si tratta di materiale scaricabile da siti di insegnamenti attivati presso corsi di laurea in Informatica o Ingegneria informatica di Università italiane che hanno parti in comune con il presente insegnamento.

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
11 gennaio 2012 14.30 Dipartimento di Matematica, Aula V Visualizza
25 gennaio 2012 14.30 Dipartimento di Matematica, Aula V Visualizza
15 febbraio 2012 14.30 Dipartimento di Matematica, Aula V Visualizza