Linguaggi e traduttori

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'insegnamento ha l'obiettivo di introdurre i concetti fondamentali riguardanti l'analisi lessicale e sintattica e le tecniche di traduzione ed interpretazione nel contesto dei linguaggi formali. Vengono considerati gli aspetti grammaticali ed algoritmici, sia da un punto di vista teorico che con particolare attenzione ad alcuni casi concreti per i quali sono presentate soluzioni pratiche basate su strumenti software standard.
Risultati apprendimento attesi
Lo studente deve essere in grado di applicare i concetti, le tecniche e gli strumenti illustrati nell'insegnamento al progetto e sviluppo di grammatiche, traduttori ed interpreti per semplici linguaggi. Lo studente dovrà inoltre mostrare di comprendere e saper discutere in modo chiaro e con proprietà di linguaggio le soluzioni da lui adottate e le loro eventuali criticità, ponendole a confronto con altre soluzioni possibili.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
Videolezioni sincrone (se l'insegnamento sarà tenuto in modalità remota). Le videolezioni, se effettuate, non saranno comunque registrate.
Programma
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 (LL e LR);

* interpreti transpilatori e traduttori: nozioni di base, grammatiche con attributi, pattern generali.
Prerequisiti
Le conoscenze preliminari che è bene aver acquisito in modo solido prima di apprestarsi a seguire le lezioni sono:

* 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"].
Metodi didattici
Lezioni frontali. La frequenza è raccomandata.
Materiale di riferimento
I testi di riferimento per la parte teorica ed algoritmica del corso sono:

* Dick Grune e Ceriel J. H. Jacobs (2008), Parsing Techniques. A Practical Guide, Springer, New York;
* Torben Ægidius Mogensen (2017), Introduction to Compiler Design, Springer International Publishing AG.

* Terence Parr (2009), Language Implementation Patterns, The Pragmatic Bookshelf.

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

* John E. Hopcroft, Rajeev Motwani, e Jeffrey D. Ullman (2007), Introduction to Automata Theory, Languages, and Computation, Pearson.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'insegnamento non prevede prove in itinere. La prova finale è costituita da un colloquio orale (con voto in trentesimi) individuale che verte su un progetto software sviluppato dallo studente, d'intesa col docente. Durante tale colloquio, 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.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Santini Massimo
Docente/i
Ricevimento:
http://santini.di.unimi.it/d/ricevimento
stanza S207 via Comelico, 39