Pagina dell'insegnamento “Linguaggi Formali e Compilazione”

Informazioni generali (A.A. 2015/16)

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. 2014/15

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).

Contenuti

  • Alfabeti e linguaggi. Linguaggi finiti. Espressioni e linguaggi regolari. Grammatiche lineari. Automi a stati finiti determinitici e non deterministici.
  • Espressioni regolari e strumenti per la manipolazione di testi: grep, sed e awk.
  • Linguaggi liberi dal contesto. Grammatiche libere. Automi a pila non deterministici.
  • Il concetto di parsing. Parsing di tipo top-down. Grammatiche e riconoscitori LL(1). Parsing di tipo bottom-up. Linguaggi e grammatiche LR(k). Parsing SLR(1).
  • Cenni alla struttura di un compilatore. Front-end e back-end. Tabelle dei simboli.
  • Strumenti per la realizzazione di compilatori: Lex e Yacc

Orario delle lezioni

  • Mercoledì 9 - 11 (Aula M1.4 - primo piano edificio ex Matematica)
  • Giovedì 11 - 13 (Aula M1.4 - primo piano edificio ex Matematica)

Avvisi (in ordine cronologico inverso)

  • 23 settembre 2015
    La prima lezione di LFC per l'Anno Accademico 2015-16 si terrà mercoledì 30 settembre 2015.
  • 15 giugno 2016 - Risultati della prova scritta del 14 giugno 2016.
    Il file è scaricabile dalla sezione relativa agli esami. Gli studenti interessati a sostenere la prova orale e coloro che vogliono ripetere lo scritto sono pregati di contattare il docente via email. In mancanza di comunicazioni, si intenderà che viene accettato il voto pubblicato.

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.
  • Testi delle prove scritte d'esame assegnate nei precedenti anni accademici, in formato zip e gz
  • Programmi Lex e Yacc illustrati a lezione.

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 e/o una prova pratica (le due prove potranno anche essere svolte immediatamente, l'una di seguito all'altra). La prova scritta verterà su tutto il programma del corso. La prova pratica consiterà nella realizzazione di un semplice programma che ingloba un qualche aspetto algoritmico visto nel corso (es. un semplice riconoscitore di linguaggi). Chi abbia superato lo scritto e/o prova pratica, (ha cioè ottenuto un voto maggiore o uguale a 18/30) può facoltativamente sostenere una prova orale, ovvero verbalizzare direttamente il voto.

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: 3 a gennaio/febbraio, 2 a giugno/luglio e 1 a settembre. Uno studente che non abbia superato l'esame in un dato appello non può presentarsi all'appello successivo. Ci sono due eccezioni a questa regola: (1) se ha fallito il terzo appello invernale, lo studente si può comunque presentare al primo appello estivo; (2) se ha fallito l'appello di settembre si può presentare al primo appello invernale successivo.
  • Un ulteriore appello può essere previsto a novembre per gli studenti iscritti alla sessione di laurea del dicembre successivo e ai quali manchi solo l'esame di LFC.

Elenco degli appelli

Data appello Ora Luogo Esito scritto
17 dicembre 2015 14.30 Edificio ex Matematica - Aula M1.4 Visualizza
21 gennaio 2016 14.30 Edificio ex Matematica - Aula M1.5 Visualizza
4 febbraio 2016 14.30 Edificio ex Matematica - Aula M1.4 Visualizza
14 giugno 2016 9.00 Edificio ex Matematica - Aula M1.2 Visualizza