domingo, diciembre 04, 2005
El extremo de atrás
Una de las etapas que requieren más cuidado, es la comprbación de tipos. Se requiere ser bastante meticuloso y analizar la gramática para tener presente dónde y cuándo hecer las verificaciones. Un descubrimiento agradable fue el encontrar que si se tiende a ser estricto y no permitor conversiones implícitas, la comprobación de tipos es capaz de alertar al mismo tiempo de ciertos errores menos perceptibles. Por ejemplo, si se utiliza el tipo "void" como tipo de retorno de una sentencia(statement) o de un procedimiento, aunque este tipo no esté disponible para el usuario, el uso de un procedimiento donde se espera una función o viceversa, se puede detectar como un error de tipos. A pesar de ello, una comprobación intencionalmete diseñada para capturar tal falla puede ser una mejor estrategia si se desea reportar con mensajes más explicativos.
Después de la etapa de comprobación de tipos, queda la generación del código intermedio. En este proyecto se pueden aplicar ciertas simplificaciones que son de mucha utilidad; tal como el asumir que todo error que se pueda capturar en la etapa de parseo, se capturará ahi, de manera que el código intermedio quedará de una vez, limpio y libre de errores.
Tal como su nombre lo indica, este producto representa el punto limítrofe entre la parte frontal y la posterior del compilador. Es interesante notar, que la representación intermedia es por sí misma, un lenguaje, y como tal es lejanamente factible escribir código de programación directamente en una representación "neutral". En teoría, cualquier lenguaje fuente puede traducirse a un determinado código intermedio, y un codigo intermedio puede traducirse a código fuente de otro lenguaje, ensamblador o código objeto(binario) de cualquier máquina. El código intermedio es, de todas formas, casi tan confuso de entender como el propio ensamblador, y varía demasiado, pues, a pesar de existir ciertos patrones de diseño, queda a conveniencia de autor del compilador utilizar la técnica que mejor se ajuste a la orientación que se adopte para el compilador.
Lo anterior me lleva a concluir que seguramente, cuando se traduce de código intermedio hacia cualquier otro, se debe asumir que fué generado por la parte frontal de un compilador y que por lo tanto, está libre de errores, ya que sería un desperdicio de recursos el hacer verificaciones en esta etapa intermedia. En el caso de este proyecto, resulta mucho más cómodo y seguro, producir el código intermedio como una estructura de datos y trabajar "en memoria", para evitar el tenr que pasar por un archivo, como es el caso de muchos compiladores profesionales. Queda claro, que ese archivo se utiliza bien por limitaciones técnicas, o por razones tales como el enlace de código escrito en varios archivos fuente distintos(probablemente en distintos lenguajes).
Otra conclusión importante, es que el uso de la tabla de símbolos es tan necesario y provechoso tanto en la etapa frontal como en la posterior; asimismo la libertad de diseño que permiten las herramientas modernas tales como el lenguaje JAVA y las computadoras de (por ahora)alta capacidad, como las actuales, facilitan sobremanera la realización de un compilador, ya que se eliminan muchas de las restricciones de espacio en memoria, algunos de los problemas de rendimiento(cuando se trate de compiladores pequeños a medianos) y el tamaño del código del compilador propiamente dicho. Aparentemente, de esta ventaja se a abusado en plataformas tales como .NET (joke?).
Implementacion de la representación intermedia.
Hay dos formas casi diferentes de implementar el código intermedio. La que he preferido es la de construir un arbol de sintaxis abstracta linealizado, utilizando una estructura de ArrayList, donde se guardan estructuras que hacen el papel de Cuads. Estas estructuras constan de un operador, dos operandos, y un resultado. Dependiendo del operador se evaluan los operandos, pudiendo éstos representar valores inmediatos, como en las hojas del árbol, o bien cursores a otras casillas en el mismo ArrayList, como en el caso de los nodos interiores. Los operandos pueden también representar índices de la Tabla de símbolos.
En este proyecto, el Arbol de sintaxis abstracta se construye de forma que siempre, al momento de crear un nodo que tiene hijos, éstos han sido previamente creados. Por otra parte, cada vez que se crea un nodo(u hoja), se inserta en la lista, y se retorna el índice en el cual sucedió la inserción, incrementando en uno el índice con cada inserción. Estos índices se hacen circular a través de la gramática como atributos sintetizados, permitiendo la fácil creacion de nuevos árboles a partir de los ya existentes. Esta forma de trabajo permite garantizar que para cualquier nodo con hijos, se cumple que el índice de los hijos es siempre menor que el índice del padre.
Este detalle se puede aprovechar de la siguiente manera:
El miembro "resultado" de los cuads se deja vacío al momento de la creación inicial del AST. El AST se recorre de acuerdo al índice de los nodos; siempre se visitará primero a los hijos, por lo cual, se puede asignar correctmente a "resultado" el valor conveniente, ya que cuando el padre de dicho nodo lo requiera, está garantizado que tal valor ya ha sido asignado.
Lo más importante de esta estrategia, es que permite la fácil asignación de registros a las expresiones en el momento del paso de la representación intermedia a ensamblador. Los registros asignados a los hijos se pueden liberar cuando se calcula el valor del padre.
Por otra parte, el asignar el resultado de los operadores binarios a uno de los registros de los operandos reduce el numero de registros necesarios para ciertos cálculos: por ejemplo para 3 + 4, en lugar de
add $t2, $t0, $t1
se puede hacer asi:
add $t0, $t0, $t1
de esta forma, se evita el tener que buscar un registro libre para el resultado, y se evita la operacion de liberar uno de los registros.
La parte referenta a los stack frames, resulta severamente difícil de entender, sin embargo no es igual de programar, ya que se trata en realidad de un segmento de código que es constante, al menos parcialmente. Claro, que esto ayudado en gran medida por la simplificación de usar palabras tanto para enteros como caracteres. Aun queda por resolver la temática de los arreglos, no obstante, parece sensato comprobar primero que las variables de tamaño constante son correctamente procesadas para despues comenzar con los arreglos. Con esto en mente, es recomendable calcular los despazamientos(offset) de manera incremental y no multiplicativa, ya que arreglos de cualquier tamaño pueden declararse entre variables de tamaño constante, por lo que simplemente multiplicar el numero de orden de declaración por el ancho de palabra es un tanto contraproducente.
En un comentario final, las estructuras de control ofrecen también un reto de estudio, pues, dado que el asembler se ejecuta secuencialmente, se debe analizar bien la colocación de los saltos y bifurcaiones.
Después de la etapa de comprobación de tipos, queda la generación del código intermedio. En este proyecto se pueden aplicar ciertas simplificaciones que son de mucha utilidad; tal como el asumir que todo error que se pueda capturar en la etapa de parseo, se capturará ahi, de manera que el código intermedio quedará de una vez, limpio y libre de errores.
Tal como su nombre lo indica, este producto representa el punto limítrofe entre la parte frontal y la posterior del compilador. Es interesante notar, que la representación intermedia es por sí misma, un lenguaje, y como tal es lejanamente factible escribir código de programación directamente en una representación "neutral". En teoría, cualquier lenguaje fuente puede traducirse a un determinado código intermedio, y un codigo intermedio puede traducirse a código fuente de otro lenguaje, ensamblador o código objeto(binario) de cualquier máquina. El código intermedio es, de todas formas, casi tan confuso de entender como el propio ensamblador, y varía demasiado, pues, a pesar de existir ciertos patrones de diseño, queda a conveniencia de autor del compilador utilizar la técnica que mejor se ajuste a la orientación que se adopte para el compilador.
Lo anterior me lleva a concluir que seguramente, cuando se traduce de código intermedio hacia cualquier otro, se debe asumir que fué generado por la parte frontal de un compilador y que por lo tanto, está libre de errores, ya que sería un desperdicio de recursos el hacer verificaciones en esta etapa intermedia. En el caso de este proyecto, resulta mucho más cómodo y seguro, producir el código intermedio como una estructura de datos y trabajar "en memoria", para evitar el tenr que pasar por un archivo, como es el caso de muchos compiladores profesionales. Queda claro, que ese archivo se utiliza bien por limitaciones técnicas, o por razones tales como el enlace de código escrito en varios archivos fuente distintos(probablemente en distintos lenguajes).
Otra conclusión importante, es que el uso de la tabla de símbolos es tan necesario y provechoso tanto en la etapa frontal como en la posterior; asimismo la libertad de diseño que permiten las herramientas modernas tales como el lenguaje JAVA y las computadoras de (por ahora)alta capacidad, como las actuales, facilitan sobremanera la realización de un compilador, ya que se eliminan muchas de las restricciones de espacio en memoria, algunos de los problemas de rendimiento(cuando se trate de compiladores pequeños a medianos) y el tamaño del código del compilador propiamente dicho. Aparentemente, de esta ventaja se a abusado en plataformas tales como .NET (joke?).
Implementacion de la representación intermedia.
Hay dos formas casi diferentes de implementar el código intermedio. La que he preferido es la de construir un arbol de sintaxis abstracta linealizado, utilizando una estructura de ArrayList, donde se guardan estructuras que hacen el papel de Cuads. Estas estructuras constan de un operador, dos operandos, y un resultado. Dependiendo del operador se evaluan los operandos, pudiendo éstos representar valores inmediatos, como en las hojas del árbol, o bien cursores a otras casillas en el mismo ArrayList, como en el caso de los nodos interiores. Los operandos pueden también representar índices de la Tabla de símbolos.
En este proyecto, el Arbol de sintaxis abstracta se construye de forma que siempre, al momento de crear un nodo que tiene hijos, éstos han sido previamente creados. Por otra parte, cada vez que se crea un nodo(u hoja), se inserta en la lista, y se retorna el índice en el cual sucedió la inserción, incrementando en uno el índice con cada inserción. Estos índices se hacen circular a través de la gramática como atributos sintetizados, permitiendo la fácil creacion de nuevos árboles a partir de los ya existentes. Esta forma de trabajo permite garantizar que para cualquier nodo con hijos, se cumple que el índice de los hijos es siempre menor que el índice del padre.
Este detalle se puede aprovechar de la siguiente manera:
El miembro "resultado" de los cuads se deja vacío al momento de la creación inicial del AST. El AST se recorre de acuerdo al índice de los nodos; siempre se visitará primero a los hijos, por lo cual, se puede asignar correctmente a "resultado" el valor conveniente, ya que cuando el padre de dicho nodo lo requiera, está garantizado que tal valor ya ha sido asignado.
Lo más importante de esta estrategia, es que permite la fácil asignación de registros a las expresiones en el momento del paso de la representación intermedia a ensamblador. Los registros asignados a los hijos se pueden liberar cuando se calcula el valor del padre.
Por otra parte, el asignar el resultado de los operadores binarios a uno de los registros de los operandos reduce el numero de registros necesarios para ciertos cálculos: por ejemplo para 3 + 4, en lugar de
add $t2, $t0, $t1
se puede hacer asi:
add $t0, $t0, $t1
de esta forma, se evita el tener que buscar un registro libre para el resultado, y se evita la operacion de liberar uno de los registros.
La parte referenta a los stack frames, resulta severamente difícil de entender, sin embargo no es igual de programar, ya que se trata en realidad de un segmento de código que es constante, al menos parcialmente. Claro, que esto ayudado en gran medida por la simplificación de usar palabras tanto para enteros como caracteres. Aun queda por resolver la temática de los arreglos, no obstante, parece sensato comprobar primero que las variables de tamaño constante son correctamente procesadas para despues comenzar con los arreglos. Con esto en mente, es recomendable calcular los despazamientos(offset) de manera incremental y no multiplicativa, ya que arreglos de cualquier tamaño pueden declararse entre variables de tamaño constante, por lo que simplemente multiplicar el numero de orden de declaración por el ancho de palabra es un tanto contraproducente.
En un comentario final, las estructuras de control ofrecen también un reto de estudio, pues, dado que el asembler se ejecuta secuencialmente, se debe analizar bien la colocación de los saltos y bifurcaiones.
