Compiladors II (CL2)
(http://www.lsi.upc.edu/~nivela)
| Professors Responsables: |
M. PILAR NIVELA ALOS (nivela lsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 0.0 P 1.5 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Obligatoria de segon cicle per la EI
Optativa per la ETIG , ETIS
Requisits de l'assignatura
|
CL1
- Pre-correquisit per la EI , ETIG , ETIS
|
|
Objectius docents
Estudiar la fase de sintesi d'un compilador e implementar un
compilador per un llenguatge, anomenat CL, de la familia
Pascal/Modula-2
Programa
1. Introducció:
- Estructura conceptual i real d'un compilador. Fase de síntesi:
assignació de memòria, generació de codi, optimització
- El llenguatge font CL
- La Q-machine: estructura de la memòria, joc d'instruccions
2. Presentació de les eines ja implementades que s'utilitzen a l'assignatura:
- L'especificació lèxica i sintàctica pel llenguatge CL
- La taula de símbols: estructura i operacions
- La comprovació de tipus pel llenguatge CL: atributs sintetitzats i atributs heretats
- L'intèrpret de la Q-machine
3. Assignació de memòria:
- Assignació estàtica i dinàmica
- Assignació dinàmica en pila
- Estructura dels blocs d'activació per la Q-machine
- Accés a noms no locals per àmbit estàtic: cadenes estàtiques i displays
- Accés a noms no locals per àmbit dinàmic: cadenes dinàmiques
- Assignació de memòria per arrays estàtics. Assignació per arrays dinàmics: descriptors d'arrays
- Implementació del pas de procediments com a paràmetres d'altres procediments: descriptors de procediments
- Assignació dinàmica en heap: estratègies d'assignació (best-fit, first-fit i circular first-fit); estratègies de desassignació: explícita i implícita (referències úniques, comptadors de referències, garbage collection)
- Implementació de punters dinàmics
4. Generació de codi intermedi:
- Tipus de codi intermedi.
- Compilació de les construccions clàssiques dels llenguatges:
procediments i funcions, expressions, instrucció d'asignació, conversions implícites, accés a components d'arrays estàtics i dinàmics, instruccions iteratives,
condicional, lectura, escriptura, crida a procediments i funcions,
compilació eficient d'expressions booleanes, formal procedures.
5. Optimització de codi:
- Criteris d'optimització, fonts d'optimització, optimitzacions locals i globals.
- Optimitzacions locals: blocs bàsics i grafs de flux, simplificació d'expressions, precàlcul de constants, propagació de còpies, representació amb grafs dirigits acíclics dels blocs bàsics: eliminació de subexpressions comunes, eliminació de codi inactiu.
- Optimitzacions globals. Detecció de bucles: dominadors, grafs de flux reduibles. Optimització de bucles: detecció d'invariants i trasllat de codi, detecció de variables d'inducció i reducció d'intensitat. Anàlisi de flux de dades: ud-chaining, expressions disponibles, propagació de còpies, du-chaining, variables actives, expressions very-busy
6. Generació de codi objecte:
- Problemes de generació de codi objecte: generació d'instruccions, ordre de càlcul, ús de registres, adreces de les variables, tractament de les etiquetes.
- Un model de màquina objecte. Informació next-use, descriptors de registres, descriptors d'adreces. Un algorisme de generació de codi
- Optimitzacions: peephole, codi inaccessible, salts múltiples
Avaluació
Avaluació de la pràctica.
L'avaluació del treball pràctico a CL1 i CL2 es basarà
exclusivament en la realització d'un examen escrit.
Avaluació de l'assignatura.
La nota final F de l'assignatura es calcularà en funció dels
exàmens de la práctica P i de teoria T tal com segueix:
Sigui min=mínim(T,P).
If min>5 Then F:=(2T+P)/3 Else F:=(min/5)*(2T+P)/3.
Càrrega
Els 4.5 crèdits de l'assignatura es descomposen en 3 de teoria i 1.5
de laboratori, el que permet organitzar l'assignatura en dues hores
setmanals de classes teòriques i una hora setmanal de laboratori (per raons
d'aprofitament les hores de laboratori s'agrupen en blocs de dues hores
quinzenals).
A les classes de laboratori es fa un seguiment del desenvolupament
del treball pràctic de l'assignatura que consisteix en l'elaboració
d'un compilador pel llenguatge font CL.
La sortida d'aquest compialdor es un programa escrit en el llenguatge Q
(que és el codi executat per la Q-machine, una variació de la
P-machine utilitzada tradicionalment en les implementacions de Pascal).
Per tal de facilitar l'implementació del compilador l'estudiant té
al seu abast una implementació completa de l'anàlisi lèxic,
sintàctic i semàntic, a més d'un simulador (o intèrpret) de la Q-machine.
La reatlització d'aquest treball pràctic es individual i la seva
presentació requereix el funcionament correcte del compilador. Els
estudiants disposen d'uns jocs de prova públics per provar-lo.
Donat que a l'assignatura no hi ha classes de problemes es recomana a
l'estudiant la resolució de la llista de problemes de que disposa
cada quatrimestre.
Bibliografia
Bibliografia bàsica
- AHO, A.V.; ULLMAN, J.D Principles of Compiler Design Addison-Wesley, 1987
- FISHER, C.N.; LeBLANC Jr., R.J Crafting a Compiler The Benjamin Cummings Publ. Comp, 1988
- WILHELM, R.; MAURER, D. Compiler Design Addison-Wesley P. C. , 1995
- A. W. Appel Modern Compiler Implementation in C Cambridge University Press, 1998
Bibliografia complementària
- SCHREINER, A.T., FRIEDMAN Jr., H.G Introduction to
Compiler Construction whit UNIX Prentice-Hall Inc. Englewook Cliffs, 1985
- WAITE, T., GOOS, G Compiler Construction Springer Verlag, 1984
- AHO, A.V., SETHI, R., ULLMAN, J. D. Compiladores, Principios, Tecnicas y Herramientas Addison Wesley Iberoamericana, 1990
|
