LINGUAGGI E TRADUTTORI
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2021/2022
- Docente
- MARCO GAVANELLI
- Crediti formativi
- 6
- Periodo didattico
- Secondo Semestre
- SSD
- ING-INF/05
Obiettivi formativi
- I principali obiettivi formativi del corso sono due:
1. apprendere le principali conoscenze teoriche e pratiche utili a definire un linguaggio di programmazione e a sviluppare un traduttore per esso (interprete o compilatore), con particolare enfasi sugli aspetti associati al riconoscimento del linguaggio (tokenization e parsing)
2. progettare programmi in un linguaggio di programmazione funzionale (uno dei quattro paradigmi di programmazione), sapendo utilizzare ed implementare funzioni di ordine superiore.
Per il primo obiettivo, le principali conoscenze acquisite saranno
- saper classificare i linguaggi secondo la classificazione di Chomsky, correlando l'espressività del linguaggio con la complessità dei corrispondenti automi riconoscitori
- saper sviluppare riconoscitori, interpreti e compilatori per linguaggi regolari e indipendenti dal contesto.
Le principali abilità (ossia la capacità di applicare le conoscenze acquisite) per il primo obiettivo saranno:
- definire formalmente linguaggi e grammatiche che li generano
- riconoscere le relazioni fra grammatiche e linguaggi generati
- classificare le grammatiche nella gerarchia di Chomsky
- progettare riconoscitori per grammatiche regolari
- progettare riconoscitori per grammatiche indipendenti dal contesto con metodologia LL
- progettare interpreti e bozze di compilatori per una semplice grammatica
- capacità di utilizzare strumenti per la generazione automatica di riconoscitori di linguaggi regolari
Per il secondo obiettivo, le principali conoscenze acquisite saranno
- descrivere le principali caratteristiche della programmazione funzionale e differenze con i paradigmi di programmazione imperativo e ad oggetti
- progettazione di programmi in un linguaggio puramente funzionale
- descrivere ed utilizzare durante la programmazione il passaggio dei parametri con valutazione "lazy" degli argomenti
- progettare programmi che utilizzano funzioni di ordine superiore; progettare nuove funzioni di ordine superiore
- progettare programmi che utilizzano la monade dell'input-output, per mantenere separate programmazione puramente funzionale e input/output con sintassi simile a quella dei linguaggi imperativi
La principale abilità per il secondo obiettivo sarà sviluppare programmi in un linguaggio funzionale (Haskell) utilizzando le caratteristiche più salienti della programmazione funzionale, fra cui
- utilizzare e progettare funzioni di ordine superiore
- utilizzare la valutazione "lazy" degli argomenti per migliorare l'efficienza o per evitare casi di ciclo infinito
- utilizzare la monade dell'input/output Prerequisiti
- Conoscenza di linguaggi di programmazione imperativa e ad oggetti.
Automi a stati finiti Contenuti del corso
- Il corso fornisce una descrizione ragionata sul problema del riconoscimento dei linguaggi di programmazione, correlando la potenza espressiva dei linguaggi alle macchine necessarie per il riconoscimento.
Contenuti di dettaglio: Descrizione formale e implementazione dei linguaggi: grammatiche formali e loro proprietà, classificazione di Chomsky. Relazione fra grammatiche e automi riconoscitori. Analisi lessicale e tecniche di analisi sintattica top-down e bottom-up per linguaggi regolari e LL per context-free. Cenni sulla descrizione formale della semantica. Organizzazione e costruzione di interpreti e compilatori e relativi supporti a tempo di esecuzione.
Introduzione agli stili di programmazione non imperativi.
Programmazione funzionale e linguaggio Haskell. Tipi di dato e typeclasses in Haskell. Lambda expressions, Currying, funzioni di ordine superiore. Pattern-matching, list comprehensions. Valutazione eager e lazy degli argomenti. Tecniche di graph reduction per migliorare la valutazione lazy degli argomenti. Memory leaks in Haskell. La monade dell'Input/Output. Metodi didattici
- Il corso viene impartito seguendo il metodo didattico della "flipped classroom". Gli studenti avranno a disposizione videolezioni, a cui accedono in autonomia fuori dall'orario di lezione, fornite dal docente in anticipo rispetto a ciascuna lezione in aula o in laboratorio di informatica.
In aula o in laboratorio di informatica verranno discusse le videolezioni che gli studenti hanno seguito, gli studenti potranno richiedere delucidazioni sulle videolezioni e si svolgeranno esercizi, in maniera collegiale, singolarmente o a gruppi.
Nelle lezioni in laboratorio di informatica, oltre ad ottenere eventuali chiarimenti sulle videolezioni, gli studenti potranno sviluppare programmi nel linguaggio di programmazione funzionale Haskell, guidati dal docente. Modalità di verifica dell'apprendimento
- Al fine di verificare le conoscenze dello studente sulla parte di grammatiche, linguaggi e riconoscitori, viene fatta una prova scritta, in cui allo studente può venire chiesto di
- scrivere una grammatica relativa ad un semplice linguaggio
- classificare una grammatica secondo la gerarchia di Chomsky
- scrivere un automa riconoscitore LL per un linguaggio di tipo 2 (indipendente dal contesto)
- scrivere, data una grammatica regolare, una espressione regolare per descrivere lo stesso linguaggio o viceversa (passare da espressione regolare a grammatica).
Al fine di verificare la conoscenza della programmazione funzionale e del software di generazione semi-automatica di riconoscitori, viene fatta una prova di laboratorio, al calcolatore. In essa, lo studente dovrà scrivere un programma in linguaggio Haskell.
Le due prove si svolgono lo stesso giorno, ad esempio una la mattina e l'altra il pomeriggio.
Il voto finale è dato dalla somma dei voti delle prove.
Nelle prove, non è ammesso utilizzare materiale cartaceo, appunti, ecc. Nella prova di laboratorio, lo studente può accedere alla documentazione (accessibile in laboratorio) associata ai vari pacchetti software utilizzati.
L'esame può essere sostenuto in lingua Inglese, se richiesto con almeno una settimana di anticipo.
In caso non sia possibile svolgere l'esame in presenza, a causa di ordinanze per il distanziamento sociale, l'esame consisterà di
1. una tesina da svolgere in linguaggio Haskell. La tesina andrà concordata con il docente e tipicamente verte sulla parte di linguaggi e grammatiche.
2. una prova orale in cui viene richiesto di
a. presentare e discutere la tesina
b. svolgere esercizi
c. domande di teoria Testi di riferimento
- MATERIALE DI RIFERIMENTO:
- videolezioni fornite dal docente
- lucidi proiettati a lezione e resi disponibili sul sito web del corso
TESTI PER APPROFONDIMENTI SU TEORIA DEI LINGUAGGI E COMPILAZIONE
Maurizio Gabbrielli, Simone Martini. Linguaggi di programmazione - Principi e paradigmi. McGraw-Hill, 2001.
A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman. Compilatori: principi, tecniche e strumenti seconda edizione, Pearson/Addison-Welsley, 2009.
J. E. Hopcroft, R. Motwani, J. D. Ullman. Automi, Linguaggi e calcolabilita', terza edizione, Pearson/Addison-Wesley, 2009.
S. Crespi Reghizzi, L. Breveglieri, A. Morzenti. Linguaggi formali e compilazione. Società editrice Esculapio 2015.
TESTI PER APPROFONDIMENTI SUL LINGUAGGIO HASKELL
Graham Hutton. Programming in Haskell. Cambridge University Press, 2007
Bryan O'Sullivan, Don Stewart, and John Goerzen. Real World Haskell. O'Reilly Media, 2008.
Miran Lipovaca. Learn You a Haskell for Great Good!: A Beginner's Guide. 2011
