JavaCC - Análisis Léxico

Análisis Léxico

El análisis léxico es la primera fase de un compilador. Dicha fase se halla bajo la responsabilidad del analizador léxico, cuya principal función consiste en leer los caracteres de entrada y elaborar como salida una secuencia de componentes léxicos llamada secuencia de tokens, que utiliza el parser para llevar a cabo el análisis sintáctico.
Cuando se utiliza JavaCC, las tareas involucradas en la etapa de análisis léxico son asignadas al Token Manager que se genera a partir de la especificación léxica que forma parte del archivo de entrada de JavaCC.

La especificación léxica para la generación del token manager, incluye la especificación de los tokens que deben reconocerse, sabiendo qué tipo de token es cada uno, los estados posibles en los que se hallará el token manager durante el proceso, y en qué casos irá transitando de un estado al otro, etc.
Para ello, la gramática del archivo de entrada debe contar con una serie de definiciones de tales entidades, las cuales se describen a continuación:

Especificación Léxica

Las entidades léxicas (tokens) que puedan ser procesadas por el token manager, se definen en el archivo de entrada mediante producciones compuestas por expresiones regulares. Tales producciones tienen la siguiente sintaxis:

regular_expr_production	::=	[ lexical_state_list ]
		regexpr_kind [ "[" "IGNORE_CASE" "]" ] ":"
		"{" regexpr_spec ( "|" regexpr_spec )* "}"

Estados Léxicos ([lexical_state_list])

Las especificaciones léxicas de JavaCC están organizadas en un conjunto de estados léxicos, que son los que permiten definir el comportamiento del token manager, dependiendo del momento en que se halla el análisis, y del contenido de la entrada en dicho instante.

Tipos de Expresiones Regulares ([regexpr_kind])

Existen cuatro tipos de expresiones regulares :
TOKEN, SPECIAL_TOKEN, SKIP y MORE, que permiten distinguir el tipo de entidad que se está reconociendo, de acuerdo a la posterior utilidad que tendrá dicho trozo del string de entrada, durante el análisis sintáctico.
Por ejemplo, si el tipo de la expresión regular es TOKEN, el token hallado es retornado. Si la clase es SPECIAL_TOKEN, el token hallado se almacenado para ser retornado conjuntamente con el próximo TOKEN que se reconozca.

Indistinguibilidad de mayúsculas ("[" "IGNORE_CASE" "]")

Sucediendo al descriptor del tipo de producción que se trata, se halla un "[IGNORE_CASE]" opcional, cuya presencia causa que la producción compuesta por expresiones regulares sea indiferente ante las letras mayúsculas y las minúsculas, es decir que tiene el mismo efecto que laopción de personalización global del parser IGNORE_CASE,salvo que en este caso se aplica localmente a la producción.

Tokens {" regexpr_spec ( "|" regexpr_spec)* "}"

La descripción de las entidades léxicas que son parte de la producción, comienza con la especificación de expresiones regulares que definan dichas entidades léxicas o tokens, pueden ir seguidas por un bloque de código java, y finalmente por una transición a otro estado léxico.

Declaraciones del Token Manager

Así como para la definición de los tokens se utilizan las producciones regular_exp_production, existe otro tipo de producciones que se utiliza durante el análisis léxico: token_manager_declsque sirve para introducir declaraciones que podrán ser insertadas en el token manager generado. La sintaxis es la siguiente:

token_manager_decls

::=

"TOKEN_MGR_DECLS" ":" java_block

Las declaraciones del token manager comienzan con la palabra reservada "TOKEN_MGR_DECLS" seguida por ":" y luego un conjunto de declaraciones Java y sentencias (del Java block). Estas declaraciones y sentencias son escritas en el token manager generado y son accesibles desde las acciones léxicas.

Sólo puede haber una declaración en un archivo de gramática JavaCC para el token manager.

Reconocimiento de tokens

En un estado determinado, todas las expresiones regulares se consideran posibles tokens. El token manager consume el número máximo de caracteres de la cadena de entrada que coincida con alguna de las expresiones regulares.Esto es, el token manager prefiere el match más largo que sea posible. Si existieran múltiples matches (de la misma longitud), se elige la expresión regular que ocurre antes en el archivo de la gramática.

Dado que el token manager se halla en un único estado en un momento determinado, sólo se consideran las expresiones regulares definidas en dicho estado. Después de lograr un match, puede especificarse una acción para ser ejecutada, o especificar una transición a un nuevo estado léxico. Si no se especifica ningún nuevo estado léxico, el token manager permanece en el estado actual.

Una vez que el token manager determina un match, los diferentes tipos de expresiones regulares especifican las acciones que deben realizarse cuando una expresión regular ha sido reconocida:

Cuando se detecta el final del archivo <EOF>, se crea un Token <EOF> sin tener en cuenta el estado actual del analizador léxico. Sin embargo, si se detecta un <EOF> en el medio de un match de una expresión regular o inmediatamente después de que una expresión regular MORE ha sido encontrada, se reporta un error.

Luego de reconocer una expresión regular, se ejecuta la acción léxica asociada, si es que la hay. Todas las variables y métodos declarados en el token manager están disponibles para ser usadas, además de otras variables y métodos adicionales. Inmediatamente ejecutadas las acciones, el token manager cambia su estado al estado especificado, si es que existe alguno.

El token manager es capaz de leer los tokens de entrada, mediante dos métodos de obtención de tokens distintos, dependiendo de las necesidades del usuario.

Ejemplos

A continuación, se encuentran dos especificaciones, a modo de ejemplo, para la identificación de cada una de las partes de la especificación.

Simple.jj, es la especificación del lenguaje ({})+

ea.jj, es la especificación del lenguaje de las expresiones aritméticas naturales con adición y producto.