Gramáticas de atributos, clasificación y aportes en técnicas de evaluación

Abstract

Las gramáticas de atributos, desde que fueron propuestas por Knuth en 1966, se han utilizado ampliamente para el desarrollo de herramientas de procesamiento de lenguajes formales como compiladores e intérpretes de lenguajes de programa-ción; como también para especificar la semántica de lenguajes. Las gramáticas de atributos son un formalismo simple para la especificación de la semántica de lenguajes formales, como ser lenguajes de programación o de especifi-cación. Integran la modularidad que brindan las gramáticas libres de contexto y la expresividad de un lenguaje funcional. Si bien las gramáticas de atributos han sido ampliamente estu-diadas no es fácil encontrar definiciones precisas y rigurosas. Los principales motivos del desarrollo de esta tesis son en primer lugar, obtener un material autocontenido sobre sus defi-niciones, extensiones, implementación y aplicaciones, ya que prácticamente no existen libros actualizados en el tema. En segundo lugar, se realiza un estudio profundo sobre nuevas clasificaciones propuestas y métodos de evaluación. En este último aspecto es donde se presentan los aportes más signifi-cativos de esta tesis. En este trabajo se presentan las gramá-ticas de atributos en su forma clásica, mostrando definiciones más precisas que las que se pueden encontrar en la bibliografía tradicional. Se describen diferentes clasificaciones y métodos de evaluación secuenciales y concurrentes. Entre los principa-les aportes de este trabajo, se propone un algorimo eficiente de evaluación dinámica bajo demanda, que puede aplicarse para la evaluación de cualquier gramática de atributos bien definida (no circular). Este algorimo se ha implementado en la herramienta agcc, la cual ha sido desarrollada en el marco de este trabajo. Se analiza una nueva clasificación, la jerarquía NC, propuesta por Wuu Yang en 1999 y se relaciona con la clasificación tradicional. Se describe NCeval, una herramienta desarrollada en el marco de esta tesis, la cual genera evalua-dores estáticos para la familia NC(1). Un evaluador generado por NCEval realiza la evaluación disparando procesos o tareas concurrentes que no requieren sincronización, ya que operan sobre conjuntos independientes de instancias de atributos. El método de particionado usado en NCEval está basado en las dependencias y se demuestra que la partición inducida sobre el conjunto de atributos es la mas fina posible. Hasta el momento, no se conocen herramientas que utilicen este enfo-que. Finalmente se describe agcc (Attribute Grammars Compiler Compiler), herramienta desarrollada en el marco de esta tesis, la cual tiene un diseño totalmente modular per-mitiendo su extensibilidad tanto en los generadores de código como en los métodos de evaluación utilizados. Acepta la familia más amplia de gramáticas de atributos para las cuales pueden generarse evaluadores estáticos