Apéndice IV. Listas en ANTLR #

Introducción #

En EBNF hay varias formas de expresar la repetición de elementos. Por ejemplo, las dos gramáticas siguientes son dos alternativas que generan el mismo lenguaje:

n: a e* b
e: x y z

n: a e b
e: (x y z)*

Posteriormente, para construir el AST, habrá que añadir acciones Java a dichas reglas para recolectar los nodos del símbolo e en una lista. Sin embargo, esto será más fácil en unas formas de expresar la repetición que en otras. Por tanto, ¿cuál de las dos versiones anteriores usar y por qué?

En este apéndice se mostrarán todas las formas de expresar listas en EBNF y se verá qué acciones Java hay que incrustar para crear y agrupar los nodos en cada una. Se verán así sus ventajas en inconvenientes.

Finalmente, después de estudiar cada opción, se hará una comparativa de todas ellas. De esta comparativa es de donde surge la recomendación hecha en el capítulo de creación de listas en EBNF sobre cómo hacer las listas en EBNF.

Sin embargo, aunque sería suficiente quedarse con esa recomendación, se incluye este apéndice por dos motivos:

• Por si se tiene interés en saber por qué se hicieron esas recomendaciones y no otras.
• Por si el alumno, a la hora de hacer su gramática, llega a otras formas de crear las listas y quiere saber las diferencias con las recomendadas. Para ello, sólo tiene que buscar su solución de entre las aquí analizadas.

Lenguaje de Ejemplo #

Para poder comparar todas las formas de introducir los nodos en listas, se modelará el mismo lenguaje en todas ellas.

• El lenguaje estará formado por los símbolos a, b, e y n.
• El símbolo n debe empezar por una a, la siguen cero o más e y acaba en una b.

  n: a  e ... e  b
  

• La composición de a, e y b no es relevante (podría ser cualquier combinación de tokens y/o no-terminales).

Se quieren gramáticas para las dos variantes del lenguaje: sin separadores entre los elementos e y otra versión con la coma ',' como separador.

Los nodos del AST que se quieren crear serán NNode y ENode para los símbolos n y e respectivamente.

n returns [NNode ast]: ...  { $ast = new NNode(...); }

e returns [ENode ast]: ...  { $ast = new ENode(...); }

Gramáticas Candidatas para el Lenguaje #

Lo que se verá ahora son las distintas gramáticas con las que se puede representar el lenguaje anterior. Concretamente, las formas de expresar la repetición del símbolo e. Esto se puede hacer de muchas maneras en función de dónde se pongan los operadores '+', '*' y '?'.

De los cuatro tipos de listas, sólo se analizarán las versiones 0+ss y 0+cs del lenguaje, ya que las versiones 1+ss y 1+cs tendrían exactamente las mismas acciones que estas.

En función de dónde se pongan los operadores, este lenguaje podría reconocerse con las siguientes gramáticas equivalentes EBNF:

• Caso 1. Poniendo la repetición en el padre n.

  // Versión de lista 0+ss n: a e* b e: ...

  // Versión de lista 0+cs n: a (e (',' e)*)? b e: ...

• Caso 2 . Poniendo la repetición en el hijo e.

  // Versión de lista 0+ss n: a e b e: (...)*

  // Versión de lista 0+cs n: a e b e: (... (',' ...)*)?

• Caso 3. Poniendo la repetición en una regla intermedia a la que se llamará es.

  // Versión de lista 0+ss n: a es b es: e* e: ...

  // Versión de lista 0+cs n: a es b es: (e (',' e)*)? e: ...

• Caso 4. Este es un caso particular que sólo se puede dar en las repeticiones 0+cs. En este caso, en el que '*' va seguido de un '?', se tienen dos opciones:

  • Que ambos operadores vayan juntos en la misma regla.

    n: a es b es: (e (s e)*)? // Aquí el '*' y el '?' e: ...

  • Que vayan separados en reglas distintas.

    n: a es? b // Aquí sólo el '?' es: e (s e)* // Aquí sólo el '*' e: ...

Caso 1. Repetición en el Padre #

Si la repetición se indica en el padre, como ya se comentó antes, se tienen los dos siguientes casos en función de que sea 0+ss o 0+cs.

// Versión de lista 0+ss
n: a e* b
e: ...

// Versión de lista 0+cs
n: a (e (',' e)*)? b
e: ...

En esta caso, se tiene tres opciones a la hora de insertar las acciones Java en las gramáticas:

• Insertar los hijos de uno en uno.
• Usar una lista local.
• Usar el operador '+=' de ANTLR.

Insertar los Hijos Individualmente #

En esta solución, en vez de crear el nodo padre NNode pasándole los hijos en el constructor, se crea primero dicho nodo padre sin pasarle ningún hijo y, posteriormente, se le van insertando los hijos de uno en uno con algún método que tenga el padre para ello.

Para mostrar esto, se van a quitar temporalmente los no-terminales a y b de la regla n: a e* b para dejarla en n: e*, ya que de otra manera complican notablemente el ejemplo (lo cual ya es un anticipo de la poca idoneidad de esta solución).

La versión 0+ss sería:

n returns [NNode ast = new NNode()]
    : (e { $ast.addChild($e.ast); })* ;

e returns [ENode ast]: ...

La versión 0+cs sería:

n returns [NNode ast = new NNode()]
    : (e { $ast.addChild($e.ast); } (',' e { $ast.addChild($e.ast); })*)? ;

e returns [ENode ast]: ...

Como puede verse, el nodo padre NNode, en vez de crearse de la manera habitual al final de la regla con el habitual $ast = new.Node(), se crea ya en la cláusula returns sin pasarle ningún hijo aún.

Consideraciones de esta opción:

• Esta solución requiere que el nodo padre tenga un método que permita añadir los hijos de uno en uno (addChild). Eso supone además que, a la hora de calcular la posición del padre en el fichero, será necesario que dicho método addChild actualice las posiciones del padre a medida que le añadan hijos.
• Esta solución se complica si, además de los elementos a repetir e, se reintroducen los símbolos a y b que había originalmente en la regla n. En ese caso, habrá que añadir métodos también para añadir dichos hijos (e intercalar sus llamadas en la regla).
• El hecho de que los hijos se añadan de uno en uno supone que:
  • No se sabrá, cuando se inserte un hijo, si habrá mas. Por tanto, esta solución no se puede usar en situaciones en las que se necesite hacer alguna operación cuando estén ya todos los hijos insertados.
  • El objeto padre, en este caso, estará en un estado inválido hasta que se pasen todos los hijos (ya que el constructor no podrá cumplir esa misión).
  • Se podría añadir un método noMoreChildren en el nodo que se llamara en una acción al final de la regla para indicar que ya no hay más hijos y, por tanto, se realicen ya las operaciones que requieran de todos ellos. Pero esto complicaría el nodo y la regla.
• Al insertar una acción en mitad de la regla, añade ruido que dificulta identificar la esencia de la regla (el a e* b). Este ruido aumenta en el caso de las versiones con separadores.
• Esta solución no sería válida si n, en vez de ser una regla, tuviera más alternativas que necesitarán devolver distintos objetos, ya que el new no va en cada regla sino en la cláusula returns.

Lista Local #

En esta solución se hará uso de una lista local donde se guardarán los ENode para luego pasárselos todos juntos al NNode.

La versión 0+ss sería:

n returns [NNode ast]
  locals[List<ENode> list = new ArrayList<ENode>()]
    : a (e { $list.add(e.ast) })* b   { $ast = new NNode($a.ast, $list, $b.ast); };

e returns [ENode ast]: ...

La versión 0+cs sería:

n returns [NNode ast]
  locals[List<ENode> list = new ArrayList<ENode>()]
    : a (e { $list.add($e.ast); } (',' e { $list.add($e.ast); })*)? b
        { $ast = new NNode($a.ast, $list, $b.ast); };

e returns [ENode ast]: ...

Consideraciones de esta opción:

• Si la regla n tuviera más hijos con repeticiones o bien más alternativas (n: ...|...) en las que también hubiera hijos con repeticiones, se complicaría la sección locals al tener que definir listas para cada uno de estos hijos.
• El requerir la cláusula locals e insertar una acción en mitad de la regla ($list.add(...)), añade cierto ruido que dificulta identificar la esencia de la regla (el a e* b). Este ruido aumentaría si hubiera más hijos con repeticiones (en la misma regla o en alternativas) y, especialmente, en el caso de la versión con separadores.

Operador '+=' #

En los casos anteriores se tenía que hacer el código que metiera los elementos en la lista uno a uno. Sin embargo, como ya se ha visto anteriormente, se le puede decir a ANTLR4, con el operador '+=', que haga la lista y meta los elementos automáticamente (los contextos de los hijos). Solo quedaría recorrer dicha lista de contextos y extraer el valor del atributo ast de cada uno.

La versión 0+ss con esta solución quedaría así:

n returns [NNode ast]
    : a v+=e* b
        {   List<ENode> list = new ArrayList<ENode>();
            for (ExprContext ctx : $v)      // $v es una 'List<ParserRuleContext>'
                list.add(ctx.ast);
            $ast = new NNode($a.ast, list, $b);
        }

e returns [ENode ast]: ...

El operador '+=' tiene la ventaja de que la regla, en vez de estar entre los símbolos de la gramática, va al final de la misma permitiendo una lectura más sencilla de la misma.

Sin embargo, si se opta por esta opción, es más limpio todavía incorporar el bucle for anterior dentro de un constructor de NNode (es decir, que , además del constructor que admita como parámetro una List<NNode>, haya otro que admita una List<ParserRuleContext> e implemente dicho for). Así se conseguiría la gramática más limpia posible:

n returns [NNode ast]
    : a v+=e* b   { $ast = new NNode($a.ast, $v, $b.ast); }

Si se usa VGen, se obtendrán constructores en todos los nodos que hacen automáticamente este proceso (ver Tutorial).

La versión 0+cs sería:

n returns [NNode ast]
    : a (v+=e (',' v+=e)*)? b   { $ast = new NNode($a.ast, $v, $b); }

Lo siguiente es un ejemplo de la aplicación de esta solución a una regla (start) que tiene dos hijos que se pueden repetir 0+ss (variable y sentence):

start returns[Program ast]
	: 'DATA' vv+=variable* 'CODE' vs+=sentence* EOF { $ast = new Program($vv, $vs); }
	;

variable returns[VarDefinition ast]
	: tipo IDENT ';' { $ast = new VarDefinition($tipo.ast, $IDENT.text); }
	;

sentence returns[Sentence ast]
	: 'print' expr ';'	{ $ast = new Print($expr.ast); }
	| l=expr '=' r=expr ';'	{ $ast = new Assignment($l.ast, $r.ast); }
	;

Consideraciones de esta opción:

• Es la solución que requiere menos reglas, ya que, de las construcciones básicas, solo quedarán las secuencias y las composiciones (no habrá reglas para expresar listas).
• Permite unas reglas más limpias al tener todo el código Java al final de las mismas (y no intercaladas entre los símbolos).
• El usar la versión de 0+cs, al contrario de lo que ocurre con las demás soluciones, apenas oscurece la regla, siendo la versión más compacta de todas.
• El inconveniente es que requiere añadir, en el constructor del nodo AST, el bucle que extraiga los nodos hijos de la lista de contextos. Sin embargo, si se usa VGen, ese código ya se genera automáticamente.

Por todo ello, esta es la solución recomendada si se utiliza VGen debido a lo compacta que queda la gramática.

Caso 2. Repetición en el Hijo #

Si la repetición se indica en el hijo, se tienen los dos siguientes casos en función de que sea 0+ss o 0+cs.

// Versión de lista 0+ss
n: a e b
e: (x y z)*

// Versión de lista 0+cs
n: a e b
e: (x y z (',' x y z)*)?

En este caso, la única opción es que el símbolo e devuelva ya una List<ENode>.

La versión 0+ss sería:

n returns [NNode ast]
    : a e b   { $ast = new NNode($a.ast, $e.list, $b.ast); }

e returns [List<ENode> list = new ArrayList<Enode>()]
    : (x y z { $list.add(new ENode($x.ast, $y.ast, $z.ast)); } )*

Ejemplo de aplicación de esta solución:

structDeclaration returns[DefinicionStruct ast]
	: 'struct' IDENT '{' fields '}' ';' { $ast = new StructDef($IDENT, $fields.list); }
	;

fields returns[List<Campo> list = new ArrayList<Campo>()]
	: (IDENT ':' type ';' { $list.add(new Campo($IDENT, $type.ast)); })*
	;

Supongase ahora que la regla e tuviera alternativas:

e: x y z | h j m | q w e

En este caso, la solución actual se aplicaría asi:

n returns [NNode ast]
    : a e b   { $ast = new NNode($a.ast, $e.list, $b.ast); }

e returns [List<ENode> list = new ArrayList<Enode>()]
    : (
        x y z { $list.add(new ENode($x.ast, $y.ast, $z.ast)); }
        | h j m { $list.add(new ENode($h.ast, $j.ast, $m.ast)); }
        | q w e { $list.add(new ENode($q.ast, $w.ast, $e.ast)); }
      )*

Ejemplo de aplicación de esta solución:

start returns[Programa ast]
	: declarations EOF { $ast = new Programa($declarations.list); }
	;

declarations returns[List<Definicion> list = new ArrayList<Definicion>()]
	: (
		structDeclaration		{ $list.add($structDeclaration.ast); }
		| globalVarDefinition	{ $list.add($globalVarDefinition.ast); }
		| functionDefinition	{ $list.add($functionDefinition.ast);}
	)*;

La versión 0+cs sería, volviendo a la versión original en la que e tenía sólo una alternativa, la siguiente:

n returns [NNode ast]
    : a e b   { $ast = new NNode($a.ast, $e.list, $b.ast); }

e returns [List<ENode> list = new ArrayList<Enode>()]
    : (x y z { $list.add(new ENode($x.ast, $y.ast, $z.ast)); }
     (',' x y z { $list.add(new ENode($x.ast, $y.ast, $z.ast)); })* )?

La versión 0+cs para e con varias alternativas no se incluye porque sería realmente confusa y se descarta directamente.

Consideraciones finales de la opción de expresar la repetición en el hijo:

• Esta solución es aplicable sólo si e es siempre usado como parte de una repetición, ya que el símbolo e lleva incorporado el '*' (es decir, otra regla no puede usar e si quiere un solo elemento).
• En esta solución la regla e mezcla tanto la propia definición de e (construcción secuencia) con la construcción lista. Como se muestra en el apéndice de estilo en gramáticas, mezclar construcciones no es recomendable ya que, como puede comprobarse especialmente en la versión 0+cs, resulta en código repetido y definiciones recargadas. Es por ello que esta solución no es práctica en la versión con separadores.

Caso 3. Regla Intermedia #

Esta es la solución que se ha propuesto en el capítulo de creacion de listas en EBNF como recomendación para la asignatura.

Si se introduce una regla intermedia que se encarga de expresar la repetición, se tienen los dos siguientes casos en función de que sea 0+ss o 0+cs.

// Versión de lista 0+ss
n: a es b
es: e*
e: ...

// Versión de lista 0+cs
n: a es b
es: (e (',' e)*)?
e: ...

La implementación para 0+ss sería:

n returns [NNode ast]
    : a es b   { $ast = new NNode($a.ast, $es.list, $b.ast); }

es returns [List<ENode> list = new ArrayList<Enode>()]
    : (e { $list.add($.ast); })*

e returns [ENode ast]: ...  { $ast = new ENode(...); }

Ejemplo de aplicación de esta solución:

start returns[Programa ast]
	: declarations EOF { $ast = new Programa($declarations.list); }
	;

declarations returns[List<Definicion> list = new ArrayList<Definicion>()]
	: (declaration { $list.add($declaration.ast);})*
	;

declaration returns[Definicion ast]
	: structDeclaration     { $ast = $structDeclaration.ast; }
	| globalVarDefinition	{ $ast = $globalVarDefinition.ast; }
	| functionDefinition	{ $ast = $functionDefinition.ast; }
	;

La versión 0+cs sería:

es returns [List<ENode> list = new ArrayList<Enode>()]
    : (e { $list.add($.ast); } (',' e { $list.add($.ast); })*)?

Consideraciones de esta solución:

• Esta solución es la que más desacopla el tipo de repetición usado (de cero/uno y con/sin separadores) de las reglas padre e hija (n y e). Facilmente permitiría pasar de un tipo de repetición a otro sin afectar al resto de las reglas (ni n ni e tendrian que ser modificadas).
• Tanto la regla n como la e quedan lo más limpias posibles (con una sola acción y al final de la regla). En general, con esta solución, toda regla que no sea una regla de lista tendrá una sola acción y al final. Sólo las reglas de listas tendrán acciones dentro de la regla (entre sus símbolos y operadores).
• Como resultado de lo anterior, esta solución facilita la comprensión de la gramática. Al ser las reglas intermedias para repetición las únicas que no tienen la acción al final, a la hora de estudiar la gramática, son fáciles de identificar e ignorar, centrándose así en las reglas relevantes de la misma (las que tienen la acción al final).
• Esta solución es la que más se parecería a una realizada en notación BNF. Para pasar de BNF a EBNF y viceversa solo habría que cambiar estas reglas intermedias. No habría que tocar las otras reglas.
• Sin embargo, el inconveniente obvio de esta solución es que hace que crezca el número de reglas de la gramática (tantas como construcciones lista haya). Sin embargo, como se comentó en el punto 3, estas reglas son fáciles de identificar e ignorar en la lectura de una gramática.

Caso 4. Repetición con Opcionalidad #

Como se adelantó a la hora de presentar los casos, en el caso particular de las repeticiones 0+cs, se presentan dos formas de combinar los operadores '*' y '?'.

• Que ambos operadores vayan juntos en la misma regla.

  n: a es b es: (e (s e)*)? // Aquí el '*' y el '?' e: x y z

• Que vayan separados en reglas distintas.

  n: a es? b // Aquí sólo el '?' es: e (s e)* // Aquí sólo el '*' e: x y z

El primer caso ya se ha estudiado anteriormente, ya que es la opción recomendada de usar regla intermedia.

La segunda solución no se recomienda por los siguientes motivos:

• La construcción repetición queda dispersa entre las dos reglas. Se recomienda que sólo una regla se encarga de expresar el tipo de repetición necesario (si es 0+cs, que se vea directamente en una sola regla y no crear una regla 1+cs para luego hacerla opcional en otro sitio).
• Se complica la acción que crea el NNode en n. Dado que es? es opcional, si este no aparece a la entrada, el contexto de $es sería null y por tanto acceder a $es.list produciría un NullPointerException. Por tanto, la acción se complicaría ya que habría que contemplar dicho caso usando un if antes de acceder al retorno de la regla es. Para mas información sobre esto, ver opcionalidad en no-terminales.

Comparativa y Conclusiones #

Siguiendo lo recomendado en el apéndice de estilo en gramáticas, a la hora de recomendar una opción, se tendrán en cuenta los objetivos de:

• Minimizar el número de reglas de la gramática.
• Maximizar la limpieza de las reglas. Una regla será más dificil de leer cuantas más acciones Java tenga y, especialmente, si están entre los símbolos de la regla.

Por ello, si se usa VGen, se recomienda usar la solución con el operador '+='. Es la única solución que consigue los dos objetivos a la vez:

• El menor número de reglas posibles en la gramática (no hay reglas auxiliares para las listas).
• La mayor limpieza en las acciones, ya que cada regla sólo tendrá una acción (el new) y estará al final de la misma (lo que facilita la comprensión de la gramática).

Si no se usa VGen (y no se quiere hacer en los constructores el código equivalente a mano), se recomienda la opción de introducir regla intermedia. Tiene inconvenientes frente a la solucion anterior:

• Requiere mayor número de reglas (añade tantas reglas como listas haya).
• No consigue tanta limpieza en las reglas (las reglas de las listas tendrán acciones entre los símbolos)

Sin embargo, es una solución sencilla de implementar y con una limpieza aceptable, ya que las reglas que sean secuencias y composiciones — que son las reglas importantes — sí tendrán una sola acción y al final de la regla.

El resto de las soluciones estudiadas no se recomiendan debido a que no consiguen alcanzar en la misma medida alguno o los dos objetivos anteriores:

• En cuanto a poner la repetición en el padre:
  • La opción de insertar los hijos individualmente no se recomienda, ya que requiere meter cada hijo por separado (incluso los que no se repiten). No vale, además, si el padre tiene varias reglas que requieran devolver distintos tipos de objetos.
  • La opción de usar una lista local tampoco se recomienda, ya que produce reglas que, al menos, necesitarán dos acciones, lo cual producirá reglas menos limpias que con otras opciones.
• En cuanto a la opción de repetición en el hijo, no se recomienda por la poca limpieza que se obtiene en las reglas. Mezcla las definiciones de los elementos con la construcción de la lista. Sólo sería planteable si la repetición fuera sin separadores y si e no se usara en ningún otro sitio individualmente.