Creación de Listas en EBNF #

En EBNF hay varias formas de expresar la repetición de elementos. Por ejemplo, las dos gramáticas equivalentes siguientes:

n: a e* b
e: ...

n: a e b
e: (...)*

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 capítulo se hará una recomendación de cómo expresar las listas en EBNF, es decir, dónde poner los operadores '*' y '+', y se verá qué acciones Java hay que incrustar para crear y agrupar los nodos.

Esta recomendación es sólo una de las múltiples formas de hacerlo. Si se tiene interés en ver otras, en el apéndice IV se estudian y comparan todas ellas. Esta recomendación surge, precisamente, de las conclusiones de dicho apéndice. Concretamente, la solución aquí propuesta es la que se corresponde con el caso 3, introducir regla intermedia.

Forma de las Reglas #

Anteriormente se habían visto los patrones para crear repeticiones en GLC. Los patrones en EBNF eran los siguientes.

Es aconsejable que cada regla siga solo una de las construcciones, por lo que se va a suponer que los operadores '*' y '+' siempre van en reglas con la estructura de la tabla anterior, es decir, que no se van a usar en otro tipo de reglas.

Por ejemplo, en el siguiente ejemplo se tiene una regla en las que hay una lista en mitad de una secuencia:

a ⟶ δ  b*  μ            // 0+ss dentro de una secuencia

En estos casos, se aconseja que las listas se separen a sus propias reglas auxiliares que tengan el formato exacto de uno de los patrones. En este caso, se crearía la regla auxiliar lb de la siguiente manera:

a ⟶ δ  lb  μ
lb ⟶ b*            // 0+ss en regla independiente

Otro ejemplo de construcciones mezcladas sería este:

f ⟶ δ  e (',' e)*  μ    // 1+cs dentro de una secuencia

La recomendación sería añadir la regla auxiliar le que sigue únicamente el patrón 1+cs.

f ⟶ δ  le  μ
le ⟶ e (',' e)*    // 1+cs en regla independiente

Acciones en los Patrones #

Una vez que tenemos aisladas las reglas que implementan los patrones, a la hora de crear los nodos de un AST, ¿qué acciones Java hay que añadir a dichas reglas-patrones? En la siguiente tabla se muestra qué acciones hay que añadir y dónde en función del patrón que representa la regla:

Aparte de esta solución de usar regla intermedia, otra opción más compacta y cómoda es utilizar el operador '+=' de ANTLR. Sin embargo, esa opción se dejará para el estudio y aplicación voluntaria del alumno.

Ejemplo 0580 #

Enunciado #

Dada la gramática en ANTLR y la gramática abstracta siguientes, añadir al fichero de ANTLR las acciones que construyan el AST.

start
    : sentences EOF
    ;

sentences
    : sentence*
    ;

sentence
    : 'print' expr ';'
    | left=expr '=' right=expr ';'
    ;

expr
    : left=expr op=('*' | '/') right=expr
    | left=expr op=('+' | '-') right=expr
    | '(' expr ')'
    | IDENT
    ;

program → sentences:sentence*;

print:sentence → expression;
assignment:sentence → left:expresión right:expression;

arithmetic:expression → left:expresión operator:string right:expression;
variable:expression → name:string;

Solucion #

La solución sería la siguiente.

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

sentences returns[List<Sentence> list = new ArrayList<Sentence>()]
	: (sentence { $list.add($sentence.ast); })*
	;

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

expr returns[Expression ast]
	: left=expr op=('*' | '/') right=expr	{ $ast = new Arithmetic($left.ast, $op.text, $right.ast); }
	| left=expr op=('+' | '-') right=expr	{ $ast = new Arithmetic($left.ast, $op.text, $right.ast); }
	| '(' expr ')'							{ $ast = $expr.ast; }
	| IDENT									{ $ast = new Variable($IDENT.text); }
	;

A destacar:

• En sentences se ha usado una lista tal y como se ha mencionado en este apartado (concretamente, el patrón 0+ss).
• Nótese que la regla '(' expr ')' no crea un nuevo nodo, sino que se limita a dejar pasar el nodo de la expresión.