Pagina dell'insegnamento “Linguaggi Formali e Compilazione”

Informazioni generali (A.A. 2013/14)

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. 2012/13

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ì 14 - 16 (Aula V Edificio ex Matematica)
  • Giovedì 11 - 13 (Aula V Edificio ex Matematica)

Avvisi (in ordine cronologico inverso)

  • 20 febbraio 2014 - Risultati della prova scritta del 19 febbraio 2014
    Dalla sezione relativa agli appelli è scaricabile il file con l'elenco degli studenti che hanno superato l'esame. Questi DEVONO inviare una email al docente dichiarando di voler sostenere la prova orale ovvero, in alternativa, se intendono rifiutare o accettare il voto (coloro cha hanno preso 30 e lode sono ovviamente esentati).
    L'orale, per coloro che intendono sostenerlo, si terrà il giorno 25 febbraio 2014 alle ore 10.00 presso l'ufficio del docente.
  • 7 febbraio 2014 - Risultati della prova scritta del 5 febbraio u.s.
    Nella sezione relativa agli appelli è scaricabile il file con l'elenco degli studenti che hanno superato l'esame. L'orale, per coloro che intendono sostenerlo, si terrà nella settimana del 17 febbraio 2014. Solo chi intende sostenere l'orale è pregato di mandare una email al docente.
  • 19 gennaio 2014 - Risultati della prova scritta del 15 gennaio 2014
    Nella sezione relativa agli appelli è scaricabile il file con i risultati. Gli studenti sono convocati per mercoledì prossimo (22 gennaio 2014) per gli eventuali orali, la verbalizzazione e per prendere visione degli elaborati.
  • 13 dicembre 2013 - Orario per l'ultima settimana di lezione
    La lezione di mercoledì 18 non si terrà causa concomitanti esami di laurea di Informatica. Il recupero avrà luogo giovedì 19 dalle 9 alle 11. SI precisa che le ultime 4 ore saranno di sola esercitazione.

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
15 gennaio 2014 14.30 Edificio ex Matematica, Aula V Visualizza
5 febbraio 2014 14.30 Edificio ex Matematica, Aula V Visualizza
19 febbraio 2014 10.30 Edificio ex Matematica, Aula V Visualizza