Informazioni sul corso

Orario e modalità delle lezioni

Le lezioni del corso si tengono il martedì alle ore 11:30 – 13:30 (o dalle 10:30 alle 14:30, in caso di esercitazioni) in Aula 109 e il giovedì alle ore 11:30 – 13:30 in Aula Alfa.

Le lezioni (ed esercitazioni) sono frontali, nell'attuale manifesto degli studi il corso non prevede un laboratorio; per questa e altre ottime ragioni in classe è vietato l'uso di laptop e strumenti analoghi.

Obiettivi dell’insegnamento

La teoria dei linguaggi formali è una delle discipline centrali dell'informatica; l'uso delle grammatiche da essa studiate non solo permette di definire in modo conciso ed esatto insiemi infiniti (come ad esempio: i programmi sintatticamente corretti, i documenti HTML validi, i file XML ben formati, gli indirizzi email o le URL aderenti allo standard), ma consente anche vari tipi di trattamento automatico dei medesimi. In particolare, permette di definire traduttori che, sfruttando la struttura grammaticale, conseguono obiettivi di grande complessità ed utilità (come, ad esempio: la compilazione, interpretazione e transpilazione del codice, l'individuazione di errori di programmazione, l'estrazione di informazioni strutturate…).

Questo insegnamento ha per obiettivo l'apprendimento degli aspetti teorici e algoritmici dei linguaggi formali coinvolti nelle attività di definizione e uso delle grammatiche, analisi e traduzione e di metterli in pratica attraverso la realizzazione di programmi concreti relativi a semplici casi di studio.

Risultati di apprendimento attesi

A seguito del superamento dell'esame, lo studente:

  • conosce le principali nozioni riguardanti i linguaggi regolari e liberi dal contesto,

  • conosce le tecniche di analisi lessicale e sintattica di base e la loro implementazione pratica,

  • conosce alcuni rudimenti del funzionamento di interpreti, transpilatori e più in generale di traduzione tra formati strutturati;

inoltre è in grado di:

  • definire una grammatica (regolare, o libera dal contesto) per descrivere semplici linguaggi di uso comune,

  • utilizzare uno strumento di costruzione automatica di analizzatori lessicali e sintattici,

  • scrivere il codice necessario a realizzare semplici traduttori.

Argomenti trattati

Riguardo all'ambito generale dei linguaggi formali:

  • nozioni di base: alfabeto, linguaggio, grammatica;

  • gerarchia di Chomsky, con particolare riferimento a linguaggi regolari e liberi dal contesto (e relative forme normali);

  • riconoscimento e generazione: derivazioni, ambiguità, alberi sintattici;

  • automi a stati finiti e a pila, deterministici e non.

Riguardo agli aspetti legati alla traduzione:

  • analisi lessicale e divisione in token: espressioni regolari, relazione con gli automi a stati finiti;

  • analisi grammaticale e parsing: tecniche generali non direzionali, tecniche generali direzionali (top-down e bottom-up), tecniche deterministiche (grammatiche LL e LR);

  • interpreti transpilatori e traduttori: nozioni di base, grammatiche con attributi, pattern generali.

Prerequisiti

Di seguito sono elencate alcune conoscenze preliminari che è bene aver acquisito in modo solido prima di apprestarsi a seguire le lezioni:

  • tecniche di dimostrazione, con particolare riguardo a quella per induzione [dagli insegnamenti di "Matematica del discreto" e/o "Logica matematica"];

  • programmazione, con particolare riguardo alla ricorsione [dal corso di "Programmazione"];

  • strutture dati elementari (liste, pile, code e dizionari); grafi e alberi e relativi algoritmi di visita (ampiezza, profondità…) [dal corso di "Algoritmi e strutture dati"];

  • aspetti di base dei linguaggi formali [dal corso "Linguaggi formali e automi"].

Modalità di valutazione

L'insegnamento non prevede prove in itinere. La prova finale è costituita da un colloquio orale in cui il candidato deve dimostrare:

  • la conoscenza delle definizioni e delle nozioni teoriche fondamentali, e la comprensione del funzionamento dei vari algoritmi di analisi lessicale e sintattica e traduzione;

  • la capacità di applicare tale conoscenza a un semplice caso concreto, sia in relazione agli aspetti grammaticali che algoritmici;

  • la capacità di utilizzare uno strumento per la generazione automatica di analizzatori e/o traduttori.

La prova orale può essere accompagnata da un progetto software da realizzare in modo autonomo, o in gruppo, come concordato assieme al docente nell'arco delle lezioni.

Bibliografia

I testi di riferimento per la parte teorica ed algoritmica del corso sono:

La maggior parte del materiale sarà tratta dai primi capitoli del primo libro (di cui è possibile scaricare una versione PDF gratuita dalla rete dell'Ateneo, nei termini della licenza d'uso stabilita dall'editore); il secondo testo tratta aspetti più pratici e legati allo strumento di costruzione automatica di analizzatori lessicali e sintattici utilizzato nel corso.

Come approfondimento individuale, con maggior orientamento alla parte di costruzione di interpreti e compilatori, si consiglia

  • Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs e Koen Langendoen (2012) Modern Compiler Design, Springer, New York;

mentre per quanto concerne lo strumento di costruzione automatica di analizzatori lessicali e sintattici, il testo di riferimento è:

Un testo di riferimento per i linguaggi formali, utile come approfondimento, o per colmare eventuali lacune rimaste dal corso di "Linguaggi formali", è il classico:

Ci sono validi testi in italiano che riguardano sia la parte dei linguaggi formali che quella di analisi e traduzione, come:

sono suggeriti solo per chi avesse seri problemi con la lingua inglese, per tutti gli altri studenti si raccomanda l'uso dei volumi sopra citati.