Je pense que je comprends le but dun AST, et jai déjà construit quelques arborescences avant, mais jamais un AST. Je suis plutôt confus parce que les nœuds sont du texte et non des nombres, donc je ne peux pas penser à une bonne façon de saisir un jeton / une chaîne pendant que janalyse du code.
Par exemple, lorsque jai regardé des diagrammes dAST, la variable et sa valeur étaient des nœuds feuilles à signe égal. Cela me semble parfaitement logique, mais comment procéder pour limplémenter? I je suppose que je peux le faire au cas par cas, de sorte que lorsque je tombe sur un « = », je lutilise comme nœud et ajoute la valeur analysée avant le « = » comme feuille. Cela semble juste faux, car je « d probablement doivent faire des cas pour des tonnes et des tonnes de choses, selon la syntaxe.
Et puis je suis tombé sur un autre problème, comment larbre est-il traversé? Dois-je descendre tout le long de la hauteur et remonter un nœud quand je touche le bas, et faire de même pour son voisin?
Jai vu des tonnes de diagrammes sur les AST, mais Je nai pas pu en trouver un exemple assez simple dans le code, ce qui aiderait probablement.
Commentaires
- Le concept clé que vous ‘ il manque une récursion . La récursivité est un peu contre-intuitive, et elle ‘ est différente pour chaque apprenant quand elle sera finalement ‘ cliquez ‘ avec eux, mais sans récursivité, il ny a tout simplement aucun moyen de comprendre lanalyse (et bien dautres sujets de calcul également ).
- Jobtiens une récursivité, je pensais juste que ‘ serait difficile à implémenter dans ce cas. beaucoup de cas qui ne ‘ t fonctionneraient pas pour une solution générale. La réponse de Gdhoward ‘ maide beaucoup pour le moment.
- Il pourrait être un exercice de créer une calculatrice RPN comme exercice. Il ne répondra pas à votre question mais pourrait enseigner certaines compétences nécessaires.
- Jai déjà construit une calculatrice RPN. Les réponses mont beaucoup aidé et je pense que je peux faire un AST de base maintenant. Merci!
Réponse
La réponse courte est que vous utilisez des piles. Ceci est un bon exemple, mais je vais lappliquer à un AST.
Pour info, voici le Algorithme Shunting-Yard .
Dans ce cas, jutiliserai une pile dopérateurs et une pile dexpressions. Puisque les nombres sont considérés comme des expressions dans la plupart des langues, jutiliserai la pile dexpressions 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()
(Soyez gentil avec mon code. Je sais que ce nest pas robuste; il est juste supposé être un pseudocode.)
Quoi quil en soit, comme vous pouvez le voir dans le code, arbitraire les expressions peuvent être des opérandes vers dautres expressions. Si vous avez lentrée suivante:
5 * 3 + (4 + 2 % 2 * 8) le code que jai écrit produirait cet AST:
+ / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 Et ensuite, lorsque vous souhaitez produire le code pour cet AST, vous effectuez une Traversée de larborescence de commande . Lorsque vous visitez un nœud feuille (avec un nombre), vous générez une constante car le compilateur a besoin de connaître les valeurs dopérande. Lorsque vous visitez un nœud avec un opérateur, vous générez linstruction appropriée à partir de lopérateur. Par exemple, le « + » Lopérateur vous donne une instruction «ajouter».
Commentaires
- Cela fonctionne pour r opérateurs qui ont une associativité de gauche à droite, pas de droite à gauche.
- @Simon, il serait extrêmement simple dajouter la capacité des opérateurs de droite à gauche. Le plus simple serait dajouter une table de recherche et si un opérateur est de droite à gauche, inversez simplement lordre des opérandes.
- @Simon Si vous voulez prendre en charge les deux, vous ‘ mieux vaut rechercher l algorithme de triage de manœuvre dans toute sa splendeur. Selon les algorithmes, ‘ est un cracker absolu.
Réponse
Il y a une différence significative entre la façon dont un AST est généralement représenté dans le test (un arbre avec des nombres / variables aux nœuds feuilles et des symboles aux nœuds intérieurs) et comment il est réellement implémenté.
limplémentation dun AST (dans un langage OO) fait un usage intensif du polymorphisme. Les nœuds de lAST sont généralement implémentés avec une variété de classes, toutes dérivant dune classe ASTNode commune. Pour chaque construction syntaxique dans le langage que vous traitez, il y aura une classe pour représenter cette construction dans AST, telle que ConstantNode (pour les constantes, telles que 0x10 ou 42), VariableNode (pour les noms de variables), AssignmentNode (pour les opérations daffectation), ExpressionNode (pour les expressions génériques), etc.
Chaque type de nœud spécifique spécifie si ce nœud a des enfants, combien et éventuellement de quel type. Un ConstantNode naura généralement pas denfants, un AssignmentNode en aura deux et un ExpressionBlockNode peut avoir nimporte quel nombre denfants.
LAST est construit par lanalyseur, qui sait quelle construction il vient danalyser, afin quil puisse construire le bon type de nœud AST.
Lors de la traversée lAST, le polymorphisme des nœuds entre vraiment en jeu. La base ASTNode définit les opérations qui peuvent être effectuées sur les nœuds, et chaque type de nœud spécifique implémente ces opérations de la manière spécifique pour cette construction de langage particulière.
Réponse
Construire lAST à partir du texte source est » simplement » analyse . La manière exacte dont cela est fait dépend du langage formel analysé et de limplémentation. Vous pouvez utiliser des générateurs danalyseurs tels que menhir (pour Ocaml) , GNU bison avec flex, ou ANTLR etc etc. Cest souvent fait » manuellement » en codant certains analyseur de descente récursive (voir cette réponse expliquant pourquoi). Laspect contextuel de lanalyse syntaxique se fait souvent ailleurs (tables de symboles, attributs, ….).
Cependant, en pratique, les AST sont beaucoup plus complexes que ce que vous pensez. Par exemple, dans un compilateur comme GCC , lAST conserve les informations de localisation source et certaines informations de typage. En savoir plus sur Arbres génériques et GIMPLE dans GCC et regardez à lintérieur de son gcc / tree.def . Si vous voulez traiter C ou C ++ ou Fortran ou Ada, pensez à écrire votre propre plugin GCC . BTW, regardez également à lintérieur du GCC MELT obsolète (que jai conçu & implémenté), il est pertinent pour votre question. Lisez le livre Dragon . Consultez également ce projet de rapport pour les références, ainsi que le projet RefPerSys et le code source de plusieurs autres projets open source (y compris Ocaml ou Guile ou SBCL ou Jq ) sur github ou gitlab comme exemples.
Commentaires
- Je ‘ m en train de créer un interpréteur Lua pour analyser le texte source et le transformer en tableau dans JS. Puis-je le considérer comme un AST? Je ‘ est censé faire quelque chose comme ceci:
--My comment #1 print("Hello, ".."world.")se transforme en `[{ » type « : » – « , » content « : » Mon commentaire # 1 « }, { » type « : » appel « , » nom « : » print « , » arguments « : [[{ » type « : » str « , » action « : » .. « , » content « : » Bonjour, « }, { » type « : » str « , » content « : » world. « }]]}] `Je pense que ‘ est beaucoup plus simple en JS que nimporte quelle autre langue! - @TheProHands Ceci serait considéré comme des jetons, pas comme un AST.
Réponse
Je sais que cette question a plus de 4 ans mais je pense que je devrais ajouter une réponse plus détaillée.
Les arbres de syntaxe abstraite ne sont pas créés différemment des autres arbres; la déclaration la plus vraie dans ce cas est que les nœuds de larbre de syntaxe ont une quantité variadique de nœuds selon les besoins.
Un exemple est des expressions binaires comme 1 + 2 Une expression simple comme cela créerait un nœud racine unique contenant un nœud droit et gauche contenant les données sur les 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 de savoir comment traverser? La traversée dans ce cas sappelle Visite des nœuds . La visite de chaque nœud nécessite que vous utilisiez chaque type de nœud pour déterminer comment évaluer les données de chaque nœud de syntaxe.
Voici un autre exemple de celui en C où jimprime 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; } } Remarquez comment la fonction visite récursivement chaque nœud en fonction du type de nœud que nous « traitons.
Ajoutons un exemple plus complexe, une instruction if! Rappelez-vous que les instructions if peut également avoir une clause else facultative. Ajoutons linstruction if-else à notre structure de nœuds dorigine. Souvenez-vous que les instructions if elles-mêmes peuvent aussi avoir des instructions if, donc une sorte de récursivité dans notre système de nœuds peut se produire. Sinon, les instructions sont facultatives, donc le champ elsestmt peut être NULL 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; }; retour dans notre fonction dimpression de visiteur de nœud appelée AST_PrintNode, nous pouvons intégrer la construction AST de linstruction if 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, larbre de syntaxe nest rien de plus quun arbre dune union étiquetée de larbre et de ses données elles-mêmes!