Linguaggi e traduttori
A.A. 2024/2025
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.
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Secondo semestre
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.
* 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 [dall'insegnamento di "Programmazione"];
* strutture dati elementari (liste, pile, code e dizionari); grafi e alberi e relativi algoritmi di visita (ampiezza, profondità ) [dall'insegnamento di "Algoritmi e strutture dati"];
* aspetti di base dei linguaggi formali [dall'insegnamento "Linguaggi formali e automi"].
* 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 [dall'insegnamento di "Programmazione"];
* strutture dati elementari (liste, pile, code e dizionari); grafi e alberi e relativi algoritmi di visita (ampiezza, profondità ) [dall'insegnamento di "Algoritmi e strutture dati"];
* aspetti di base dei linguaggi formali [dall'insegnamento "Linguaggi formali e automi"].
Metodi didattici
Lezioni frontali. La frequenza è raccomandata.
Materiale di riferimento
I testi di riferimento per la parte teorica ed algoritmica dell'insegnamento 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 dall'insegnamento di "Linguaggi formali", è il classico:
* John E. Hopcroft, Rajeev Motwani, e Jeffrey D. Ullman (2007), Introduction to Automata Theory, Languages, and Computation, Pearson.
* 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 dall'insegnamento 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.
* 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
Turni:
Turno
Docente:
Santini MassimoDocente/i
Ricevimento:
https://santini.di.unimi.it/d/ricevimento
stanza 5007, V piano, via Celoria, 18