JavaCC

3 Feb

JavaCC

El JavaCC (Java Compiler Compiler) es un generador de programa de parsers (analizadores) de la fuente abierta para el lenguaje de programación de Java. JavaCC es similar al Yacc en que genera un programa de análisis para una gramática proporcionada en la notación EBNF, a menos que la salida sea código fuente de Java. Es semejante de Yacc, sin embargo, JavaCC genera programas de análisis de arriba hacia abajo, que lo limita al LL (k) clase de de gramáticas (particularmente, la repetición dejada no se puede utilizar). El constructor que lo acompaña, JJTree, construcciones del árbol sus árboles de la parte inferior para arriba.

JavaCC se autoriza debajo de una licencia del DEB.

En el 1996, el Sun Microsystems lanzó un generador de programa de análisis llamado Gato . Los reveladores responsables del Gato crearon a su propia compañía llamada Metamata y cambiaron el nombre de Gato del a JavaCC. Metamata se convirtió en eventual parte de WebGain . Después de que WebGain cerrara sus operaciones, JavaCC fue movido a su hogar actual.

La especificación proporcionada al generador JavaCC puede contemplar distintos aspectos del lenguaje para el que se quiere obtener el analizador:
– Características lexicográficas y sintácticas
es la forma más frecuente de uso del generador; la especificación proporcionada define las característi¬cas sintácticas y lexicográficas de un lenguaje y se genera un analizador léxico-sintáctico del lenguaje especificado.
– Características lexicográficas
en la especificación proporcionada al generador sólo se definen características lexicográficas del lengua¬je; con el código generado se puede obtener un analizador lexicográfico.
Características lexicográficas y sintácticas y comprobaciones semánticas
también es posible completar una especificación léxico-sintáctica con la inclusión de código Java com-plementario para que el programa generado (que incorpora adecuadamente ese código auxiliar) pueda hacer un análisis completo (léxico, sintáctico y semántico) del lenguaje especificado.

HERRAMIENTAS

Dado que el código generado por JavaCC está escrito en Java, es necesario disponer de una versión del sis-tema Java (compilador de Java e intérprete de la Máquina Virtual Java). Son programas de libre distribución y fáciles de conseguir. Estos son:

javacc: generador de analizadores
jjdoc: productor de documentación
jjtree: preprocesador de apoyo para tareas semánticas

Acción lexicográfica. Acción sintáctica

• acción lexicográfica: bloque de código Java asociado a una pieza sintáctica nominal (TOKEN) o a una secuencia de caracteres (SKIP); se ejecuta cuando se detecta en la entrada la pieza o la secuencia corres­pondiente; no se puede aplicar a piezas sintácticas anónimas (autodefinidas con comillas),

• acción sintáctica: bloque de código Java asociado a un punto de la estructura sintáctica (el punto indica­do por el sitio de la producción donde se inserta el bloque); se ejecuta cuando el análisis de la entrada pa­sa por ese punto de la estructura.

Valor de una pieza sintáctica comunicada

El analizador lexicográfico comunica al analizador sintáctico una pieza a través de un valor de la clase Token (fichero Token.java); un objeto de la clase Token representa las características de la pieza comunicada. En la clase Token, entre otros, se tienen los campos

String image

lexema de la pieza

int beginLine, beginColumn, endLine, endColumn

posición del lexema en el fichero analizado (indicada por los números de fila y de columna de su comienzo y de su terminación)

Valor asociado a un símbolo

En las producciones que especifican la sintaxis se pueden incluir asignaciones que sirven para dejar ano­tado el valor asociado a un símbolo:

• símbolo no terminal              valor = nombreSimbolo()

el método de análisis asociado a nombreSimbolo se ha declarado de un cierto tipo (distinto del tipo void); valor ha de ser una variable del mismo tipo que el método

• símbolo terminal                   dato = < nombrePieza >

el valor asignado es el valor de la clase Token representativo de la pieza sintáctica (nominal); dato ha de ser una variable de tipo Token

Pieza sintáctica comunicada

La pieza sintáctica comunicada puede mirarse desde cada uno de los dos analizadores:

• analizador sintáctico

la pieza comunicada (desde el analizador lexicográfico) se tiene anotada en un campo de la clase del analizador sintáctico declarado como

(static) public Token token

este valor es accesible desde el código de todos los métodos de análisis sintáctico; el contenido del campo varía cuando se recibe una nueva pieza sintáctica

• analizador lexicográfico

la pieza dispuesta para ser comunicada (al analizador sintáctico) se tiene anotada en una variable local declarada como

Token matchedToken

este valor es accesible para el código de todas las acciones lexicográficas

Lexema de la pieza comunicada

El lexema de la pieza sintáctica comunicada se encuentra disponible en dos sitios distintos que compar­ten el mismo nombre pero que son de distinto tipo y se usan de distinta manera:

• String image

es un campo de la clase TOKEN; puede consultarse en relación con un objeto de esa clase que esté disponible

• StringBuffer image

es un campo de la clase del analizador lexicográfico ( ∙ ∙ ∙ ∙ TokenManager.java); es accesible desde el código de la clase y, por lo tanto,  desde todas las acciones lexicográficas (bloques de có­digo que están incorporados al analizador lexicográfico);

se trata de un valor disponible tanto para las piezas sintácticas nominales (TOKEN) como para las secuencias que se saltan (SKIP)

Lexicografía

TOKEN    pieza sintáctica nominal

“∙ ∙ ∙”  pieza sintáctica anónima

SKIP     secuencia de caracteres que no forman pieza

1acción

lexicográfica

común

Commom –

TokenAction

2acción

lexicográfica

propia

(acción ligada

a una pieza)

3bloque de

declaraciones

lexicográficas

TOKEN_

MGR_DECLS

4declaraciones

lexicográficas

predefinidas

(disponibilidad

de uso)

TOKEN si si si si
“∙ ∙ ∙” si no
SKIP no si si si

▫ Las indicaciones “si” de las columnas 3 y 4 son consecuencia de las indicaciones de la columna 2.

▫ La acción lexicográfica común se ejecuta después de la acción lexicográfica propia.

 

Precisiones sobre el analizador sintáctico generado

Puede decirse que, en su funcionamiento más sencillo, cuando no se emplean las posibilidades de examen por adelantado (“lookahead”), JavaCC comprueba que las reglas sintácticas cumplen la condición LL(1) y generan un analizador descendente-predictivo-recursivo. Pero esta apreciación hay que matizarla, ya que el analizador sintáctico generado no se ajusta en sentido estricto al modelo de analizador LL(1).

En el modelo de análisis LL(1), el orden del examen de las distintas alternativas de expansión de un símbo­lo no terminal es indiferente ya que se conocen los símbolos directores de cada una de ellas (que resultan ser conjuntos disjuntos); en la implementación del subprograma de análisis asociado al símbolo no terminal <NombreSimb> cuyas producciones son

<NombreSimb> ::= α1

| α2

∙  ∙  ∙

| αn

se podría preguntar en cualquier orden si la pieza actual pertenece al conjunto de símbolos directores de las distintas reglas. Sin embargo, en el analizador sintáctico generado por JavaCC, la implementación del mé­todo asociado al símbolo no terminal <NombreSimb> no sigue esa pauta.

Si las anteriores reglas sintácticas se transcriben en JavaCC de la forma

void nombreSimb () :

{  }

{

α1-jcc

| α2-jcc

∙  ∙  ∙

| αn-jcc

}

el método de análisis generado procede de la siguiente manera:

se van considerando las alternativas, sucesivamente, en el mismo orden en el que están especifica­das: primero la de α1 (α1-jcc), después la de α2 (α2-jcc),  etc,

para cada alternativa seleccionada, se comprueba si la pieza por adelantado coincide con alguno de los símbolos iniciales de la parte derecha, y si hay coincidencia se prosigue el análisis con ella; si no hay coincidencia se pasa a la alternativa siguiente,

siguiendo con este orden, si se llega al final de las alternativas sin haberse encontrado coincidencia alguna, se produce un error sintáctico.

En el analizador generado por JavaCC hay una peculiaridad que no se tiene en los analizadores LL(1) es­trictamente considerados: la palabra vacía sí se considera como posible símbolo inicial de la parte derecha una regla (esto ocurre siempre que la parte derecha es anulable). De esta peculiaridad se deriva una conse­cuencia que ha de tenerse en cuenta al escribir la especificación: dado que siempre es posible considerar la palabra vacía como la siguiente pieza por adelantado, si se llega a examinar la alternativa correspondiente a una producción anulable, el analizador generado siempre seleccionará esa alternativa con independencia de la siguiente pieza que esté presente en la entrada que queda por analizar.

Así pues, si alguna de las producciones que definen un símbolo no terminal es anulable, es importante el or­den en que se escriben las alternativas en una especificación sintáctica JavaCC: el funcionamiento del ana­lizador generado sí depende de la colocación elegida para las reglas.

LINKS

  papar
Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: