Generación automática de analizadores sintácticos a partir de esquemas de análisis

Abstract

Los esquemas de análisis sintáctico son un formalismo de definición de algoritmos de análisis sintáctico que permite abstraer detalles de bajo nivel. En este trabajo, presentamos una técnica de compilación para transformar automáticamente un esquema de análisis sintáctico en una implementación ejecutable. Concretamente, a partir de un esquema obtendremos el código Java que implementa el analizador correspondiente, incluyendo técnicas de indexación adaptadas a cada esquema concreto para garantizar eficiencia. La técnica presentada es general, permitiendo trabajar con todo tipo de esquemas para gramáticas independientes del contexto, e incluye mecanismos de extensibilidad para definir nuevos elementos susceptibles de aparecer en dichos esquemas, al tiempo que es fácilmente generalizable a otros formalismos gramaticales.

The parsing schemata formalism allows us to describe parsing algorithms in a simple way by capturing their fundamental semantics while abstracting low-level detail. In this work, we present a compilation technique allowing automatic transformation of parsing schemata to executable implementations of their corresponding algorithms. Taking a simple description of a schema as input, our technique generates Java code for the corresponding parsing algorithm, including schema-specific indexing code in order to attain efficiency. Our technique is general enough to be able to handle all kinds of schemata for context-free grammars, providing an extensibility mechanism which allows the user to define custom notational elements, and it could also be easily generalized to other grammatical formalisms.