Linguaggi Formali e Compilazione

Informazioni generali sull'insegnamento (A.A. 2012/13)

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
Orario di ricevimento

Pagina web dell'insegnamento tenuto nell'A.A. 2011/12

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)

  • 31 gennaio 2013 - Risultati della prova scritta del 30 gennaio 2013
    Dalla sezione relativa agli esami è scaricabile il file dei risultati, con elencati i soli studenti che hanno superato la prova scritta. Gli studenti che desiderano verbalizzare direttamente il voto (senza sostenere la prova orale) e che hanno solo il libretto elettronico, ovvero coloro che desiderano ripetere la prova scritta, possono semplicemente inviare una comunicazione al docente. Gli altri sono convocati per il giorno 7 febbraio p.v., alle ore 8.45, per gli eventuali orali e/o la verbalizzazione su libretto cartaceo.
  • 20 gennaio 2013 - Risultati della prova scritta del 16 gennaio 2013
    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 (22 gennaio 2013) alle ore 14.30 presso l'ufficio del docente.
  • 31 dicembre 2012 - Appelli sessione invernale 2013
    Sono state fissate le date per gli appelli di gennaio-febbraio 2013 (si consulti la sezione relativa agli esami). Si ricorda che l'iscrizione su esse3 è obbligatoria.

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, Pitagora 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
16 gennaio 2013 14.30 Edificio ex Matematica, Aula IV Visualizza
30 gennaio 2013 14.30 Edificio ex Matematica, Aula V Visualizza
13 febbraio 2013 14.30 Edificio ex Matematica, Aula V