Contact

Linguaggi Formali e Compilatori

Scopo del corso è l'acquisizione delle nozioni fondamentali della teoria dei linguaggi formali, e dei principi di funzionamento dei compilatori e dei traduttori. Le competenze acquisite consentiranno di sviluppare interpreti, compilatori, e traduttori secondo il paradigma della programmazione orientata agli oggetti. 

  • N. ore di didattica assistita: 24 ore di lezioni + 24 ore di esercitazioni
  • SSD: INF/01 - informatica

Modalità di Esame

L'esame consta di una prova scritta, e nella discussione di un progetto di un traduttore. Il progetto è individuale, e scelto liberamente da ogni studente sulla base delle indicazioni di massima fornite dal docente durante il corso.

La prova orale è facoltativa. Gli studenti hanno inoltre la possibilità di far vertere la prova orale interamente sulla discussione di un progetto più complesso di quello obbligatorio. Tale progetto dovrà essere concordato preventivamente col docente, e realizzzato in gruppi di al più tre unità.

Programma del Corso

  • Linguaggi e Grammatiche: Linguaggi. Grammatiche. Concetto di derivazione.
  • Linguaggi Regolari e Analizzatori Lessicali: Grammatiche di tipo 3 e linguaggi regolari. Espressioni regolari. Automi deterministici e non, eliminazione del non-determinismo. Esempi di scrittura di analizzatori lessicali. Utilizzo di un generatore di analizzatori lessicali.
  • Linguaggi Non Contestuali e Automi a Pila: Alberi di parsing. Derivazioni. Automi a pila deterministici e non. Analisi sintattica di tipo ascendente o discendente.
  • Analisi Discendente: Grammatiche LL(1), calcolo delle tabelle di parsing e degli insiemi guida. Scrittura di un analizzatore sintattico ricorsivo. Recupero degli errori.
  • Grammatiche ad Attributi per l’Analisi Semantica: Le grammatiche ad attributi. Attributi ereditati e sintetizzati. Azioni con effetti collaterali. Azioni semantiche.
  • Analisi Ascendente: Grammatiche LR(0), LR(1), SLR(1), LALR(1). 

Riferimenti

  • J. E. Hopcroft, R. Motwani, J. D. Ullman, Automi, linguaggi e calcolabilità, Addison Wesley
  • G. Ausiello, F. D'Amore, G. Gambosi, Linguaggi, Modelli Complessità, Disponibile elettronicamente sul sito del corso di informatica teorica del Prof. Ausiello.
  • D. Saccà. Materiale didattico per la realizzazione di parser LL(1).

Ricevimento

Il docente riceve il Martedì dalle ore 11:30 alle ore 13:30.