Ateneo - UPO

Linguaggi formali, grammatiche context free, automi riconoscitori, parsing LR. Traduzione guidata dalla sintassi e suo utilizzo per la traduzione dei linguaggi imperativi di programmazione.

Stefano Crespi Reghizzi “Sintassi, semantica e tecniche di compilazione Volume 1: Metodi Sintattici”, CLUP.
A. V. Aho, R. Sethi, J.D. Ullman: "Compilers Principles, Techniques and Tools", Addison-Wesley, 1986 oppure A. V. Aho, M.S. Lam, R. Sethi, J.D. Ullman: "Compilers Principles, Techniques and Tools", 2a edizione, Addison-Wesley, 2006

Le seguenti conoscenze e capacita':
• modellare linguaggi regolari e linguaggi context free (tramite espressioni regolari, e grammatiche context free, eventualmente lineari)
• riconoscere linguaggi regolari e context free mediante automi (a stati finiti e a pila)
• conoscere il parsing LR(0) ed SLR(1), sviluppare parser LR(0) e SLR(1) a partire da grammatiche context-free,
• conoscere i metodi per la traduzione diretta dalla sintassi e le condizioni per la loro applicazione: durante l’analisi LR, come attraversamento dell'albero di derivazione, del grafo delle dipendenze
• conoscere come la traduzione diretta dalla sintassi viene applicata alla traduzione dei linguaggi di programmazione per la traduzione di espressioni numeriche, istruzioni di controllo ed espressioni booleane

Nozioni di base acquisite nei corsi di programmazione dei primi due anni.

Lezioni frontali in aula, esercitazioni.

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.

Esame scritto (orale facoltativo). Contiene sia esercizi pratici che domande teoriche su diversi argomenti trattati nel corso. La valutazione è stabilita collegialmente dai docenti. La valutazione misura la proporzione di raggiungimento dei diversi risultati di apprendimento attesi.

- Linguaggi ed espressioni regolari
- Linguaggi e grammatiche context free
- Grammatiche lineari, e loro relazioni con i linguaggi regolari
- 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) e SLR(1)).
- Traduzione guidata dalla sintassi: grammatiche ad attributi e schemi di traduzione. .
- Generazione del codice intermedio

Conoscenza e capacità di comprensione:
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) e SLR(1)
Conoscere i metodi per la traduzione diretta dalla sintassi durante l’analisi LR, come attraversamento dell'albero di derivazione e mediante il grafo delle dipendenze, e le condizioni per la loro applicazione.

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. Applicazione della traduzione diretta dalla sintassi alla traduzione dei linguaggi di programmazione.

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. Riconoscere le condizioni per poter applicare la traduzione diretta dalla sintassi durante l’analisi LR.

Abilita, comunicative:
acquisire ed utilizzare la terminologia rigorosa utilizzata nell'ambito della teoria dei linguaggi

Capacita' di apprendere:
capacita' di riconoscere classi di problemi e di affrontarle con le metodologie appropriate per le classi stesse. Inoltre, una generale capacita' di modellazione ed analisi formale dei problemi.