La generación de código para expresiones

4o Ingenier´ıa Inform´atica

II26 Procesadores de lenguaje

Generaci´on de c´odigo

Esquema del tema

1. Introducci´on

2. C´odigo intermedio

3. Generaci´on de c´odigo para expresiones

4. Generaci´on de c´odigo para las estructuras de control

5. Generaci´on de c´odigo m´aquina

6. Resumen

1. Introducci´on

Una vez ha terminado el an´alisis y se ha obtenido un AST decorado, comienza la generaci´on

de c´odigo. Esta fase suele dividirse en dos partes:

Generaci´on de c´odigo intermedio.

Generaci´on de c´odigo de m´aquina.

El primero es c´odigo para una m´aquina virtual. Estas m´aquinas se definen con dos objetivos:

Ser lo suficientemente simples como para poder generar c´odigo para ellas de manera sencilla,

pero con la suficiente riqueza para poder expresar las construcciones del lenguaje fuente.

Estar lo suficientemente pr´oximas a los procesadores reales para que el paso del c´odigo

intermedio al c´odigo de m´aquina sea pr´acticamente directo.

Para conseguirlo, las m´aquinas virtuales tienen una serie de caracter´ısticas simplificadoras. Por

ejemplo:

Tienen pocos modos de direccionamiento.

Pueden tener un n´umero ilimitado de registros (que pueden estar organizados en forma de

pila).

Tienen un juego de instrucciones relativamente simple.

En principio, el c´odigo intermedio es independiente del lenguaje de programaci´on fuente. En la

pr´actica, es habitual que se definan c´odigos intermedios que faciliten la representaci´on de deter-

minadas caracter´ısticas del lenguaje fuente. As´ı, el P-code est´a pensado para traducir Pascal y el

Java-bytecode es muy bueno para el Java.

Otra de las ventajas del c´odigo intermedio es que facilita la escritura de compiladores para

distintas m´aquinas. La traducci´on del lenguaje a c´odigo intermedio ser´ıa id´entica en todas y lo

unico que cambiar´ıa ser´ıa el traductor de c´odigo intermedio a c´odigo de m´aquina. Esta idea de

independencia del c´odigo intermedio de la m´aquina puede llevarse un paso m´as all´a, como se hace

en diversos lenguajes, de los cuales Java es quiz´a el m´as representativo. La idea es compilar el

lenguaje a un c´odigo intermedio que despu´es es interpretado. De esta manera, un mismo “binario”

puede ejecutarse en m´aquinas con arquitecturas y sistemas operativos totalmente distintos.

Una vez generado el c´odigo intermedio, se traduce ´este a c´odigo de m´aquina. La traducci´on

tiene que hacerse de manera que se aprovechen adecuadamente los recursos de la m´aquina real.

2 II26 Procesadores de lenguaje

Aunque en principio estas dos fases bastan para la generaci´on del c´odigo final, en la pr´actica

est´an mezcladas con fases de optimizaci´on. Es habitual tener entonces un esquema similar al que

vimos en el primer tema:

Programa fuente

An´alisis

An´alisis

l´exico

´

An´alisis

sint´actico

An´alisis

sem´antico

S´ıntesis

Generaci´on de

c´odigo intermedio

Optimizaci´on de

c´odigo intermedio

Generaci´on de

c´odigo objeto

Optimizaci´on de

c´odigo objeto

Programa objeto

Podr´ıamos entonces decir que la generaci´on de c´odigo tiene como objetivo generar el ejecutable

que despu´es emplear´a el usuario. Sin embargo, es habitual que el producto del compilador no

sea directamente un fichero ejecutable. Es bastante m´as com´un que sea un fichero en lenguaje

ensamblador. De esta manera, se evitan problemas como tener que medir el tamano exacto de las

instrucciones o llevar la cuenta de sus direcciones. Adem´as, es muy probable que el c´odigo generado

tenga referencias a objetos externos como funciones de biblioteca. Estas referencias externas ser´an

resueltas por el enlazador o el cargador.

1.1. Lo m´as f´acil: no generar c´odigo

Dado que la generaci´on de c´odigo es una tarea compleja, especialmente si queremos que sea

eficiente y razonablemente compacto, es interesante buscar maneras de evitar esta fase. De hecho

existe una manera sencilla de evitar la generaci´on de c´odigo (al menos, la generaci´on de c´odigo

m´aquina) que permite obtener ejecutables de muy buena calidad: generar c´odigo en otro lenguaje

para el que haya un buen compilador.

Hoy en d´ıa, pr´acticamente cualquier sistema tiene compiladores de C de gran calidad. Es

posible, por tanto, traducir nuestro lenguaje a C y despu´es compilar el programa obtenido con un

buen compilador. Esto tiene varias ventajas:

El tiempo de desarrollo de nuestro compilador se reduce considerablemente.

En muchos sistemas, el compilador de C genera c´odigo de muy alta calidad ya que de ´el

dependen muchos programas cr´ıticos (entre ellos el propio sistema operativo).

Nos permite tener un compilador para gran n´umero de m´aquinas con un esfuerzo m´ınimo

(el de adaptarse a las pequenas diferencias entre unos compiladores y otros). De hecho,

en algunos casos se habla del lenguaje C como de un “ensamblador independiente de la

m´aquina”.

En el caso de lenguajes de muy alto nivel o de paradigmas como el funcional y el l´ogico, esta es

pr´acticamente la elecci´on un´anime. Hay incluso propuestas de lenguajes como el C--, que buscan

un lenguaje reducido y con ciertas caracter´ısticas de m´as bajo nivel como lenguaje destino para

muchos compiladores.

Si hemos construido el ´arbol mediante clases, la traducci´on a C es pr´acticamente trivial para

muchas de las construcciones habituales en los lenguajes imperativos. Por ejemplo, para los nodos

Generaci´on de c´odigo 3

correspondientes a las expresiones aritm´eticas, podemos utilizar algo parecido a:

Objeto NodoSuma:

...

M´etodo traduceaC()

devuelve (i.traduceaC()+ "+" +d.traduceaC());

fin traduceaC

...

fin NodoSuma

donde i y d son los hijos izquierdo y derecho, respectivamente.

Igual que vimos en el tema de an´alisis sem´antico, tanto en este caso como en los que comentemos

despu´es, no es necesario que utilicemos una clase por cada tipo de nodo. Tampoco es necesario

que utilicemos objetos y m´etodos: podemos recorrer el ´arbol con ayuda de una pila o de funciones

recursivas adecuadas.

2. C´odigo intermedio

Existen diversos tipos de c´odigos intermedios que var´ıan en cuanto a su sencillez, lo pr´oximos

que est´an a las m´aquinas reales y lo f´acil que es trabajar con ellos. Nosotros nos centraremos en

un tipo de c´odigo que se parece bastante al lenguaje ensamblador. Existen otros tipos de c´odigo

intermedio que representan los programas como ´arboles o grafos. Tambi´en existen representaciones

mixtas que combinan grafos o ´arboles y representaciones lineales.

El formato que usaremos para las operaciones binarias es:

r1:= r2 op r3

donde

r1, r2 y r3 son registros, de los que tenemos un n´umero infinito,

op es un operador.

En caso de que el operador sea unario, la forma de la instrucci´on es r1:= op r2. Para acceder a

memoria utilizaremos asignaciones entre registros y memoria. Las asignaciones pueden ser directas

de la forma r1:=&d o &d:= r2 y tambi´en relativas a un registro como en r1:= &r2[d] y en

&r1[d]:= r2.

Por ejemplo, la sentencia a:= b*(-c), donde a es una variable local en la direcci´on 1 respecto

al FP y b y c son variables globales en las direcciones 1000 y 1001, se puede traducir como:

r1:= &1000

r2:= &1001

r3:= - r2

r4:= r1 * r3

&FP[1]:= r4

Uno de los objetivos que suele perseguirse es reducir al m´ınimo el n´umero de registros utilizados.

En nuestro caso, podemos emplear dos:

r1:= &1000

r2:= &1001

r2:= - r2

r1:= r1 * r2

&FP[1]:= r1

c Universitat Jaume I 2006-2007

4 II26 Procesadores de lenguaje

Si las variables estuvieran en los registros1 r1, r2 y r3, podr´ıamos incluso no utilizar ning´un

registro auxiliar:

r1:= - r3

r1:= r2 * r1

Tambi´en tendremos instrucciones para controlar el flujo de ejecuci´on, para gestionar entra-

da/salida, etc. A lo largo del tema iremos viendo esas instrucciones seg´un las vayamos necesitando.

3. Generaci´on de c´odigo para expresiones

Comenzaremos por estudiar c´omo generar c´odigo para las expresiones. Asumiremos que para

gestionar el c´odigo disponemos de una funci´on auxiliar, emite. Esta funci´on recibe una cadena

...