Tutorial do chodzenia ANTLR ASTs w C#?

Czy ktoś zna tutoriale do chodzenia po astach generowanych przez ANTLR w C#? Najbliższe, które udało mi się znaleźć, to to , ale nie jest to zbyt pomocne.

Moim celem jest przechodzenie przez drzewa, które generuję w oparciu o język domenowy, nad którym pracuję, i wykorzystanie drzew do generowania wygenerowanego kodu C#.

Pomocny byłby również samouczek oparty na Javie -- wszystko, co dostarcza jasnych przykładów jak przemierzać ASTs ANTLR.

Author: kpozin, 2009-05-20

4 answers

Udało mi się to rozgryźć, dostosowując przykład na końcu artykułu Manuela Abadia .

Oto moja wersja, której akurat używam do konwersji parsowanego kodu do C#. Są to kroki:

  1. tworzy instancję ANTLRStringStream lub podklasę ze swoim wejściem (może to być plik lub łańcuch znaków).
  2. Utwórz instancję wygenerowanego lexera, przechodzącego w tym strumieniu łańcuchowym.
  3. utworzenie strumienia tokena z lexer.
  4. Utwórz instancję parsera z tym strumieniem tokena.
  5. Pobierz wartość najwyższego poziomu z parsera i przekształć ją w CommonTree.
  6. Trawers drzewa:

Aby uzyskać dosłowny tekst węzła, użyj node.Text. Aby uzyskać tokenową nazwę węzła, użyj node.Token.Text.

Zauważ, że node.Token.Text poda ci rzeczywistą nazwę Twojego tokenu tylko wtedy, gdy jest to urojony token bez odpowiadającego mu ciągu znaków. Jeśli jest to prawdziwy token, to node.Token.Text zwróci jego ciąg znaków.

Dla przykład, jeśli w gramatyce masz następujące zdanie:

tokens { PROGRAM, FUNCDEC }

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

Wtedy dostaniesz "PROGRAM", "FUNCDEC", "==", i {[10] } z odpowiednich dostępów node.Token.Text.

Możesz zobaczyć część mojego przykładu poniżej, lub możesz przeglądać pełna wersja.


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;

      ....
    }
}
 19
Author: kpozin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-29 19:06:09

Normalnie chodzisz z rekurencją i wykonujesz różne czynności w zależności od rodzaju węzła. Jeśli używasz polimorficznych węzłów drzewa (tj. różnych podklas dla różnych węzłów w drzewie), Podwójna wysyłka we wzorcu odwiedzającego może być odpowiednia; jednak zwykle nie jest to zbyt wygodne w przypadku Antlr.

W pseudokodzie chodzenie zwykle wygląda mniej więcej tak:

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))
Rodzaje przetwarzania są w dużym stopniu zależne od semantyki języka. Na przykład, obsługa instrukcji IF, ze strukturą (IF <predicate> <if-true> [<if-false>]), podczas generowania kodu dla maszyny stosowej, takiej jak JVM lub CLR, może wyglądać mniej więcej tak:
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)

Ogólnie wszystko jest wykonywane rekurencyjnie w zależności od typu aktualnego węzła itp.

 8
Author: Barry Kelly,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-20 13:29:32

Powinieneś przyjrzeć się pisaniu Treeparsera; może to znacznie uprościć interpretację drzewa.

Dla ANTLR 2.x Zobacz http://www.antlr2.org/doc/sor.html Dla ANTLR 3.x zobacz http://www.antlr.org/wiki/display/ANTLR3/Tree+construction (przykład parsera opartego na Javie i parsera drzewa)

 1
Author: Scott Stanchfield,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-20 14:17:07

Zrobiłem coś podobnego (ale nie do końca) i skończyłem z Treeparserem.

Sugeruję również zakup książki ANTLR. Uważam, że jest bardziej wartościowy niż jakikolwiek zasób internetowy. Może nie ma wszystkich odpowiedzi, ale na pewno pomaga w podstawach.

 0
Author: Jasper Floor,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-20 14:24:43