IBURG: su aplicación para la generación de generadores de código en un proyecto de compiladores

Abstract

En numerosas carreras de Ciencias de Computación se incluye la realización de un proyecto de diseño e implementación de un compilador. La etapa de generación de código, por su complejidad y por la extensión global del proyecto, suele simplificarse adoptando como lenguaje objeto el mismo lenguaje en que se realiza el desarrollo o el de alguna máquina abstracta definida ad hoc. Sin embargo desarrollar esta etapa en condiciones reales, para una arquitectura existente, es de gran valor formativo y quizás la mejor forma de enfrentar al alumno con la práctica de la programación a bajo nivel. En este trabajo se discute la aplicación de las técnicas usadas en la construcción de generadores de código y el uso de una herramienta iburg, cuya utilización permitió, generar código assembler optimizante para el ambiente linux como última etapa de un compilador Mini c. Trabajo realizado en una asignatura cuatrimestral. Generalmente un compilador genera una representación intermedia del programa fuente para realizar las operaciones requeridas en la generación de código optimizante. Esto permite además abstraerse de la plataforma (hardware y sistema operativo) sobre el cual se desea generar el código objeto, permitiendo desarrollar un front-end portable. El front_end utiliza un (o viarios) back_end que se encarga de la generación de código final para una plataforma determinada. El código intermedio generado, generalmente tiene la forma de árbol, ya que se asemeja a la forma del árbol de parsing construido por el reconocedor sintáctico (parser). Para producir código objeto a partir de esta representación es conveniente utilizar alguna herramienta que permita realizar un reconocimiento de patrones (subárboles) que se relacionan con las entidades semánticas mínimas y seleccionar las instrucciones de máquina más apropiadas que las implementen, esto es, secuencias de instrucciones que tengan el menor costo ( según un criterio de uso de recursos preestablecido). Un recorrido posible para un árbol no necesariamente es el que lleva a producir código de menor costo (en términos de uso de recursos), por lo cual es necesario evaluar todos los posibles recorridos para determinar el óptimo. En este artículo se analizará la herramienta, iburg, que toma como entrada una gramática libre de contexto que describe el árbol de representación elegido (aumentada con información de costos) y genera como salida un reconocedor de patrones (parser o BURS authomata) sobre el árbol. El reconocedor generado realiza una cobertura óptima en término de los costos asociados para un nodo del árbol dado como entrada. La determinación de recorridos (covers) se realiza en el momento en que se construye el autómata BURS (Bottom-Up Rewrite System) utilizando programación dinámica. Esto permite que el autómata generado sea extremadamente rápido y simple. Se ven ejemplos de aplicaciones para selección de instrucciones, inferencia de tipos y simplificaciones de árboles y se describe la experiencia realizada.