Pagina dell'insegnamento “Linguaggi Formali e Compilazione”

Informazioni generali (A.A. 2014/15)

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. 2013/14

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ì 14 - 16 (Aula M2.5 - terzo piano edificio ex Matematica)
  • Giovedì 11 - 13 (Aula M2.5 - terzo piano edificio ex Matematica)

Avvisi (in ordine cronologico inverso)

  • 15 giugno 2015 - Appelli sessione estiva 2015
    Si prega di contattare il docente per concordare le date.
  • 14 gennaio 2015 - Risultati della prova scritta di ieri.
    File scaricabile dalla sezione avvisi. La data della prova orale verrà concordata in seguito con coloro che indendano eventualmente sostenerla.
  • 18 dicembre 2014 - Risultati del preappello del 17 dicembre 2014
    Il file ` scaricabile dalla sezione Appelli. Gli studenti che hanno superato la prova possono iscriversi al primo appello di gennaio per la registrazione del voto.

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 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 2014 14.00 Edificio ex Matematica - Aula M1.4 Visualizza
13 gennaio 2015 14.30 Edificio ex Matematica - Aula M2.5 Visualizza
2 luglio 2015 14.30 Edificio ex Matematica - Aula M1.3 Visualizza
23 luglio 2015 14.30 Edificio ex Matematica - Aula M1.1 Visualizza