Herramientas para la construcción de compiladores

Se han creado algunas herramientas generales para el dise˜no automatico de componentes especıficos de compilador. Estas herramientas utilizan lenguajes especializados para especificar e implantar el componente, y pueden utilizar algoritmos bastante complejos. Las herramientas mas efectivas son las que ocultan los detalles del algoritmo de generacion y producen componentes que se pueden integrar con facilidad al resto del compilador. La siguiente es una lista de algunas herramientasutiles para la construccion de compiladores:

1. Generadores de analizadores sintacticos: Estos generadores producen anal-izadores sintacticos, normalmente a partir de una entrada fundamentada en una gramatica independiente del contexto. En los primeros com-piladores, el analisis sintactico consumıa no solo gran parte del tiempo de ejecucion del compilador, sino gran parte del esfuerzo intelectual de escribirlo. Esta fase se considera ahora una de las mas faciles de aplicar. Muchos de los generadores de analizadores sintacticos utilizan poderosos algoritmos de analisis sintactico, y son demasiado complejos para realizarlos manualmente.

2. Generadores de analizadores lexicos. Estas herramientas generan automaticamente analizadores lexicos, por lo general a partir de una especificacionbasada en expresiones regulares. La organizacion basica del analizadorlexico resultante es en realidad un automata finito. Una herramienta muyutilizada en la especificacion de analizadores lexicos para varios lenguajeses el compilador LEX.

3. Dispositivos de traduccion dirigida por la sintaxis. Estos producen grupos de rutinas que recorren el arbol de analisis sintactico, como el visto enclase, generando codigo intermedio. La idea basica es que se asocian una o mas ”traducciones” con cada nodo del arbol de analisis sintactico, y cada traduccion se define partiendo de traducciones en sus nodos vecinos en el arbol.

4. Generadores automaticos de codigo: Tales herramientas toman un conjunto de reglas que definen la traduccion de cada operacion del lenguaje intermedio al lenguaje de maquina para la maquina objeto. Las reglas deben incluir suficiente detalle para poder manejar los distintos metodos de acceso posibles a los datos; por ejemplo, las variables pueden estaren registros, en una posicion fija (estatica) de memoria o pueden tener asignada una posicion en una pila. La tecnica fundamental es la de ”concordancia de plantillas”. Las proposiciones de codigo intermedio se reemplazan por ”plantillas” que representan secuencias de instruccionesde maquina, de modo que las suposiciones sobre el almacenamiento de las variables concuerden de plantilla a plantilla. Como suele haber muchas opciones en relacion con la ubicacion de las variables (por ejemplo, en uno ovarios registros o en memoria), hay muchas formas posibles de ”cubrir” elcodigo intermedio con un conjunto dado de plantillas, y es necesario seleccionar una buena cobertura sin una explosion combinatoria en el tiempo de ejecucion del compilador.

5. Dispositivos para analisis de flujo de datos: Mucha de la informacion necesaria para hacer una buena optimacion de codigo implica hacer un ”analisis de flujo de datos”, que consiste en la recoleccion de informacion sobre la forma en que se transmiten los valores de una parte de un programa a cada una de las otras partes. Las distintas tareas de esta naturaleza se pueden efectuar esencialmente con la misma rutina, en la que el usuario proporciona los detalles relativos a la relacion que hay entre las proposiciones en codigo intermedio y la informacion que se esta recolectando.

Generación de Código Intermedio

En el modelo de análisis y síntesis de un compilador, la etapa inicial traduce un
programa fuente a una representación intermedia a partir de la cual la etapa final
genera el código objeto.
Los detalles del lenguaje objeto se confinan en la etapa final, si esto es posible. Aunque un programa fuente se puede traducir directamente al lenguaje objeto, algunas
ventajas de utilizar una forma intermedia independiente de la máquina son:

1. 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.
2. Se puede aplicar a la representación intermedia un optimizador de código
independiente de la máquina.



Hay lenguajes que son pseudointerpretados que utilizan un código intermedio llamado
código-P que utiliza lo que se denomina bytecodes (sentencias de un μP hipotético). Por ejemplo
Java utiliza los ficheros .class, éstos tienen unos bytecodes que se someten a una
JavaVirtualMachine, para que interprete esas sentencias.
En este capítulo se muestra cómo se pueden utilizar los métodos de analizadores dirigidos
por la sintaxis para traducir a un código intermedio, construcciones de lenguajes de programación
como declaraciones, asignaciones y proposiciones de flujo de control. La generación de código
intermedio se puede intercalar en el análisis sintáctico.

Gestión de la memoria en tiempo de ejecución

Cuando un programa se ejecuta sobre un sistema operativo existe un proceso previo
llamado cargador que suministra al programa un bloque contiguo de memoria sobre el
cual ha de ejecutarse. El programa resultante de la compilación debe organizarse de
forma que haga uso de este bloque. Para ello el compilador incorpora al programa objeto el código necesario.
Las técnicas de gestión de la memoria durante la ejecución del programa difieren de unos lenguajes a otros, e incluso de unos compiladores a otros. En este capítulo se estudia la gestión de la memoria que se utiliza en lenguajes procedurales como FORTRAN,PASCAL, C, MODULA-2, etc. La gestión de la memoria en otro tipo de lenguajes(funcionales, lógicos, ...) es en general diferente de la organización que aquí se plantea.
Para lenguajes imperativos, los compiladores generan programas que tendrán en tiempo
de ejecución una organización de la memoria similar (a grandes rasgos) a la que aparece en la figura 1.



En este esquema se distinguen las secciones de:
- El Código
- La Memoria Estática.
- La Pila.
- El Montón.

ALGORITMO PARA CONVERTIR EXPRESIONES INFIJAS EN POSTFIJAS (RPN)

1. Incrementar la pila
2. Inicializar el conjunto de operaciones
3. Mientras no ocurra error y no sea fin de la expresión infija haz
- Si el carácter es:
*. PARENTESIS IZQUIERDO. Colocarlo en la pila

*. PARENTESIS DERECHO. Extraer y desplegar los valores hasta encontrar paréntesis izquierdo. Pero NO DESPLEGARLO

*. UN OPERADOR.
- Si la pila esta vacía o el carácter tiene más alta prioridad que el elemento del tope de la pila insertar el carácter en la pila.
- En caso contrario extraer y desplegar el elemento del tope de la pila y repetir la comparación con el nuevo tope.

*. OPERANDO. Desplegarlo.
4. Al final de la expresión extraer y desplegar los elementos de la pila hasta que se vacíe.

EXPRESIONES InFija, PreFija Y PosFija

1. PreFija:

La Expresión o Notación PreFija nos indica que el operador va antes de los operandos sus características principales son:

-Los operandos conservan el mismo orden que la notación infija equivalente.
-No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación.
-Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.
-Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado.

2. InFija:

La Expresión o Notación InFija es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión

3. PostFija:

Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son:

-El orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua.
-La operación posfija no es exactamente lo inverso a la operación prefija equivalente

EJEMPLO:

Si deseamos representar la expresione (2+(3*4)) = x en las tres notaciones mencionadas, el resultado sería:

Notación prefija
= + 2 * 3 4 x

Notación infija
2+3*4 = x

Notación postfija
2 3 4 * + x =