miércoles, 18 de mayo de 2011

UNIDAD 8 GENERACION DE CODIGO INTERMEDIO



GENERACIÓN DE CÓDIGO INTERMEDIO

INTRODUCCION
Esta fase del compilador no es en realidad una parte separada del compilador, la mayoría de los compiladores generan código como parte del proceso de análisis sintáctico, esto es debido a que requieren del árbol de sintaxis y si este no va a ser construido físicamente, entonces deberá acompañar al analizador sintáctico al barrer el árbol implícito. En lugar de generar código ensamblador directamente, los compiladores generan un código intermedio que es más parecido al código ensamblador, las operaciones por ejemplo nunca se hacen con más de dos operandos. Al no generarse código ensamblador el cual es dependiente de la computadora especifica, sino código intermedio, se puede reutilizar la parte del compilador que genera código intermedio en otro compilador para una computadora con diferente procesador cambiando solamente el generador de código ensamblador al cual llamamos back-end, la desventaja obviamente es la lentitud que esto conlleva.

La tarea de síntesis suele comenzar generando un código intermedio. El código intermedio no es el lenguaje de programación de ninguna máquina real, sino que corresponde a una máquina abstracta, que se debe de definir lo más general posible, de forma que sea posible traducir este código intermedio a cualquier máquina real. El objetivo del código intermedio es reducir el número de programas necesarios para construir traductores, y permitir más fácilmente la transportabilidad de unas máquinas a otras. Supóngase que se tienen n lenguajes, y se desea construir traductores entre ellos. Sería necesario construir n*(n-1) traductores.

Sin embargo si se construye un lenguaje intermedio, tan sólo son necesarios 2*n traductores.
Así por ejemplo un fabricante de compiladores puede construir un compilador para diferentes máquinas objeto con tan sólo cambiar las dos últimas fases de la tarea de síntesis.

Aunque un programa fuente se puede traducir directa mente al lenguaje objeto, algunas ventajas de utilizar una forma intermedia independiente de la máquina son:
       Se facilita la redestinación; se puede crear un compilador para una máquina distinta uniendo una etapa final para la nueva máquina a una etapa inicial ya existente.

          Se puede aplicar a la representación intermedia un optimizador de código independiente de la máquina.
 
Lenguajes intermedios
Los árboles sintácticos y la notación postfija son dos clases de representaciones intermedias. 
El código intermedio es un código abstracto independiente de la máquina para la que se generará el código objeto. El código intermedio ha de cumplir dos requisitos importantes: ser fácil de producir a partir del análisis sintáctico, y ser fácil de traducir al lenguaje objeto. 
Control de flujo
En los lenguajes de programación hay estructuras y operadores que permiten controlar el flujo de la ejecución, estos pueden ser ciclos, saltos, condiciones entre otros.
Expresiones booleanas
En los lenguajes de programación, las expresiones booleanas tienen dos propósitos principales.  Se utilizan para calcular valores lógicos y como expresiones condicionales en proposiciones que alteran el flujo del control, como las proposiciones if-else o  do-while.

Las expresiones booleanas se componen de los operadores boleanos (and, or y not) aplicados a los elementos que son variables booleanas o expresiones relacionales.  Algunos lenguajes permiten expresiones más generales donde se pueden aplicar operadores booleanos, aritméticos y relacionales a expresiones de cualquier tipo, sin diferenciar valores booleanos de aritméticos; si es necesario se realiza una coerción. 
 Saltos
En el código de los saltos los operadores lógicos &&, || y ! son traducidos a saltos aunque estos no aparecen realmente en el código. Por ejemplo la expresión: if (x < 100 || x > 200 && x!= y ) x=0; se puede traducir como las siguientes instrucciones:

If x < 100 goto L2
If False x > 200 goto L1
If False x != y goto L1
L2: x =0
L1:
Si la expresión es verdadera se alcanza la etiqueta L2 y se realiza la asignación en caso contrario no haría nada.
Backpatching
Cuando se genera un código con saltos condicionales y expresiones booleanas se enfrenta un problema muy común, en la expresión if (B) S debemos establecer el salto hacia S cuando se da B, el problema es que no siempre se conoce B a la hora de hacer esta transformación.
 
Backpatching es un enfoque donde al momento de generar un salto el objetivo de este salto se deja temporalmente indefinido. Cada salto es almacenado en una lista de saltos donde las etiquetas de sus destinos son establecidas en el momento en que ya pueden ser determinadas.
 
La manipulación de la lista de etiquetas se realiza con los métodos:
  •                 makelist(i) crea una nueva lista que contiene solo a i,un índice en el vector de instrucciones y además el método makelist retorna un puntero a la lista creada.
  •            merge(pl , p2 ) concatena las listas apuntadas por pl y p2 , y retorna el puntero a la nueva lista.
  •        backpatch(p, i) inseta i como la etiqueta objetivo para cada instruccion en la lista apuntada por p.
  •   

Expresiones
Pueden ser de tipo entero, real, matriz , registros. En la Tabla de Símbolos se puede buscar los nombres de las expresiones y se puede acceder a los elementos de matrices y registros.
Estos nombres representan a las expresiones dentro de la Tabla de Símbolos.
Tipos y Declaraciones
Conforme se examina la secuencia de declaraciones dentro de un procedimiento o un bloque, se puede distribuir la memoria para los nombres locales al procedimiento.  Para cada nombre local se crea una entrada en la tabla de símbolos con información, por ejemplo, referente al tipo y la dirección relativa de la memoria correspondiente al nombre.

La sintaxis de lenguajes como C, Pascal y FORTRAN permite que todas las declaraciones en un solo procedimiento se procesen como un grupo.  
Las expresiones de tipo son las estructuras de tipos que definen un programa, pueden ser de tipos básicos (booleano, char, integer, float, void) o formados por una estructura de tipos básicos creada por operadores de constructores de tipo.
 
Una forma conveniente de representar una expresión de tipo es usando un grafo. Los nodos interiores se usaran para constructores de tipo y las hojas se usaran para los tipos básico. Cuando las expresiones de tipos están representadas por grafos se pueden comparar para ver si son de tipos equivalentes. Dos tipos son estructuralmente equivalentes si:
  •                  Son el mismo tipo básico 
  •                  Son formados utilizando el mismo constructor con los mismos tipos básicos 
  •              Uno es un tipo que denota otro
Dado un tipo de una variable, se puede calcular la cantidad de almacenamiento que se necesitara para la variable en tiempo de ejecución. El tipo y la dirección relativa se guardaran en la tabla de símbolos para cada variable. Para los tipos de dimensión variable, tales como hileras de caracteres o vectores dinámicos, se les asignara una cantidad de almacenamiento para un puntero al tipo.
 
Parte importante de la generación de código de un compilador es la verificación de tipos. Se debe verificar que el programa siga las reglas de tipos especificados por el programa, una implementación que se base en estas reglas encontrará errores en las modificaciones al compilar. 
Verificación de tipos
 La verificación de tipos es una técnica utilizada para asegurar que un programa obedece las reglas de compatibilidad específicas del lenguaje de programación utilizado. La verificación se puede realizar de dos formas: en tiempo de ejecución o de manera estática.
 
Para que un compilador pueda realizar el chequeo se debe asignar una expresión de tipo que
identifique cada componente del lenguaje fuente. Con estas definiciones de tipos se pueden formular reglas lógicas que son llamadas: sistema de tipos, el cuál define como un lenguaje de programación clasifica sus elementos en tipos y determina reglas de relación y comportamiento entre estos tipos. Una violación a alguna regla es llamada choque de tipos.
 Tipos de chequeo
 La verificación de datos se puede realizar de dos maneras: por medio de síntesis y con el método de la inferencia.
 
El método de la síntesis consiste en derivar el tipo de una expresión basándose en los tipos de sus subexpresiones. En la síntesis se requiere que los tipos estén declarados antes de ser utilizados y deben poseer un nombre que los identifique.
 
La inferencia de tipos se basa en determinar el tipo de una expresión o elemento según la manera en que sea utilizado, es decir si tenemos una función f(x) donde se supone que x sea de un tipo Y, tendremos que cada vez que se aplique F () sobre algún elemento este elemento será de tipo Y.
Conversión de tipos 
 
Algunos tipos diferentes de datos son tratados de forma diferente por el computador, sin embargo es necesario poder operar entre ellos, por lo que los lenguajes de programación implementan la conversión de tipos, que se basa en cambiar el tipo de una expresión por otro.
 
Por ejemplo si deseamos multiplicar un numero entero y uno flotante, el compilador debe unificar los tipos ya que el almacenamiento y manejo de la maquina es diferente para estos 2 tipos. Lo que el compilador hacer es convertir el entero a flotante.
Sobrecarga de funciones y operadores
La sobrecarga de operadores es utilizada cuando necesitamos realizar varias funciones con el mismo símbolo o función. El operador se trata dependiendo del contexto donde se encuentre.
 
Por ejemplo el operador “+” en Java puede ser utilizado para concatenar una hilera o para sumar numerales. “Las funciones definidas por el usuario se pueden sobrecargar como se muestra a continuación:
 
           void err () {…}
void err(String s) {…}
 
La escogencia de una de estas dos funciones se realiza tomando en cuenta su número y tipo de
argumentos.”.

Funciones polimórficas
Las funciones normales permiten ser ejecutadas con argumentos de tipos fijos, una función polimórfica acepta parámetros de tipos variables. El término polimórfico aplica también a operadores.
Las funciones polimórficas son muy útiles ya que permite crear algoritmos independientes del tipo de operadores.

Llamadas a funciones/procedimientos
Es fundamental que un compilador genere buen código para llamadas y retornos de funciones.   La traducción de una llamada incluye una secuencia de llamada, que es una secuencia de acciones que se toman a la entrada y a la salida de cada función/procedimiento. 

Aunque las secuencias de llamada difieren, incluso en aplicaciones del mismo lenguaje, habitualmente tienen lugar las siguientes acciones:

Cuando ocurre la llamada a un función, se debe asignar espacio para el registro de activación del procedimiento llamado.  Los argumentos de la función llamada se deben evaluar y poner a disposición de la función llamada en un lugar conocido.  Se deben establecer los apuntadores de ambiente para permitir que la función llamada tenga acceso a los datos de las funciones abarcadoras.  
Se debe guardar el estado de la función que efectúa la llamada para que pueda reanudar la ejecución después de la llamada.  También se guarda en un lugar conocido la dirección de retorno, que es la posición a la que la rutina llamada debe transferir el control cuando finalice.  La dirección de retorno normalmente es la posición de la instrucción que sigue la llamada en la función autor de la llamada.  Por último, se debe generar un salto al principio del código la función llamada.


No existe una división exacta de las tareas en el momento de la ejecución entre la función que hace la llamada y la función que recibe la llamada.

 A menudo, el lenguaje fuente, la máquina objeto y el sistema operativo imponen requisitos que favorecen una solución sobre otra.
Código de Tres Direcciones
Es una manera linear de representar un grafo de subexpresiones en donde los nombres explícitos
corresponden a los nodos interiores del grafo (figura 3), muy útil principalmente a la hora de optimizar. Las instrucciones se representan utilizando cuando mucho un solo operador en la parte derecha de la expresión, es decir, una expresión del tipo "x+y*z" se representaría de la manera "t1=y*z y t2=x+t1".
El código de tres direcciones se basa en 2 conceptos principalmente en 2 conceptos: direcciones e
instrucciones.
  • Nombres: los nombres que se usan en el programa puede aparecer también en el código de 3 direcciones, aunque a la hora de implementar se usara un puntero o su entrada en la tabla de símbolos.
  • Una constante: el compilador tiene que poder interactuar con muchos tipos de constantes.
Las instrucciones más básicas pueden definirse de la siguiente manera:
  • x=y'op'z, donde 'op' es un operador binario aritmético o una expresión lógica.
  •  x='op'y, donde 'op' es una operación unaria.
  • x=y, donde a x se le asigna el valor de y
  • goto L, la instrucción con la etiqueta L se ejecutara.
  • if x goto L o if false goto L, se ejecutaría la instrucción con la etiqueta L dependiendo de si x es verdadero o falso.
  • if x relop y goto L, se ejecutaría la instrucción L dependiendo del operador relacional que se le aplique a x y yparam x y call p,n, donde param x indica que x es un parámetro. call llama un procedimiento p con un número de parámetros n.
 En el diseño del código intermedio, es necesario escoger un buen conjunto de operadores. Se
Usando el código de 3 direcciones, el compilador puede representar código intermedio y ayudarse en la implementación mas optima del código final.
 
Las direcciones se pueden definir como: deben tener los suficientes operadores para satisfacer las instrucciones del lenguaje, y que a su vez sean cercanos al lenguaje de maquina. Sin embargo, si se crean demasiadas instrucciones, el optimizados y el generador de código tendrán que trabajar mas para generar el código final.
 
Una proposición de código de 3-direcciones se puede implantar como una estructura tipo registro con campos para el operador, los operandos y el resultado. La representación final será entonces una lista enlazada o un vector de proposiciones. Hay dos formas principales de implementar el código de tres direcciones:
Cuadruplas
Una cuadrupla es una estructura tipo registro con cuatro campos que se llaman (op, result, arg1, arg2). El campo op contiene un código interno para el operador.
Por ejemplo, la proposición de tres direcciones x = y + z se podría representar mediante la cuadrupla (ADD, x,y, z). Las proposiciones con operadores unarios no usan el arg2. Los campos que no se usan se dejan vacíos o un valor NULL. Como se necesitan cuatro campos se le llama representación mediante cuadruplas.

Tripletas
Para evitar tener que introducir nombres temporales en la tabla de símbolos, se hace referencia a un valor temporal según la posición de la proposición que lo calcula. Las propias instrucciones representan el valor del nombre temporal. La implementación se hace mediante registros de solo tres campos (op, arg1, arg2).
 
En la notación de tripletes se necesita menor espacio y el compilador no necesita generar los
nombres temporales. Sin embargo, en esta notación, trasladar una proposición que defina un valor temporal exige que se modifiquen todas las referencias a esa proposición. Lo cual supone un inconveniente a la hora de optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.
 
Una forma de solucionar esto consiste en listar las posiciones a las tripletas en lugar de listar las tripletas mismas. De esta manera, un optimizador podría mover una instrucción reordenando la lista, sin tener que mover las tripletas en si.


1 comentario:

Vistas a la página totales