Как именно создается абстрактное синтаксическое дерево?

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

Например, когда я смотрел на диаграммы AST, переменная и ее значение представляли собой листовые узлы со знаком равенства. Это имеет смысл для меня, но как бы я реализовал это? Я думаю, я могу сделать это в каждом конкретном случае, поэтому, когда я натыкаюсь на «=», я использую это как узел и добавляю значение, проанализированное перед «=» в качестве листа. Это просто кажется неправильным, потому что я, вероятно, должен был бы делать случаи для множества вещей, в зависимости от синтаксиса.

И тогда я натолкнулся на другую проблему, как проходит дерево? Должен ли я пройти весь путь вниз по высоте и вернуться назад к узлу, когда я достигну дна, и сделать то же самое для его соседа?

Я видел тонны диаграмм на AST, но я не смог найти довольно простой пример того, что в коде, который, вероятно, помог бы.

Короткий ответ: вы используете стеки. Это хороший пример, но я применю его к AST.

К вашему сведению, это алгоритм Шунтирования-Ярда Эдсгера Дейкстры .

В этом случае я буду использовать стек операторов и стек выражений. Поскольку числа считаются выражениями в большинстве языков, я буду использовать их для хранения.

class ExprNode:
    char c
    ExprNode operand1
    ExprNode operand2

    ExprNode(char num):
        c = num
        operand1 = operand2 = nil

    Expr(char op, ExprNode e1, ExprNode e2):
        c = op
        operand1 = e1
        operand2 = e2

# Parser
ExprNode parse(string input):
    char c
    while (c = input.getNextChar()):
        if (c == '('):
            operatorStack.push(c)

        else if (c.isDigit()):
            exprStack.push(ExprNode(c))

        else if (c.isOperator()):
            while(operatorStack.top().precedence >= c.precedence):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            operatorStack.push(c)

        else if (c == ')'):
            while (operatorStack.top() != '('):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            # Pop the '(' off the operator stack.
            operatorStack.pop()

        else:
            error()
            return nil

    # There should only be one item on exprStack.
    # It's the root node, so we return it.
    return exprStack.pop()

(Пожалуйста, будьте внимательны с моим кодом. Я знаю, что он не надежный; просто он должен быть псевдокодом.)

В любом случае, как видно из кода, произвольные выражения могут быть операндами других выражений. Если у вас есть следующие данные:

5 * 3 + (4 + 2 % 2 * 8)

код, который я написал, будет производить этот AST:

     +
    / \
   /   \
  *     +
 / \   / \
5   3 4   *
         / \
        %   8
       / \
      2   2

И затем, когда вы хотите создать код для этого AST, вы выполняете обход дерева почтовых заказов . Когда вы посещаете листовой узел (с номером), вы генерируете константу, потому что компилятору необходимо знать значения операнда. Когда вы посещаете узел с оператором, вы генерируете соответствующую инструкцию от оператора. Например, оператор «+» дает вам инструкцию «добавить».

Существует значительная разница между тем, как AST обычно изображается в тесте (дерево с числами / переменными в конечных узлах и символами во внутренних узлах), и тем, как оно на самом деле реализовано.

Типичная реализация AST (на языке OO) интенсивно использует полиморфизм. Узлы в AST обычно реализуются с помощью различных классов, все они являются производными от общего ASTNodeкласса. Для каждой синтаксической конструкции в языке, который вы обрабатываете, будет класс для представления этой конструкции в AST, такой как ConstantNode(для констант, таких как 0x10или 42), VariableNode(для имен переменных), AssignmentNode(для операций присваивания), ExpressionNode(для универсального выражения) и т. д.
Каждый конкретный тип узла указывает, есть ли у этого узла дочерние элементы, сколько и, возможно, какого типа. У ConstantNodeдетей, как правило, нет детей, у детей AssignmentNodeможет быть два, и ExpressionBlockNodeу детей может быть любое количество детей.

AST создается синтаксическим анализатором, который знает, какую конструкцию он только что проанализировал, поэтому он может создать правильный тип AST Node.

При прохождении AST полиморфизм узлов действительно вступает в игру. База ASTNodeопределяет операции, которые могут быть выполнены на узлах, и каждый конкретный тип узла реализует эти операции определенным образом для этой конкретной языковой конструкции.

Построение AST из исходного текста - это просто анализ . Как именно это делается, зависит от разобранного формального языка и реализации. Вы можете использовать генераторы синтаксического анализатора, такие как menhir (для Ocaml) , GNU bisonwith flex, или ANTLR и т. Д. И т. Д. Это часто делается «вручную» путем кодирования некоторого синтаксического анализатора с рекурсивным спуском (см. Этот ответ, объясняющий почему). Контекстный аспект синтаксического анализа часто выполняется в другом месте (таблицы символов, атрибуты, ....).

Однако на практике AST гораздо сложнее, чем вы верите. Например, в компиляторе, таком как GCC, AST хранит информацию о местоположении источника и некоторую информацию о типизации. Прочтите об общих деревьях в GCC и загляните внутрь его gcc / tree.def . Кстати, посмотрите также внутри GCC MELT (который я разработал и внедрил), это актуально для вашего вопроса.

Я знаю, что этому вопросу 4+ года, но я чувствую, что должен добавить более подробный ответ.

Абстрактный синтаксис Деревья создаются не иначе, как другие деревья; более верное утверждение в этом случае состоит в том, что узлы синтаксического дерева имеют вариативное количество узлов, КАК НУЖНО.

Примером являются бинарные выражения, такие как 1 + 2 Простое выражение, подобное этому, создающее один корневой узел, содержащий правый и левый узел, который содержит данные о числах. На языке C это будет выглядеть примерно так

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod,
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

Ваш вопрос был также, как пройти? Обход в этом случае называется посещением узлов . Посещение каждого узла требует использования каждого типа узла, чтобы определить, как оценивать данные каждого узла синтаксиса.

Вот еще один пример этого в C, где я просто печатаю содержимое каждого узла:

void AST_PrintNode(const ASTNode *node)
{
    if( !node )
        return;

    char *opername = NULL;
    switch( node->Type ) {
        case AST_IntVal:
            printf("AST Integer Literal - %lli\n", node->Data->llVal);
            break;
        case AST_Add:
            if( !opername )
                opername = "+";
        case AST_Sub:
            if( !opername )
                opername = "-";
        case AST_Mul:
            if( !opername )
                opername = "*";
        case AST_Div:
            if( !opername )
                opername = "/";
        case AST_Mod:
            if( !opername )
                opername = "%";
            printf("AST Binary Expr - Oper: \'%s\' Left:\'%p\' | Right:\'%p\'\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right);
            AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node.
            AST_PrintNode(node->Data->BinaryExpr.right);
            break;
    }
}

Обратите внимание, как функция рекурсивно посещает каждый узел в зависимости от того, с каким типом узла мы имеем дело.

Давайте добавим более сложный пример, ifконструкцию оператора! Напомним, что операторы if могут также иметь необязательное условие else. Давайте добавим оператор if-else к нашей исходной структуре узла. Помните, что сами операторы if могут также иметь операторы if, поэтому может произойти своего рода рекурсия в нашей системе узлов. Остальные операторы являются необязательными, поэтому elsestmtполе может иметь значение NULL, которое рекурсивная функция посетителя может игнорировать.

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
    struct {
        struct ASTNode *expr, *stmt, *elsestmt;
    } IfStmt;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

вернувшись в нашу функцию печати посетителя узла AST_PrintNode, мы можем разместить ifконструкцию AST оператора, добавив этот код C:

case AST_IfStmt:
    puts("AST If Statement\n");
    AST_PrintNode(node->Data->IfStmt.expr);
    AST_PrintNode(node->Data->IfStmt.stmt);
    AST_PrintNode(node->Data->IfStmt.elsestmt);
    break;

Так просто, как, что! В заключение, синтаксическое дерево - это не что иное, как дерево тегового объединения дерева и самих его данных!