Учебник для ходьбы ANTLR AST в C #? - PullRequest
21 голосов
/ 20 мая 2009

Кто-нибудь знает учебники по обходу AST, генерируемых ANTLR, в C #? Самое близкое, что мне удалось найти, это это , но это не очень полезно.

Моя цель - пройтись по деревьям, которые я генерирую на основе предметно-ориентированного языка, над которым я работаю, и использовать деревья для вывода сгенерированного кода C #.

Учебное пособие на основе Java также будет полезным - все, что содержит наглядные примеры того, как обходить ANTLR AST.

Ответы [ 4 ]

19 голосов
/ 29 мая 2009

Мне удалось это выяснить, адаптировав пример в конце Статья Мануэля Абадии .

Вот моя версия, которую я использую для преобразования разобранного кода в C #. Это шаги:

  1. Создание ANTLRStringStream или подкласса с вводом (это может быть файл или строка).
  2. Создайте экземпляр вашего сгенерированного лексера, передавая этот поток строк.
  3. Создание потока токенов с помощью лексера.
  4. Создайте свой синтаксический анализатор с этим потоком токенов.
  5. Получите значение верхнего уровня из вашего анализатора и превратите его в CommonTree.
  6. Пройдите по дереву:

Чтобы получить буквенный текст узла, используйте node.Text. Чтобы получить имя токена узла, используйте node.Token.Text.

Обратите внимание, что node.Token.Text даст вам действительное имя вашего токена, только если это воображаемый токен без соответствующей строки. Если это настоящий токен, node.Token.Text вернет его строку.

Например, если в вашей грамматике было следующее:

tokens { PROGRAM, FUNCDEC }

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

Тогда вы получите "PROGRAM", "FUNCDEC", "==" и "=" от соответствующих обращений node.Token.Text.

Вы можете увидеть часть моего примера ниже, или вы можете просмотреть полную версию .


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;

      ....
    }
}
8 голосов
/ 20 мая 2009

Обычно вы проходите AST с рекурсией и выполняете различные действия в зависимости от типа узла. Если вы используете полиморфные узлы дерева (то есть разные подклассы для разных узлов дерева), тогда двойная диспетчеризация в шаблоне Visitor может быть уместной; однако, это обычно не очень удобно с Antlr.

В псевдокоде ходьба обычно выглядит примерно так:

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))

Виды обработки сильно зависят от семантики языка. Например, обработка оператора IF со структурой (IF <predicate> <if-true> [<if-false>]) при генерации кода для стековой машины, такой как JVM или CLR, может выглядеть примерно так:

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)

Обычно все выполняется рекурсивно в зависимости от типа текущего узла и т. Д.

1 голос
/ 20 мая 2009

Вы должны посмотреть на написание TreeParser; это может упростить работу по интерпретации дерева.

Для ANTLR 2.x см. http://www.antlr2.org/doc/sor.html Для ANTLR 3.x см. http://www.antlr.org/wiki/display/ANTLR3/Tree+construction (пример парсера на основе Java и синтаксического анализатора дерева)

0 голосов
/ 20 мая 2009

Я сделал что-то похожее (но не совсем), и у меня получился TreeParser.

Я также предлагаю купить книгу ANTLR. Я нашел это более ценным, чем любой веб-ресурс. Возможно, у него нет ответов на все вопросы, но он определенно помогает с основами.

...