OBJETIVOS

• Describir el formato de especificación sintáctica en JavaCC.
• Describir las técnicas de tratamiento de gramáticas no LL(1) incluidas en JavaCC.
• Describir la implementación del analizador sintáctico del lenguaje de programación Tinto en JavaCC.

CÓDIGO A UTILIZAR

El código de esta práctica contiene la versión en JavaCC del analizador léxico y sintáctico de Tinto. Todos los ficheros Java del paquete tinto.parser se generan de forma automática a partir de la especificación descrita en el fichero TintoParser.jj.

• Código de la práctica

ESPECIFICACIÓN SINTÁCTICA EN JAVACC

La especificación sintáctica de la gramática se describe a continuación de la especificación léxica. (En realidad, las definiciones léxicas y sintácticas pueden estar mezcladas, pero resulta mucho más claro si se definen de forma ordenada.) Esta especificación corresponde a la definición de las reglas de producción asociadas a cada símbolo no terminal de la gramática. La sintaxis básica de una declaración sintáctica es la siguiente:

Como ya hemos comentado, JavaCC se basa en un análisis sintáctico descendente recursivo. En este tipo de análisis, cada símbolo no terminal genera una función. La cabecera de la declaración sintáctica corresponde a la cabecera de la función asociada al símbolo no terminal descrito. El tipo se refiere al tipo de dato que devuelve la función, que puede ser tanto un tipo de datos simple como un objeto de una determinada clase. El identificador corresponde al nombre del símbolo no terminal, que coincide con el nombre de la función asociada. La lista de parámetros se refiere a los parámetros a utilizar en la llamada a la función y se describen de la misma forma que en un método Java. El código Java que sigue a la cabecera de la declaración es incluido literalmemte en la función generada y se suele utilizar para declarar las variables que se van a utilizar en la función.

La descripción EBNF de la regla de producción permite utilizar todas las operaciones de este formato: la disyunción (por medio del carácter ‘|’), la clausura (siguiendo el formato ‘(‘ expresión ‘)’* ), la clausura positiva (con el formato ‘(‘ expresión ‘)’+ ) y la opcionalidad (utilizando ‘[‘ expresión ‘]’ ). Para referirnos a símbolos terminales, es decir, a tokens, se utiliza la expresión ‘<‘ nombre_del_token ‘>’. Para referirnos a símbolos no terminales se utiliza la expresión identificador(lista_de_parámetros), es decir, se introduce una llamada a la función asociada al símbolo no terminal.

Como hemos comentado, las funciones asociadas a los símbolos terminales pueden devolver un valor de cualquier tipo válido en Java. Por su parte, los símbolos terminales devuelven un valor de tipo Token. Estos valores pueden asignarse variables de la siguiente forma:

Estas variables deben haber sido declaradas en el bloque Java incluido al comienzo de la declaración sintáctica.

A continuación se muestra un ejemplo de definición de una regla de producción sintáctica:

EL MANEJO DEL LOOKAHEAD EN JAVACC

El comportamiento por defecto de la herramienta JavaCC es generar analizadores para gramáticas de tipo LL(1). Sin embargo, la herramienta ofrece la posibilidad de modificar el lookahead, es decir, el número de tokens a analizar para tomar decisiones, para manejar así gramáticas de orden superior.

Existen cuatro formas de modificar el lookahead en JavaCC. La documentación de la herramienta denomina a estas formas como lookahead global, lookahead local, lookahead sintáctico y lookahead semántico. Vamos a estudiar cada una de estas formas.

• Lookahead global

JavaCC ofrece la posibilidad de modificar el valor del lookahead por medio de las opciones incluidas al comienzo de cada especificación. Para fijar, por ejemplo, un lookahead 2, hay que añadir al comienzo del archivo de especificación de la gramática el siguiente bloque:

options {      LOOKAHEAD = 2;   }

Este tipo de opciones es muy desaconsejable, ya que fuerza a la herramienta a generar un código en el que todas las tomas de decisiones se realizan analizando el valor de dos tokens. Esto produce unas instrucciones más complicadas y más lentas al ejecutarse.

En una descripción gramatical normal, los posibles conflictos LL(1) se producen en puntos muy concretos de la gramática. En la mayoría de los puntos de decisión es suficiente con analizar el siguiente token para tomar la decisión adecuada, por lo que modificar globalmente el lookahead no tiene demasiada utilidad.

• Lookahead local

La modificación local del lookahead consiste en asignar un valor diferente a este parámetro tan sólo en aquellos puntos de decisión en los que no sea suficiente con estudiar el siguiente token, sino que haya que considerar un número de tokens mayor. JavaCC permite modificar localmente el valor del lookahead en cualquier punto de una descripción sintáctica insertando la función LOOKAHEAD con el valor deseado para este parámetro en el punto de inserción.

La siguiente gramática presenta un conflicto LL(1) delante de la opción ya que cuando el siguiente token es num no se puede saber si se refiere al primer num de la opción o al num posterior a la misma.

<Llamada>  ->   id   parab   (  num   (  coma   num  )*  )?   num   parce

Este conflicto se resuelve analizando dos tokens en vez de uno. En ese caso, si los tokens fueran num coma o num num entonces debe ejecutarse la opción. Por el contrario, si los tokens fueran num parce significa que la opción no estaría presente en la cadena de entrada. La sintaxis para resolver este problema en JavaCC es la siguiente:

void llamada() :    {}   {        <ID> <PARAB>       LOOKAHEAD(2)       ( <NUM> ( <COMA> <NUM> ) * )?       <NUM> <PARCE>    }

• Lookahead sintáctico

En ocasiones, la decisión de expandir una determinada construcción sintáctica depende de que los siguientes tokens a analizar cumplan un determinado patrón sintáctico. Para resolver este problema se puede fijar un valor local para el lookahead lo suficientemente grande como para abarcar todo el patrón, pero esto no siempre es posible ni deseable. Veamos un ejemplo.

void JavaDefinition() :    {} {        JavaClassDefinition()      | JavaInterfaceDefinition()   }    void JavaClassDefinition() :    {} {      (“public” | “abstract” | “final”) * “class”      JavaClassName()      JavaClassExtends()      JavaClassImplements()      JavaClassBody()    }    void JavaInterfaceDefinition() :    {} {      (“public” | “abstract” | “final”) * “interface”      JavaInterfaceName()      JavaInterfaceExtends()      JavaInterfaceBody()    }

La figura anterior muestra la descripción en JavaCC de una definición en Java, que puede ser una clase o una interfaz. El problema es que ambos tipos de definiciones comienzan con la misma construcción (los modificadores de acceso) y sólo es posible distinguir si se trata de una definición de clase o interfaz al llegar a los tokens class o interface. Por tanto, la descripción anterior no es LL(1). Podemos intentar resolver esta situación fijando un valor mayor para el lookahead, que en este caso debe tener al menos un valor 4. Sin embargo, la construcción sintáctica de los modificadores de acceso puede (teóricamente) estar formada por un número indeterminado de tokens, ya que contiene una operación de clausura. Esto nos lleva a aumentar el valor del lookahead hasta alguna cantidad que supongamos que no va a alcanzarse nunca (10 o 20, por ejemplo) lo que se traduce en unas expresiones de las condiciones de selección demasiado complejas.

JavaCC ofrece una sintaxis diferente de la función LOOKAHEAD que permite resolver este problema de una forma sencilla. Consiste en utilizar como parámetro de la función LOOKAHEAD una definición sintáctica. Si los tokens de la cadena de entrada verifican esa construcción sintáctica entonces se acepta la opción siguiente. Utilizando esta opción, el ejemplo anterior se puede resolver de la siguiente forma:

void JavaDefinition() : {} {        LOOKAHEAD( (“public” | “abstract” | “final”) * “class” )        JavaClassDefinition()      | JavaInterfaceDefinition()    }

Se puede utilizar cualquier definición sintáctica como parámetro de la función LOOKAHEAD. Por ejemplo, JavaClassDefinition es una definición sintáctica que hemos descrito en la especificación anterior, por tanto, la siguiente definición también es válida:

void JavaDefinition() : {} {        LOOKAHEAD( JavaClassDefinition() )        JavaClassDefinition()      | JavaInterfaceDefinition()    }

Sin embargo, este tipo de expresiones hay que tratarlas con cuidado. El ejemplo anterior se puede interpretar de la siguiente forma: si la cadena de entrada responde sintácticamente a la definición de una clase, entonces continúa el análisis ejecutando la definición de una clase. Esto conlleva realizar dos pasadas sobre el fichero de entrada: la primera para tomar la decisión y la segunda para realizar el análisis. Aunque formalmente es correcto, desde el punto de vista de la eficiencia es inaceptable. Además, como hemos visto, se puede tomar la decisión correcta en el momento de leer el token class y esta opción continuaría analizando todos los tokens hasta completar la clase (podrían ser miles).

Se puede utilizar la función LOOKAHEAD combinando dos parámetros: un número (lookahead local) y una expresión (lookahead sintáctico). En este caso el valor numérico representa el número máximo de tokens a analizar. Si tras leer ese número de tokens aún no se ha verificado la expresión sintáctica, entonces se considera no verificada. Por ejemplo:

void JavaDefinition() :    {} {         LOOKAHEAD( 10, (“public” | “abstract” | “final”) * “class” )        JavaClassDefinition()      | JavaInterfaceDefinition()    }

• Lookahead semántico

La última de las posibilidades que ofrece JavaCC para modificar el lookahead se conoce como lookahead semántico y responde a la siguiente sintaxis de la función LOOKAHEAD:

LOOKAHEAD( { expresión_booleana } )

La expresión booleana debe estar descrita entre llaves puede tener cualquier código Java que genere un valor booleano. El significado es que si el resultado de evaluar la expresión es verdadero, entonces se acepta la opción siguiente. La expresión se utiliza generalmente para analizar aspectos semánticos de los tokens. El siguiente ejemplo muestra una construcción gramatical en la que se ejecuta la opción B cuando el lexema del siguiente token comienza por la letra “I”.

void A() :    {} {        LOOKAHEAD( { getToken(1).image.startsWith(“I”) } )        B()      | C()    }