Linguaggi e traduttori
A.A. 2018/2019
Obiettivi formativi
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.
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 apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
Informazioni sul programma
# 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); cenni di gestione degli errori;
- interpreti, compilatori e transpilatori: nozioni di base, grammatiche con parametri/attributi, pattern generali.
# 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, compilatori e transpilatori;
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.
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); cenni di gestione degli errori;
- interpreti, compilatori e transpilatori: nozioni di base, grammatiche con parametri/attributi, pattern generali.
# 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, compilatori e transpilatori;
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.
Propedeuticità
- Matematica del discreto
- Logica matematica
- Programmazione
- Algoritmi e strutture dati
- Linguaggi formali e automi
- Logica matematica
- Programmazione
- Algoritmi e strutture dati
- Linguaggi formali e automi
Prerequisiti
# 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;
- 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.
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;
- 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.
Metodi didattici
Lezioni frontali (teoria) con esercitazioni guidate (pratica).
Docente/i
Ricevimento:
https://santini.di.unimi.it/d/ricevimento
stanza 5007, V piano, via Celoria, 18