corso

Compilatori

Codice:	AA026	Crediti:	6	Semestre:	2	Sigla:	COP

Settore disciplinare:		INF/01 - Informatica

Docenti

Andrea Maggiolo Schettini

Tel. 0502212700
Marco Bellia

Tel. 0502212781

Prerequisiti

1 modulo: Fondamenti di programmazione.
2 modulo: Fondamenti di programmazione, Algoritmica e laboratori I e II.

Obiettivi di apprendimento

1 modulo: La conoscenza dei concetti della teoria degli automi e dei linguaggi formali di base e il loro utilizzo per la compilazione dei linguaggi di programmazione.
2 modulo: Introdurre le principali problematiche inerenti la realizzazione di traduttori e interpreti per linguaggi di programmazione. Introdurre le tecniche e gli strumenti per analisi statica, traduzione, generazione e interpretazione di codice.

Descrizione

1 modulo:La teoria degli automi e dei linguaggi formali è alla base della descrizione dei linguaggi di programmazione, della costruzione dei loro riconoscitori e traduttori, della realizzazione di strumenti di elaborazione testuale. Il corso esporrà la teoria degli automi finiti e dei linguaggi non contestuali e descriverà algoritmi e strutture dati per l’analisi lessicale e l’analisi sintattica dei programmi.
2 modulo:Si introducono tecniche basate su grammatiche ad attributi e su syntax-directed definitions per costruire analizzatori semantici e traduttori guidati dalla sintassi. Queste tecniche sono utilizzate in contesti differenti e nella costruzione di strumenti quali riconoscitori di linguaggi non context-free, esecutori di linguaggi non-standard, editor guidati dalla sintassi, sistemi per la composizione grafica di testi e immagini.

English Description

1 modulo: The theory of automata and formal languages is at the basis of the description of programming languages, of the construction of parsers and translators, of the realization of text-processing tools. The course will expound the theory of finite automata and of context-free languages, and will describe algorithms and data structures for lexical and syntactical analysis of programs.
2 modulo:The second module is centered on the techniques for syntax directed translation, static properties of programming languages, and for code generation. These techniques are used in several contexts and in the construction of many different tools, for instance: context-free recognizers, non-standard languages executors, programming environmemts and syntax-directed editors,systems for the graphical composition of texts and images.

Programma

1 modulo (3 cfu) - prof. A.Maggiolo-Schettini:

Automi a stati finiti. Espressioni regolari. Proprietà degli insiemi regolari. Analisi lessicale. (6 ore)

Grammatiche non contestuali. Automi a pila. Proprietà dei linguaggi non-contestuali. (6 ore)

Grammatiche LLK e LRK. Analizzatori sintattici ascendenti e discendenti. (8 ore)

Generatori di analizzatori lessicali e sintattici. (4 ore)

Pagina web: http://www.di.unipi.it/~maggiolo/lucidi-COP.html

2 modulo (3 cfu) - prof. M. Bellia:

Attributi, grammatiche L-attributate, esecutori top-down e bottom-up, rappesentazioni di programmi (ore 6)

Analisi statica: proprietà statiche di programmi, sistemi di tipi e controllo di tipi (ore 6)

Macchine astratte: supporto run time, memoria statica e dinamica, tabella dei simboli (ore 4)

Generazione di codice: linguaggi intermedi, traduzione di espressioni, controllo di sequenza, astrazioni procedurali (8 ore)

Pagina web: http://www.di.unipi.it/~bellia

Bibliografia
1 modulo:

Hopcroft, J.E., Ullman J.D., Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Reading, Mass., 1979.

Hopcroft, J.E., Motwani, R., Ullman, J.D., Automi, linguaggi e calcolabilità, Addison Wesley, Pearson Education Italia, 2003.

Salomaa, A., Formal Languages, Academic Press, New York, 1987.

Aho A.V., Sethi R., Ullman J.D., Compilers: Principles,Techniques and Tools, Addison-Wesley, Reading, Mass., 1988.

2 modulo:
Aho A.V., Sethi R. , Ullman J.D., Compilers. Principles, Techniques and Tools, Addison Wesley, Reading, Mass., 1986.

Wilhelm R. and Maurer D., Compiler Design, Addison-Wesley, 1996.