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

Gli studenti devono aver acquisito 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 il metodo per la traduzione diretta dalla sintassi durante l’analisi LR, e l’esistenza di altri metodi.

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

Lezioni frontali in aula, esercitazioni.

Esame scritto (orale facoltativo). Contiene sia esercizi pratici che domande teoriche.

- 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:
gli studenti devono conoscere ee 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 in dettaglio il metodo per la traduzione diretta dalla sintassi durante l’analisi LR, e l’esistenza di altri metodi.

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:
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.