Creación del AST #

Una vez que ya están implementados todos los nodos, ya se puede crear el AST, es decir, ya se pueden hacer los new de las clases creadas en el capítulo anterior.

Dónde crear los Nodos #

Crear el AST implica hacer los new de los distintos nodos del árbol en algún punto del analizador sintáctico. Se trata ahora de determinan dichos puntos.

El AST debe reflejar lo que se ha ido encontrando en la entrada ¿Cuándo se querrá crear, por ejemplo, un nodo que represente a una sentencia print? Pues después de haber encontrado todos los símbolos de dicha estructura en la entrada.

En la imagen anterior, se querrá crear el nodo Print después de que se haya encontrado en la entrada el punto y coma que finaliza la construcción — es decir, después del match(';').

Creación de Nodos en parser Manual #

Si el parser se implementa de manera manual (por ejemplo, de manera recursiva descendente), bastaría con añadir el new detrás de dicho match(';').

// print ⟶ PRINT expr ';'

Sentence print() {
    match(PRINT);
    Expresion e = expr();
    match(';');

    return new Print(e);
}

Cosas a destacar:

• Cada función debe devolver el subárbol que corresponda con la estructura encontrada. En este caso, dado que el método reconoce sentencias print, el return devuelve un nodo Print.
• Nótese cómo se enlazan los nodos padres con los hijos. De nuevo, como cada función devuelve su subárbol, lo habitual será que lo que devuelvan los hijos (en este caso e = expr()) sean los parámetros del constructor del padre (new Print(e)).

Creación de Nodos en ANTLR #

Cuando se implementa un parser con una herramienta, hay que utilizar la forma particular que tenga dicha herramienta para obtener el código equivalente a la versión manual anterior.

En este apartado se verá, para el caso concreto de ANTLR, cómo se hacen las siguientes tareas:

• Cómo insertar código (acciones) dentro de la especificación ANTLR (para que quede en el lugar equivalente a la versión manual).
• Cómo se enlazan los nodos padres e hijos en dicha herramienta.

Insertar Acciones #

Hasta ahora, en ANTLR se han utilizado dos tipos de símbolos para formar las reglas: terminales y no-terminales. Sin embargo, admite también un tercer tipo de símbolo: las acciones. Una acción no es más que código Java entre llaves.

instr: 'A' { f(); } 'B' { g(); } ;

A diferencia de los otros dos tipos de símbolos, las acciones no producen ningún efecto sobre el proceso de reconocimiento. Simplemente se ejecutan cuando se hayan reconocido todos los símbolos que las precedan en la regla. En el caso anterior, quedaría algo parecido a:

instr() {
    ...
    match('A');
    f();
    match('B');
    g();
    ...
}

Aunque, como se ha visto, se pueden poner acciones entre los símbolos de una regla, se recomienda usarlo lo menos posible, ya que esto dificulta su lectura. Es preferible, siempre que sea posible, poner las acciones al final de las reglas.

Además, en las acciones se pueden poner tanto código java como se quiera, pudiendo incluso extenderse por más de una línea.

instr: 'A' 'B' { f();
                 g(); };

Enlazar Nodos #

Usando acciones ya se podría ubicar el new adecuado de cada nodo. Sin embargo, queda el problema de cómo enlazar padres e hijos.

Para ello, hay que ver definir dos aspectos:

• Cómo devolver valores en las reglas.
• Cómo obtener valores de los hijos.

Es decir, habría que determinar qué se pone en lugar de los puntos suspensivos en los dos huecos de este ejemplo:

print: PRINT expr ';' { ... = new Print(...); } ;

Devolución de Valores #

En este apartado se mostrará qué hay que poner en los puntos suspensivos de la izquierda del ejemplo anterior (dónde se está dejando el nodo creado).

Se ha comentado anteriormente que cada regla debe devolver el subárbol que represente la entrada que ha reconocido. Por tanto, hay que indicar en ANTLR qué nodo devuelve cada regla/función. Esto se hace usando la directiva returns antes de los dos puntos de la regla.

print returns[Print ast]
	: 'print' expr ';' { $ast = new Print(...); }
	;

expr returns[Expresion ast]
	: ...
	;

La directiva returns sirve para dos cosas:

1. Para indicar el tipo de retorno que debe tener el método que ANTLR implemente a partir de dicha regla.
2. Para crear una variable (en este caso ast) donde las acciones podrán dejar el valor de retorno de la función (ya que no pueden usar la sentencia return de Java). Para usar esta variable en las acciones, ANTLR exige prefijar su nombre con el carácter $ (por eso en la acción se asigna a $ast).

Por ejemplo, ante las reglas anteriores definidas con returns, ANTLR generaría un código equivalente al siguiente:

Print print() {     // 1. Tipo de retorno
    Print ast;      // 2. Variable donde dejar el valor de retorno
    ...
    ast = new Print(...)
    ...
    return ast;
}

Expresion expr() { ... }

Aunque se puede poner cualquier nombre a la variable de retorno definida con returns, en este texto se seguirá el siguiente convenio:

• Llamarla ast cuando sea un subárbol, es decir, un nodo que implemente el interfaz AST.
• Llamarla list cuando sea una lista de cualquier tipo.
• Llamarla val (de valor) cuando sea cualquier otro valor (un string, un entero, un objeto que no sea un nodo,. ..).

Por último, comentar que la variable de retorno se puede inicializar en la definición y, si no se asigna otro valor en una acción, este será el valor que devuelva la regla.

a returns[String s = "hola"]
	: ... ;

Obtención de Valores #

Ahora que ya se ha averiguado qué había que poner en los primeros puntos suspensivos ($ast), queda ahora indicar qué hay que poner en los puntos suspensivos que quedan a la derecha: cómo obtener el valor de los hijos para pasarlos en el constructor.

print returns[Print ast]
	: 'print' expr ';' { $ast = new Print(...); }
	;

Se va a ver primero el caso en el que los hijos sean no-terminales, que es el caso que se plantea en el fragmento anterior. En dicho caso, para crear el Print, se querría obtener el subárbol que se formó con su hijo expr. Para obtenerlo, hay que usar la siguiente notacion:

$<hijo>.<variable de su returns>

La parte <variable de su returns> se refiere a la variable que se haya definido con returns en dicho hijo (en este caso, y siempre si se sigue el convenio anterior, es ast).

print returns[Print ast]
	: 'print' expr ';' { $ast = new Print($expr.ast); }
	;

expr returns[Expresion ast]
	: ... { $ast = ... }
	;

Si los hijos son terminales (tokens), se usa la notación $<hijo> para obtener su objeto Token (y, por tanto, se pueden invocar sobre el valor devuelto todos los métodos de esta clase).

a: IDENT { System.out.println($IDENT); } // Objeto `Token`

b: IDENT { System.out.println($IDENT.getText()); } // Lexema del token

Dado que el método Token.getText() será usado habitualmente para obtener el lexema del token, ANTLR permite el atajo de poner $<hijo>.text y él lo sustituirá por $<hijo>.getText().

a: IDENT { System.out.println($IDENT.text); } // Equivale a `$IDENT.getText()`

Etiquetas #

Si un símbolo aparece varias veces en la regla, al usar su nombre sólo se accederá al último de ellos.

a: IDENT IDENT { System.out.println($IDENT); } // Imprime el último IDENT!!

Para poder diferenciar los distintos símbolos de la regla, lo más sencillo es etiquetarlos con nombres, los cuales se podrán usar en las acciones para identificarlos. Para etiquetar un símbolo, basta con poner un nombre seguido de un '=' antes de dicho símbolo.

a: id1=IDENT id2=IDENT { System.out.println($id1); } // Primer IDENT

Aunque en el ejemplo anterior se han usado tokens, se pueden etiquetar igualmente los símbolos no-terminales (de hecho, será lo más común).