Herramientas para la construccion de compiladores

Bison
C
Generador de Analizadores Sintácticos Ascendentes tipo YACC

COCO/R
C/C++
Generador de Analizadores Léxicos y Sintácticos Descendentes Recursivos

Flex
C
Generador de Analizadores Léxicos tipo Lex

Lex
C
Generador de Analizadores Léxicos

SDGLL1
exe
Sistema Detector de Gramáticas LL(1)

TS 2006
C/C++
Tipo abstracto de datos Tabla de Símbolos de uso sencillo (beta 0.4)

TS
C
Tipo abstracto de datos Tabla de Símbolos

TS-OO
C++
Tipo abstracto de datos Tabla de Símbolos

YACC
C
Generador de Analizadores Sintácticos Ascendentes LR(1)

Generacion de codigo intermedio

GENERACION DE CÓDIGO

Aquí se hablará de las herramientas generadoras automáticas de código para un compilador. Estas herramientas trabajan basadas en un conjunto de reglas; estas reglas definen la traducción de las instrucciones del lenguaje intermedio al lenguaje de máquina.

Para la generación de código, se busca en las reglas establecidas la proposición que coincida con la entrada actual; la entrada actual proviene de un árbol. Un ejemplo de esto seria entonces el compilador recibe una entrada de caracteres, por lo general escrita por el programador; el compilador realiza los análisis: léxico, sintáctico y semántico, para generar seguidamente el código intermedio, el código intermedio se genera con principios de búsqueda de patrones y aplicación de reglas. Después se hace la optimización del código intermedio; seguidamente se realiza la generación de código objeto en lenguaje de máquina.

Para la creación de generadores de código se deben considerar los siguientes aspectos:

La arquitectura de software para la cual se va ha desarrollar el generador
Las características especificas del lenguaje de programación para el cual se hará el generador.
El lenguaje con el que se desarrollará el propio generador Responder los interrogantes: ¿La generación de código se realizará a partir de modelos como Uml1? ¿La generación de código se hará a partir de las tablas de una base de datos ?,¿Se realizará un generador de código que su resultado sea fragmentos de código que son de uso más frecuente en el software? ¿Se creará un generador genérico que "genere" código para diferentes lenguajes.
Las reglas de utilización del generador, en otras palabras, la forma adecuada para que los usuarios del generador obtengan el mayor provecho.

En sintesis para crear un generador de código se deben hacer muchas de las tareas que realizan los compiladores; algunas de estas tareas son: la busqueda de patrones,la escritura de código, el analisis sintactico, el analisis lexico y la optimización de código. Estas tareas las realiza el desarrollador una vez para una arquitectura especifica.

Gestión de memoria en tiempo de ejecucion

Organizació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 elcual ha de ejecutarse. El programa resultante de la compilación debe organizarse deforma 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. 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) al del siguiente esquema

En este esquema se distinguen las secciones de:

- El Código
- La Memoria Estática.
- La Pila.
- El Montón.

El codigo

Es la zona donde se almacenan las instrucciones del programa ejecutable en código máquina, y también el código correspondiente a los procedimientos y funciones que utiliza. Su tamaño puede fijarse en tiempo de compilación.

Algunos compiladores fragmentan el código del programa objeto usando “overlays”. Estos “overlays” son secciones de código objeto que se almacenan en ficheros independientes y que se cargan en la memoria central (RAM) dinámicamente, es decir, durante la ejecución del programa. Los overlays de un programa se agrupan en zonas y módulos, cada uno de los cuales contiene un conjunto de funciones o procedimientos.

La memoria estatica

La forma más fácil de almacenar el contenido de una variable en memoria en tiempo de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del programa. No todos los objetos (variables) pueden ser almacenados estáticamente. Para que un objeto pueda ser almacenado en memoria estática su tamaño ( número de bytes necesarios para su almacenamiento) ha de ser conocido en tiempo de compilación. Como consecuencia de esta condición no podrán almacenarse en memoria estática:

• Los objetos correspondientes a procedimientos o funciones recursivas, ya que en tiempo de compilación no se sabe el número de variables que serán necesarias.
• Las estructuras dinámicas de datos tales como listas, árboles, etc. ya que el número de
  elementos que la forman no es conocido hasta que el programa se ejecuta.

La pila

La aparición de lenguajes con estructura de bloque trajo consigo la necesidad de técnicas de alojamiento en memoria más flexibles, que pudieran adaptarse a las demandas de memoria durante la ejecución del programa. En estos lenguajes, cada vez que comienza la ejecución de un procedimiento se crea un registro de activación para contener los objetos necesarios para su ejecución, eliminandolo una vez terminada ésta.

Dado que los bloques o procedimientos están organizados jerárquicamente, los distintos registros de activación asociados a cada bloque deberán colocarse en una pila en la que entrarán cuando comience la ejecución del bloque y saldrán al terminar el mismo. La estructura de los registros de activación varía de unos lenguajes a otros, e incluso de unos compiladores a otros. Este es uno de los problemas por los que a veces resulta difícil enlazar los códigos generados por dos compiladores diferentes.

El monton

Cuando el tamaño de un objeto a colocar en memoria puede variar en tiempo de ejecución, no es posible su ubicación en memoria estática, ni tan siquiera en la pila. Son ejemplos de este tipo de objetos las listas, los árboles, las cadenas de caracteres de longitud variable, etc. Para manejar este tipo de objetos el compilador debe disponer de un área de memoria de tamaño variable y que no se vea afectada por la activación o desactivación de procedimientos. Este trozo de memoria se llama montón (traducción literal del termino ingles heap que se utiliza habitualmente en la literatura técnica). En aquellos lenguajes de alto novel que requieran el uso del montón, el compilador debe incorporar al programa objeto el código correspondiente a la gestión del montón. Las operaciones básicas que se realizan sobre el montón son:

• Alojamiento: Se demanda un bloque contiguo para poder almacenar un objeto de un cierto tamaño.
• Desalojo: Se indica que ya no es necesario conservar un objeto, y que por lo tanto, la
  memoria que ocupa debe quedar libre para ser reutilizada en caso necesario por otros
  objetos.

Puedes encontrar mas informacion en la sigueinte direccion:

http://www.lcc.uma.es/~galvez/ftp/tci/tictema8.pdf

NOTACIONES

NOTACION 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

Ejemplo1:

A + (B * C)

Convertimos la parte de la expresión que se evalúa primero (aplicando leyes de
precedencia):

A + (B * C)
A + (B C *)
A (B C *) +
ABC *+

NOTACION 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.

Ejemplo 1: Expresar en notación prefija

A + (B * C)
A + (* B C )
+A (*B C)

NOTACION POLACA

La notación polaca es la originada por un automata con pila, en la que los operadores
siempre preceden a los operandos sobre los que actúan, y que tiene la ventaja de no
necesitar paréntesis:

Estándar

Ejemplo 1: 2 * ( 3 + 5 )

Ejemplo 2: 2 * 3 + 5

Polaca

Ejemplo 1: * 2 + 3 5

Ejemplo 2: + * 2 3 5