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

47

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.

Comment puis
la source
Le concept clé qui vous manque est la récursivité . La récursivité est un peu paradoxale, et il est différent pour chaque apprenant de «cliquer» avec lui, mais sans récursivité, il n’ya tout simplement pas moyen de comprendre l’analyse syntaxique (et bien d’autres sujets relatifs au calcul également).
Kilian Foth
Je reçois de la récursivité, je pensais juste que ce serait difficile à mettre en œuvre dans ce cas. En fait, je voulais utiliser la récursivité et je me suis retrouvé avec beaucoup de cas qui ne fonctionneraient pas pour une solution générale. La réponse de Gdhoward m'aide beaucoup en ce moment.
Howcan
Il peut s’agir d’un exercice consistant à construire une calculatrice RPN en tant qu’exercice. Cela ne répondra pas à votre question, mais pourrait enseigner certaines compétences nécessaires.
En fait, j'ai déjà construit une calculatrice RPN. Les réponses m'ont beaucoup aidé et je pense que je peux maintenant faire un AST de base. Merci!
Howcan

Réponses:

47

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".

Gavin Howard
la source
Cela fonctionne pour les opérateurs qui ont une associativité de gauche à droite et non de droite à gauche.
Simon
@Simon, il serait extrêmement simple d’ajouter la possibilité aux opérateurs de droite à gauche. Le plus simple consisterait à ajouter une table de consultation et, dans le cas d'un opérateur de droite à gauche, inverser simplement l'ordre des opérandes.
Gavin Howard
4
@Simon Si vous souhaitez prendre en charge les deux, il est préférable de rechercher l' algorithme de la cour de triage dans toute sa splendeur. Comme les algorithmes vont, c'est un cracker absolu.
biziclop
19

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.

Bart van Ingen Schenau
la source
9

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.

Basile Starynkevitch
la source
Je crée un interpréteur Lua pour analyser le texte source et le transformer en tableau dans JS. Puis-je considérer cela comme un AST? Je suis censé faire quelque chose comme ceci: se --My comment #1 print("Hello, ".."world.") transforme en `[{" type ":" - "," content ":" Mon commentaire n ° 1 "}, {" type ":" call "," name ":" print "," arguments ": [[{" type ":" str "," action ":" .. "," content ":" Bonjour, "}, {" type ":" str "," content ": "monde." }]]}] `Je pense que c'est beaucoup plus simple en JS que dans toute autre langue!
Hydroper
@TheProHands Cela serait considéré comme un jeton et non comme un AST.
YoYoYonnY
2

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!

Nergal
la source