Comment crée-t-on exactement un arbre de syntaxe abstraite?

Je pense comprendre l’objectif d’un AST et j’ai déjà construit quelques structures en arbre, mais jamais un AST. La plupart du temps, je suis confus parce que les nœuds sont du texte et non des nombres, je ne peux donc pas penser à un moyen agréable de saisir un jeton / une chaîne alors que je suis en train d'analyser du code.

Par exemple, lorsque je regardais les diagrammes d'AST, la variable et sa valeur étaient des nœuds feuilles à signe égal. Cela me semble tout à fait logique, mais comment pourrais-je m'y prendre? Je suppose que je peux le faire au cas par cas, de sorte que lorsque je tombe sur un "=", je l’utilise comme noeud et j'ajoute la valeur analysée avant le "=" comme feuille. Cela semble faux, parce que je devrai probablement défendre des tonnes et des tonnes de choses, en fonction de la syntaxe.

Et puis je suis tombé sur un autre problème, comment l'arbre est-il traversé? Est-ce que je vais jusqu'au bout de la hauteur et que je remonte un nœud lorsque je touche le bas et fais de même pour son voisin?

J'ai vu des tonnes de diagrammes sur les AST, mais je ne trouvais pas un exemple assez simple de code dans le code, ce qui aiderait probablement.

La réponse courte est que vous utilisez des piles. C'est un bon exemple, mais je l'appliquerai à un AST.

Pour votre information, il s'agit de l' algorithme Shunting-Yard d' Edsger Dijkstra .

Dans ce cas, je vais utiliser une pile d'opérateurs et une pile d'expression. Les nombres étant considérés comme des expressions dans la plupart des langues, je vais utiliser la pile d’expressions pour les stocker.

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

(S'il vous plaît soyez gentil avec mon code. Je sais qu'il n'est pas robuste; il est simplement supposé être un pseudocode.)

Quoi qu'il en soit, comme vous pouvez le voir dans le code, les expressions arbitraires peuvent être des opérandes pour d'autres expressions. Si vous avez l'entrée suivante:

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

le code que j'ai écrit produirait cet AST:

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

Et ensuite, lorsque vous souhaitez générer le code pour cet AST, vous effectuez une traversée de l'arbre des commandes postales . Lorsque vous visitez un nœud feuille (avec un nombre), vous générez une constante car le compilateur doit connaître les valeurs d'opérande. Lorsque vous visitez un nœud avec un opérateur, vous générez l'instruction appropriée de l'opérateur. Par exemple, l'opérateur '+' vous donne une instruction "add".

Il existe une différence significative entre la manière dont un AST est décrit dans le test (un arbre avec des nombres / variables aux nœuds d'extrémité et les symboles aux nœuds intérieurs) et la manière dont il est réellement mis en œuvre.

L'implémentation typique d'un AST (dans un langage OO) utilise beaucoup le polymorphisme. Les nœuds de l'AST sont généralement implémentés avec une variété de classes, toutes dérivées d'une ASTNodeclasse commune . Pour chaque construction syntaxique dans le langage que vous traitez, il y aura une classe pour représenter cette construction dans l'AST, telle que ConstantNode(pour les constantes, telle que 0x10ou 42), VariableNode(pour les noms de variables), AssignmentNode(pour les opérations d'affectation), ExpressionNode(pour les fonctions génériques). expressions), etc.
Chaque type de noeud spécifique spécifie si ce noeud a des enfants, combien et éventuellement de quel type. Un ConstantNodetestament n'a généralement pas d'enfants, un AssignmentNodetest deux et un ExpressionBlockNodenombre illimité d'enfants.

L’AST est construit par l’analyseur, qui sait quelle construction il vient d’analyser, afin de pouvoir construire le bon type de nœud AST.

En traversant l'AST, le polymorphisme des nœuds entre vraiment en jeu. La base ASTNodedéfinit les opérations pouvant être effectuées sur les nœuds et chaque type de nœud spécifique implémente ces opérations de manière spécifique pour cette construction de langage particulière.

Construire l'AST à partir du texte source est une analyse "simple" . La manière exacte dont cela est fait dépend du langage formel analysé et de la mise en œuvre. Vous pouvez utiliser des générateurs de parseurs tels que menhir (pour Ocaml) , GNU bisonavec flex, ou ANTLR, etc. Cela se fait souvent "manuellement" en codant un analyseur de descente récursif (voir la réponse pour expliquer pourquoi). L’aspect contextuel de l’analyse se fait souvent ailleurs (tables de symboles, attributs, ....).

Cependant, dans la pratique, les AST sont beaucoup plus complexes que ce que vous croyez. Par exemple, dans un compilateur tel que GCC, l'AST conserve les informations d'emplacement source et certaines informations de frappe. Lisez à propos des arbres génériques dans GCC et regardez à l'intérieur de son fichier gcc / tree.def . BTW, regardez aussi à l'intérieur de GCC MELT (que j'ai conçu et mis en œuvre), il est pertinent pour votre question.

Je sais que cette question a 4 ans ou plus mais je pense que je devrais ajouter une réponse plus détaillée.

Syntaxe abstraite Les arbres ne sont pas créés différemment des autres arbres. L'instruction la plus vraie dans ce cas est que les nœuds de l'arborescence de syntaxe ont une quantité variadique de nœuds AU BESOIN.

Un exemple est celui des expressions binaires. 1 + 2 Une expression simple comme celle-ci créerait un seul nœud racine contenant un nœud droit et un nœud gauche contenant les données relatives aux nombres. En langage C, cela ressemblerait à quelque chose comme

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;
};

Votre question était aussi comment traverser? Le parcours dans ce cas s'appelle Nœuds visiteurs . Pour visiter chaque nœud, vous devez utiliser chaque type de nœud pour déterminer comment évaluer les données de chaque nœud de syntaxe.

Voici un autre exemple de cela en C où j'imprime simplement le contenu de chaque nœud:

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;
    }
}

Notez que la fonction visite récursivement chaque nœud en fonction du type de nœud avec lequel nous traitons.

Ajoutons un exemple plus complexe, une ifconstruction d'instruction! Rappelez-vous que les instructions if peuvent également avoir une clause else optionnelle. Ajoutons l'instruction if-else à notre structure de nœud d'origine. Rappelez-vous que si les instructions elles-mêmes peuvent également avoir des instructions if, une sorte de récursivité dans notre système de nœuds peut se produire. Les autres instructions étant facultatives, le elsestmtchamp peut être NULL, ce que la fonction de visiteur récursif peut ignorer.

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;
};

De retour dans notre fonction d'impression de visiteur de noeud appelée AST_PrintNode, nous pouvons adapter la ifconstruction AST de déclaration en ajoutant ce code 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;

Aussi simple que cela! En conclusion, l'arbre de syntaxe n'est pas beaucoup plus qu'un arbre d'une union étiquetée de l'arbre et de ses données!