Ateneo - UPO

Parte 1 (6 crediti) Linguaggi formali, grammatiche context free, automi riconoscitori, parsing LR. Parte 2 (3 crediti) Sviluppo di un compilatore top-down a discesa ricorsiva per un linguaggio imperativo con dichiarazione di tipo.

Parte 1
S. Crespi Reghizzi , L. Breveglieri, A. Morzenti, Linguaggi formali e compilazione, Esculapio.
Parte 2
Charles N. Fischer, Ron K. Cytron, Richard J. Le Blanch Jr., "Crafting a compiler", Addison-Wesley.

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 teorici e quelli pratici. Per la parte teorica l'obiettivo e' di capire le relazioni fra linguaggi e automi e l’espressivita’ della classe dei linguaggi regolari e liberi da contesto. Per la parte pratica l'obiettivo, attraverso l'implementazione di un compilatore, e' di applicare le nozioni teoriche introdotte ed inoltre imparare come si struttura un sistema complesso in fasi successive individuando le strutture dati e le funzioni che costituiscono le interfacce fra le varie fasi.

Conoscenze dei contenuti di Programmazione 1 e 2; Programmazione ad Oggetti; Algoritmi 1.

Parte 1
Lezioni frontali in aula, esercitazioni.
Parte 2.
lezioni iniziali (teoriche) per circa 5 lezioni. Lezioni in laboratorio per lo sviluppo del compilatore.

Per le lezioni in laboratorio gli studenti/le studentesse sono invitati a sottoporre settimanalmente le parti sviluppate (in parte in laboratorio e in parte autonomamente). Gli elaborati degli studenti/delle studentesse vengono commentate in aula.
Le studentesse e gli studenti con disabilità o con Disturbi Specifici dell’Apprendimento (DSA) o con Bisogni Educativi Speciali (BES) possono richiedere servizi e strumenti specifici a loro dedicati rivolgendosi allo Staff "Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti" e consultando la pagina dedicata del sito di Ateneo: https://uniupo.it/it/servizi/servizi-studenti-disabili-e-dsa
Le studentesse e gli studenti con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo, possono contattare la/il docente titolare dell'insegnamento in relazione alla declinazione delle modalità di esame, in merito agli aspetti didattici.

La valutazione finale viene stabilita collegialmente dai docenti del corso tenendo conto delle conoscenze e competenze acquisite dalla studentessa/dallo studente verificate attraverso lo svolgimento delle due parti dell'esame dettagliate nel seguito: su entrambe le componenti occorre superare una soglia minima.

Parte 1 Esame scritto:7-8 domande, che posso essere sia esercizi pratici sia domande teoriche sugli automi riconoscitori e sulle tipologie di linguaggi mostrate a lezione

Parte 2.
L'esame consiste di una prova scritta e della presentazione del compilatore sviluppato con relativa discussione orale.
Il compito scritto contiene un esercizio in cui si chiedere di determinare se una grammatica e' LL(1) e di fare qualche derivazione di stringhe del linguaggio e tre domande aperte sulla teoria dei linguaggi formali relativa allo sviluppo di compilatori. Per raggiungere la sufficienza lo studente deve dimostrare di aver svolto con errori trascurabili l'esercizio.
Il compilatore deve essere presentato per accedere alla prova scritta. La discussione orale viene fatta assieme alla presentazione del risultato della prova scritta. La votazione sul progetto dipende dalla sua correttezza e dallo stile di programmazione adottato.
Il voto della Parte 2 è la media della votazione sul progetto e di quella del compito scritto.

Nella valutazione finale il voto della Parte 1 pesa per i 2/3 quella della Parte 2 per 1/3 in coerenza con il numero di CFU erogati per le due parti.

Parte 1
- Linguaggi ed espressioni regolari
- Linguaggi e grammatiche context free
- Grammatiche lineari, e loro relazioni con i linguaggi regolari
- grammatiche attributi
- Grammatiche context sensitive (cenni)
- Principali strutture sintattiche e regole grammaticali per generale
- Automi a stati finite e loro relazione con i linguaggi regolari
- Automi a pila (deterministici e non) e loro relazioni con i linguaggi context free
- Principi del parsing bottom up, focalizzandosi sul parsing LR (LR(0)).

Parte 2.
- Introduzione ai compilatori.
- Strutturazione dei compilatori
- Analisi lessicale: tokens e loro produzione
- Analisi sintattica: parsing top-down a discesa ricorsiva
- Albero sintattico astratto e Symbol table.
- Pattern visitor per l’analisi di tipo e la generazione del codice

Parte 1
Conoscenza e capacità di comprensione:
gli studenti/le studentesse devono conoscere e comprendere le seguenti nozioni di base:
linguaggi regolari, espressioni regolari, grammatiche lineari, automi a stati finiti (deterministici e non)
linguaggi context free, grammatiche context free, automi a pila (deterministici e non)
parser LR(0)

Capacita' di applicare conoscenza:
modellare linguaggi regolari tramite espressioni regolari
modellare linguaggi regolari tramite grammatiche lineari
modellare linguaggi mediante grammatiche context free, utilizzando la metodologia "divide et impera" nello sviluppo delle grammatiche
sviluppare automi a pila non deterministici a partire da grammatiche context-free
sviluppare automi a pila deterministici per riconoscere linguaggi context-free deterministici
sviluppare parser LR(0) e SLR(1) a partire da grammatiche context-free

Autonomia di giudizio:
riconoscere linguaggi regolari rispetto ai linguaggi context free
conoscere la relazioni fra classi di linguaggi, classi di grammatiche, e classi di automi riconoscitori
selezionare i costrutti appropriati per la definizione di grammatiche context-free a partire da un linguaggio

Abilita, comunicative:
Gli studenti/Le studentesse devono acquisire ed utilizzare la terminologia rigorosa utilizzata nell'ambito della teoria dei linguaggi

Capacita' di apprendere:
Gli studenti/le studentesse devono aver acquisito le capacita' di riconoscere classi di problemi e di affrontarle con le metodologie appropriate per le classi stesse. Devono inoltre aver acquisito una generale capacita' di modellazione ed analisi formale dei problemi.

Parte 2.
Conoscenza e capacità di comprensione: lo studente/la studentessa deve acquisire familiarita’ con la trasformazione di concetti formali (quali automi e grammatiche) in strumenti per la traduzione diretta da sintassi dei linguaggi.

Capacità di applicare conoscenza e comprensione: lo studente/la studentessa deve saper progettare ed implementare una traduzione diretta da sintassi di un semplice linguaggio, essendo in grado di progettare le strutture dati necessarie e strutturando in modo modulare il codice.

Autonomia di giudizio: lo studente/la studentessa deve essere in grado di riconoscere l’appropriatezza dell’uso di diversi tipi di analizzatori sintattici evidenziandone i vantaggi e gli svantaggi.

Abilità comunicative: lo studente/la studentessa deve essere in grado di esporre e motivare anche le proprie scelte.