¿Cómo generar el AST construido utilizando ANTLR?

Estoy haciendo un analizador estático para C. He hecho el analizador y el analizador usando ANTLR en el cual se genera código Java.

¿ANTLR construye el AST para nosotros automáticamente por options {output=AST;} ? ¿O tengo que hacer el árbol yo mismo? Si lo hace, ¿cómo escupir los nodos en ese AST?

Actualmente estoy pensando que los nodos en ese AST se usarán para hacer SSA, seguido de análisis de flujo de datos para hacer el analizador estático. ¿Estoy en el camino correcto?

Raphael escribió:

¿Antlr construye el AST para nosotros automáticamente por la opción {output = AST;}? ¿O tengo que hacer el árbol yo mismo? Si lo hace, ¿cómo escupir los nodos en ese AST?

No, el analizador no sabe lo que quiere como raíz y como hojas para cada regla del analizador, por lo que tendrá que hacer un poco más que simplemente poner options { output=AST; } options { output=AST; } en tu gramática.

Por ejemplo, al analizar la fuente "true && (false || true && (true || false))" utilizando el analizador generado a partir de la gramática:

 grammar ASTDemo; options { output=AST; } parse : orExp ; orExp : andExp ('||' andExp)* ; andExp : atom ('&&' atom)* ; atom : 'true' | 'false' | '(' orExp ')' ; // ignore white space characters Space : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ; 

el siguiente árbol de análisis sintáctico se genera:

enter image description here

(es decir, solo una lista plana, 1 dimensión de tokens)

Querrá decirle a ANTLR qué símbolos en su gramática se convierten en raíz, hojas o simplemente quedan fuera del árbol.

La creación de AST se puede hacer de dos maneras:

  1. utilice reglas de reescritura que se vean así: foo : ABCD -> ^(DAB); , donde foo es una regla de analizador que coincide con los tokens ABCD . Entonces, todo después de -> es la regla de reescritura real. Como puede ver, el token C no se usa en la regla de reescritura, lo que significa que se ha omitido del AST. La ficha colocada directamente después de ^( se convertirá en la raíz del árbol;
  2. usa los operadores de árbol ^ y ! después de un token dentro de las reglas del analizador, donde ^ convertirá un token en la raíz, y ! eliminará un token del árbol. El equivalente de foo : ABCD -> ^(DAB); sería foo : ABC! D^; foo : ABC! D^;

Ambos foo : ABCD -> ^(DAB); y foo : ABC! D^; foo : ABC! D^; producirá el siguiente AST:

enter image description here

Ahora, puedes reescribir la gramática de la siguiente manera:

 grammar ASTDemo; options { output=AST; } parse : orExp ; orExp : andExp ('||'^ andExp)* // Make `||` root ; andExp : atom ('&&'^ atom)* // Make `&&` root ; atom : 'true' | 'false' | '(' orExp ')' -> orExp // Just a single token, no need to do `^(...)`, // we're removing the parenthesis. Note that // `'('! orExp ')'!` will do exactly the same. ; // ignore white space characters Space : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ; 

que creará la siguiente AST a partir de la fuente "true && (false || true && (true || false))" :

enter image description here

Enlaces relacionados a ANTLR wiki:

  • Construcción de árbol
  • Análisis de árbol
  • Instalaciones de construcción de árboles

Raphael escribió:

Actualmente estoy pensando que los nodos en ese AST se usarán para hacer SSA, seguido de análisis de flujo de datos para hacer el analizador estático. ¿Estoy en el camino correcto?

Nunca hiciste algo así, pero IMO lo primero que querrías es un AST de la fuente, así que sí, ¡creo que estás en el camino correcto! 🙂

EDITAR

A continuación, le mostramos cómo puede usar el analizador y el analizador generados:

 import org.antlr.runtime.*; import org.antlr.runtime.tree.*; import org.antlr.stringtemplate.*; public class Main { public static void main(String[] args) throws Exception { String src = "true && (false || true && (true || false))"; ASTDemoLexer lexer = new ASTDemoLexer(new ANTLRStringStream(src)); ASTDemoParser parser = new ASTDemoParser(new CommonTokenStream(lexer)); CommonTree tree = (CommonTree)parser.parse().getTree(); DOTTreeGenerator gen = new DOTTreeGenerator(); StringTemplate st = gen.toDOT(tree); System.out.println(st); } } 
    Intereting Posts