Tutorial para caminar ANTLR ASTs en C#?

Question

¿Alguien conoce los tutoriales para caminar AST generados por ANTLR en C#? Lo más cerca que pude encontrar es this, pero no es terriblemente útil.

Mi objetivo es recorrer los árboles que estoy generando en función de un lenguaje de dominio específico en el que estoy trabajando y utilizar los árboles para generar el código C# generado.

Un tutorial basado en Java sería útil también, cualquier cosa que proporcione ejemplos claros de cómo atravesar ANTLR AST.

Answer 1

Logré resolver esto adaptando el ejemplo al final de Manuel Abadia's article.

Aquí está mi versión, que estoy usando para convertir el código analizado a C#. Estos son los pasos:

1. una instancia de un ANTLRStringStream o subclase con su entrada (que puede ser un archivo o una cadena).
2. Crea una instancia de tu lexer generado, pasando esa secuencia de cadenas.
3. Cree una secuencia de token con el lexer.
4. Crea una instancia de tu analizador con esa secuencia de token.
5. Obtenga el valor de nivel superior de su analizador y conviértalo en CommonTree.
6. recorrer el árbol:

Para obtener el texto literal de un nodo, utilice node.Text. Para obtener el nombre del token de un nodo, use node.Token.Text.

Tenga en cuenta que node.Token.Text solo le dará el nombre real de su token si se trata de un token imaginario sin la cadena correspondiente. Si es un token real, entonces node.Token.Text devolverá su cadena.

Por ejemplo, si usted tenía lo siguiente en su gramática:

tokens { PROGRAM, FUNCDEC } 

EQUALS : '=='; 
ASSIGN : '='; 

entonces obtendrá "PROGRAM", "FUNCDEC", "==" y "=" partir de los correspondientes accesos de node.Token.Text.

Puede ver parte de mi ejemplo a continuación, o puede navegar por el full version.

---

public static string Convert(string input) 
{ 
    ANTLRStringStream sStream = new ANTLRStringStream(input); 
    MyGrammarLexer lexer = new MyGrammarLexer(sStream); 

    CommonTokenStream tStream = new CommonTokenStream(lexer); 

    MyGrammarParser parser = new MyGrammarParser (tStream); 
    MyGrammarParser.program_return parserResult = parser.program(); 

    CommonTree ast = (CommonTree)parserResult.Tree; 

    Print(ast); 
    string output = header + body + footer; 

    return output; 
} 

public static void PrintChildren(CT ast) 
{ 
    PrintChildren(ast, " ", true); 
} 

public static void PrintChildren(CT ast, string delim, bool final) 
{ 
    if (ast.Children == null) 
    { 
     return; 
    } 

    int num = ast.Children.Count; 

    for (int i = 0; i < num; ++i) 
    { 
     CT d = (CT)(ast.Children[i]); 
     Print(d); 
     if (final || i < num - 1) 
     { 
      body += delim; 
     } 
    } 
} 

public static void Print(CommonTree ast) 
{ 
    switch (ast.Token.Text) 
    { 
     case "PROGRAM": 
      //body += header; 
      PrintChildren(ast); 
      //body += footer; 
      break; 
     case "GLOBALS": 
      body += "\r\n\r\n// GLOBALS\r\n"; 
      PrintChildren(ast); 
      break; 
     case "GLOBAL": 
      body += "public static "; 
      PrintChildren(ast); 
      body += ";\r\n"; 
      break; 

     .... 
    } 
} 

Answer 2

Normalmente recorre los AST con recursividad y realiza diferentes acciones según el tipo de nodo. Si está utilizando nodos de árbol polimórficos (es decir, diferentes subclases para diferentes nodos en el árbol), entonces el doble envío en el patrón de visitante puede ser apropiado; sin embargo, eso generalmente no es muy conveniente con Antlr.

En pseudocódigo, caminar por lo general se ve algo como esto:

func processTree(t) 
    case t.Type of 
     FOO: processFoo t 
     BAR: processBar t 
    end 

// a post-order process 
func processFoo(foo) 
    // visit children 
    for (i = 0; i < foo.ChildCount; ++i) 
     processTree(foo.GetChild(i)) 
    // visit node 
    do_stuff(foo.getText()) 

// a pre-order process 
func processBoo(bar) 
    // visit node 
    do_stuff(bar.getText()) 
    // visit children 
    for (i = 0; i < foo.ChildCount; ++i) 
     processTree(foo.GetChild(i)) 

Los tipos de procesamiento dependen de la semántica del lenguaje altamente. Por ejemplo, el manejo de una declaración IF, con la estructura (IF <predicate> <if-true> [<if-false>]), cuando se genera código para una máquina de pila como la JVM o CLR, podría ser algo así como esto:

func processIf(n) 
    predicate = n.GetChild(0) 
    processExpr(predicate) // get predicate value on stack 
    falseLabel = createLabel() 
    genCode(JUMP_IF_FALSE, falseLabel) // JUMP_IF_FALSE is called brfalse in CLR, 
             // ifeq in JVM 
    if_true = n.GetChild(1) 
    processStmt(if_true) 
    if_false = n.ChildCount > 2 ? n.GetChild(2) : null 
    if (if_false != null) 
     doneLabel = createLabel() 
     genCode(JUMP, doneLabel) 
    markLabel(falseLabel) 
    if (if_false != null) 
     processStmt(if_false) // if-false branch 
     markLabel(doneLabel) 

En general todo se hace de forma recursiva en función del tipo de la corriente nodo, etc.

Answer 3

Debería buscar escribir un TreeParser; puede simplificar el trabajo de interpretación del árbol.

Para 2.x ANTLR ver http://www.antlr2.org/doc/sor.html Para ver 3.x ANTLR (analizador y el analizador de árboles ejemplo en java) http://www.antlr.org/wiki/display/ANTLR3/Tree+construction

Answer 4

hice algo similar (pero no realmente) y terminé con un TreeParser.

También sugiero comprar el libro ANTLR. Me pareció más valioso que cualquier recurso web. Puede que no tenga todas las respuestas pero seguro que ayuda con lo básico.