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 di espressioni.

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.

Gli studenti devono aver 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.

Parte 2.
Per le lezioni in laboratorio gli studenti sono invitati a sottoporre settimanalmente le parti sviluppate (in parte in laboratorio e in parte autonomamente). Gli elaborati degli studenti vengono commentate in aula.

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.
Compito scritto consistente di un esercizio e tre domande aperte.
Presentazione del progetto con discussione orale delle scelte effettuate ed eventuali richieste di piccole modifiche.
Il voto della Parte 2 sara' la media pesata del giudizio sul progetto e nel compito scritto.

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 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 devono acquisire ed utilizzare la terminologia rigorosa utilizzata nell'ambito della teoria dei linguaggi

Capacita' di apprendere:
Gli studenti 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 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 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 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 deve essere in grado di esporre e motivare anche le proprie scelte.