| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II Introducción 2.1 Estructura de un Compilador 2.1.1 Función del analizador léxico 2.1.2 Función del analizador sintáctico

2.1.3 Tabla de Símbolos

2.1.4 Función del analizador Semántico

2.1.5 Etapa de análisis

2.1.6 Etapa de Síntesis

UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

2.1.6 Etapa de Síntesis

> La generación de código no sólo depende de la representación intermedia elegida, sino también del hardware destino y del conjunto de instrucciones de dicho hardware.

> El código generado puede ser: Código absoluto, o Código relocalizable.

> El código absoluto significa la generación del código de máquina con direcciones de memoria absolutas, mientras que el código relocalizable indica la generación de código con desplazamientos de direcciones, como se muestra en la siguiente figura.

> Asignación de Memoria

> La declaración de un nombre y el uso posterior de este nombre da lugar a manipulaciones de la tabla de símbolos. En el caso de la generación de código, es necesario transformar la información de la tabla de símbolos en direcciones de memoria.

> La asignación de memoria es la asignación de espacio de memoria para el almacenamiento de los nombres, las variables auxiliares definidas por el compilador y la información adicional de los procedimientos, como la dirección de retorno.

> La asignación estática, el espacio de memoria para los nombres se asignará cuando se compile el programa fuente. La asignación dinámica puede asignarse y liberarse el espacio de memoria de un nombre durante la ejecución del programa.

> La asignación dinámica de memoria permite usar diferentes técnicas: Asignación por pila o asignación por montículo.

> La asignación dinámica se usa para procedimientos recursivos, mientras que la asignación por montículo es útil para manejar estructuras dinámicas de datos, como las listas enlazadas o los árboles.

> Paso de Parámetros

> Se conocen varias técnicas de paso de parámetros, como son: Llamada por Valor, en las cuales se copia el valor del parámetro real al espacio de memoria del parámetro formal durante la llamada al procedimiento, de esta manera, es posible tratar los parámetros formales como si fueran reales, ya que la asignación de memoria y el acceso son iguales que para las variables locales. Hay que generar código que lleve a cabo la operación de copiado.

> En las Llamada por Referencia se pasa al procedimiento la dirección del parámetro real, en lugar de su valor, de esta manera, la posición del parámetro formal contiene únicamente la dirección donde puede encontrar o modificar los datos.

> En las Llamada por Valor – Resultado, el parámetro real se copia al formal al entrar en el procedimiento y luego se copia de regreso al terminar, de esta manera, se puede tener acceso a los parámetros como si fueran variables locales. Esta técnica sólo debe aplicarse para pasar variables de tipo simple.

> En las Llamada por Nombre, el parámetro real sustituye textualmente al parámetro formal cada vez que éste ocurre. La forma tradicional para implantar esta técnica consiste en tratar el procedimiento como una macro, en donde el compilador reemplaza cada llamada al procedimiento con el cuerpo de procedimiento, los parámetros formales se sustituyen textualmente con los parámetros reales y los nombres locales se mantienen distintos de los nombres del bloque invocador.

> Direccionamiento de Variables

- Variables Simples

> En las variables simples hay que proporcionar espacio de la memoria para el almacenamiento de las variables. Una declaración de variable hace que se asigne espacio en esta área de datos, lo cual normalmente se lleva a cabo por medio de un apuntador al siguiente espacio libre, por lo que, el direccionamiento es muy simple.

- Matrices

> El manejo de matrices de tamaño fijo no es simple, debido a que el acceso a un elemento a[i] de una matriz unidimensional a[i1..s1] está indicado por la dirección basea + (i- i1) * tamaño, donde basea denota la dirección del primer elemento de la matriz (a[i1]) en el área de datos, i1 (s1) denota el límite inferior de la matriz y tamaño es el espacio de memoria (en palabras o bytes) que debe asignarse para almacenar un elemento de la matriz (dependiendo del tipo de la matriz).

> En el caso de matrices multidimensionales hay que establecer la correspondencia con una estructura lineal para que pueda efectuarse el almacenamiento. Esto puede hacerse en dos formas:

> En la forma por filas, los elementos de la matriz se almacenan de manera que el índice de la derecha es el que varía con mayor rapidez; en la forma por columnas, es el índice de la izquierda el que varía más rápidamente.

> La dirección de un elemento a[i, j] de una matriz bidimensional a[i1..s1, a2..s2] en forma por filas es:

> basea + ((i - i1) * (s2 - i2 + 1) + (j- i2)) * tamaño

> Y en forma por columnas es:

> basea + ((j - i2) * (s1- i1 + 1) + (i- i1)) * tamaño.

> Si los dos límites inferiores son cero, estas fórmulas de dirección se simplifican a:

> basea + (i * (s2 + 1) + j) * tamaño y basea + (j * (s1 + 1) + i) * tamaño, respectivamente.

> El manejo de matrices dinámicas es un poco más complicado, debido a que el problema puede resolverse generando un descriptor de la matriz durante la compilación, al cual se asigna un valor inicial en el momento de la ejecución. El descriptor reserva espacio para almacenar información acerca de la matriz. El direccionamiento de los elementos de las matrices es el mismo que para matrices de tamaño fijo, pero la información de límites inferiores y superiores se obtiene del descriptor.

> - Registros

> La asignación de una variable de tipo registro r1 a otra, r2, se lleva a cabo copiando el espacio de memoria correspondiente a r1 al área de r2, en donde se puede tener acceso a los elementos individuales del registro usando la dirección base del registro y un desplazamiento adecuado.

> Generación de Código

> La función de un generador de código es básicamente la traducción de la salida del análisis sintáctico y semántico (el código intermedio) a una secuencia equivalente de instrucciones que pueden ejecutarse en la máquina destino. La salida de un generador de código debe satisfacer dos requisitos esenciales:

> 1. El código producido debe ser correcto, y

> 2. El código debe ser óptimo.

> Al generar código de máquina con base en código intermedio, esto quiere decir que se han efectuado la mayoría de las revisiones y la conversión de tipos y que por tanto, el generador de código ya no tiene que encargarse de las reglas semánticas del lenguaje de programación.

> Hay que tomar dos decisiones básicas al generar código:

> 1. Asignación de registros: Los procesadores y las implantaciones de los lenguajes muchas veces requieren que se usen determinados registros para propósitos específicos.

> 2. Selección de instrucciones: Muchas veces es posible efectuar ciertos cálculos de distintas maneras, la elección de la mejor secuencia de instrucciones suele requerir conocimiento contextual.

> El Algoritmo de Generación de Código (GC)

> Supongamos que el generador de código produce un tipo de código ensamblador en forma de dos direcciones: operación fuente y operación destino.

> El algoritmo GC (generación de código) se presenta como un procedimiento con dos parámetros: un bloque básico y la longitud del bloque básico, como se muestra en el siguiente fragmento de código.

> El procedimiento HallarArg (arg, loc) determina la posición actual de arg, efectuando un relación de preferencia < λ. Para cada posición de arg, la preferencia mem < λ.reg significa que una posición de registro es más útil que una posición de memoria.

> El procedimiento LocalizarResultado (cuad, res) determina la posición donde debe colocarse el resultado de un cuádruplo (cuad.Res), considerando la posición de cuad.Argl y aplicando la relación de preferencia < λ con ciertas condiciones. Si no hay registros libres, hay que guardar en memoria uno que esté ocupado para luego devolver en res un registro libre.

> El procedimiento CódigoM (op, fuente, dest) produce las instrucciones de código de máquina de acuerdo con los parámetros reales.

> El procedimiento ActualizarDirección (x, p) actualiza el descriptor de dirección de x (en la tabla de símbolos) para indicar que x se encuentra en la posición p.

> El procedimiento ActualizarRegistro (x, r) actualiza el descriptor de registro de r para indicar que r contiene el valor x.

> El procedimiento ActualizarMemoria actualiza las posiciones de memoria de las variables cuyos valores han cambiado en los registros y que ya no se almacenan en memoria.

> Al aplicar el algoritmo GC al un bloque básico por ejemplo, se obtiene la secuencia de instrucciones siguiente:

> Es evidente que la secuencia de instrucciones no es óptima. Por ejemplo, no es necesario copiar el contenido el registro R0 al registro R2.

> Si el código intermedio es un árbol de sintaxis abstracta, nos interesa entonces un algoritmo de recorrido de árbol para producir el código destino deseado. Este algoritmo puede basarse en algoritmos generales de recorrido de árboles y probablemente sería más fácil de implantar. La representación de bloques básicos con gratos acíclicos dirigidos (DAG, directed acyclic graphs) es otro método útil.

> Optimización de Código

> La optimización de código normalmente aumenta el tiempo de compilación, el código puede optimizarse en función de reducir el tamaño de un programa, o
> aumentar la velocidad de ejecución de un programa.

> La reducción del tamaño de un programa ya no es tan importante, gracias a la disponibilidad a precios razonables de chips de memoria de alta densidad, pero la optimización de la velocidad de ejecución sigue siendo de interés vital, sin embargo, no debe malinterpretarse el término optimización.

> Las técnicas de optimización se basan en un extenso análisis de la estructura del programa y del flujo de datos. Durante la optimización suele subdividirse el programa en regiones de optimización y las técnicas empleadas pueden categorizarse como independientes de la máquina y dependientes de la máquina.

> Las técnicas de optimización independientes de la máquina no tienen por qué considerar el conocimiento de la estructura de hardware ni el conjunto de instrucciones de la máquina destino, por lo que son de carácter general. Las técnicas dependientes de la máquina deben conocer el hardware y el conjunto de instrucciones, ya que afectan cosas como la asignación de registros o la selección de instrucciones. Entre las técnicas de optimización están las siguientes:

> Calculo Previo de Constantes

> Cuando aparecen varias constantes en una expresión aritmética, puede ser posible combinarlas para formar una sola constante, su efecto es que el código generado requiere menos memoria y que aumenta la velocidad de ejecución del programa.

> El cálculo previo de constantes no sólo tiene que ver con proposiciones simples, sino que además puede aplicarse a pares de proposiciones. Por supuesto, esto requiere un análisis previo del flujo de datos, ya que el código requerirá menos memoria y se reducirá el tiempo de ejecución.

> Reducción de Fuerza y Frecuencia

> La reducción de fuerza es el proceso por el cual una operación costosa (en términos de tiempo de ejecución) se reemplaza por una más barata, la reducción de frecuencia es un proceso por el cual ciertos cálculos se mueven de una posición a otra para que se ejecuten con menos frecuencia.

> Las optimizaciones representativas que usan la reducción de fuerza son:

> - Reemplazar una operación de exponenciación por una de multiplicación más rápida.

> - Reemplazar una operación de multiplicación en un lazo por una operación de suma más rápida.

> - Reemplazar las operaciones de multiplicación por una potencia de dos por operaciones de desplazamiento aritmético.

> La reducción de frecuencia también se conoce como traslado de código. Si un lazo contiene cálculos que producen el mismo resultado cada vez que se ejecuta el lazo, es posible sacar los cálculos del lazo. De esta manera se aprovecha la memoria temporal para obtener un considerable aumento en la velocidad de ejecución.

> Optimización de Lazos

> La optimización de lazos es probablemente la entidad que produce los mejores resultados en cuanto al tiempo de ejecución de un programa.
> La aplicación de las técnicas de reducción de fuerza y frecuencia pueden servir para optimizar lazos, otras técnicas para la optimización de lazos pueden describirse como optimización por combinación y optimización por desarrollo.

> Eliminación de Código

> Otra técnica más de optimización se basa en la eliminación de código redundante y en subexpresiones comunes. Un código es redundante si nunca se puede llegar a él o si una expresión contiene elementos superfluos.

> Las subexpresiones comunes pueden ser especificadas en forma explícita por el programador. No obstante, las subexpresiones comunes también pueden aparecer en forma implícita al indizar matrices que comprendan operaciones de multiplicación o suma.

> Reacomodos

> De acuerdo con las reglas de asociatividad y distributividad, es posible efectuar ciertos reacomodos en las expresiones lógicas y aritméticas para obtener una reducción en la memoria temporal o un incremento en la velocidad de ejecución. Suponiendo que se trata de una máquina con un solo acumulador.

> Optimización Local

> La optimización local consiste en efectuar la optimización examinando grupos de instrucciones (el área local). Esta técnica puede ser dependiente de la máquina si la optimización se basa en el conjunto de instrucciones de la máquina destino. Sin embargo, esta técnica también puede ser independiente de la máquina si, por ejemplo, la optimización se basa en el código intermedio.

> Considerando un grupo de instrucciones, puede efectuarse una optimización de varias maneras:

> - Reemplazar las instrucciones costosas por otras más baratas, en donde podemos emplear instrucciones de desplazamiento en lugar de operaciones de multiplicación, o bien usar simplificaciones algebraicas.

> - Reducir las transformaciones de datos redundantes que frecuentemente aparecen en proposiciones consecutivas.

> - Reemplazar cadenas de instrucciones de ramificación por una sola instrucción de ramificación; es decir, si se transfiere el control a otra instrucción de ramificación, podemos reemplazar la dirección por la del destino final.

> - Las optimizaciones pueden dar lugar a otras optimizaciones o mejoras del código, de manera que es necesario repetir varias veces la optimización local para obtener la máxima mejora del código.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello