una - Tutorial para caminar ANTLR ASTs en C#?

tips para caminar

Question

¿Alguien está al tanto de los tutoriales para caminar AST generados por ANTLR en C #? Lo más cercano que pude encontrar es this , pero no es de mucha ayuda.

Mi objetivo es recorrer los árboles que estoy generando en base a un lenguaje específico del dominio en el que estoy trabajando y usar los árboles para generar el código C # generado.

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

Answer 1

Debes mirar en escribir un TreeParser; Puede hacer que el trabajo de interpretación del árbol sea mucho más simple.

Para ANTLR 2.x vea http://www.antlr2.org/doc/sor.html Para ANTLR 3.x vea http://www.antlr.org/wiki/display/ANTLR3/Tree+construction (basado en java Ejemplo de analizador y analizador de árbol)

Answer 2

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

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

Answer 3

Logré resolver esto adaptando el ejemplo al final del artículo de Manuel Abadia .

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

1. Cree una instancia de ANTLRStringStream o una subclase con su entrada (puede ser un archivo o una cadena).
2. Cree una instancia de su lexer generado, pasando esa secuencia de cadena.
3. Crear una instancia 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 CommonTree en un CommonTree .
6. Atraviesa el árbol:

Para obtener el texto literal de un nodo, use 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 es un token imaginario sin la cadena correspondiente. Si es un token real, entonces node.Token.Text devolverá su cadena.

Por ejemplo, si tienes lo siguiente en tu gramática:

tokens { PROGRAM, FUNCDEC }

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

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

Puede ver parte de mi ejemplo a continuación, o puede navegar por la versión completa .

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 4

Normalmente, usted camina AST con recursión 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 puede ser apropiado realizar un doble despacho en el patrón de visitante; sin embargo, eso no suele ser muy conveniente con Antlr.

En pseudocódigo, el caminar usualmente se ve algo así:

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 en gran medida de la semántica del lenguaje. Por ejemplo, el manejo de una instrucción IF , con estructura (IF <predicate> <if-true> [<if-false>]) , al generar código para una máquina de pila como JVM o CLR, puede verse algo 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 realiza de forma recursiva según el tipo de nodo actual, etc.