Hoe wordt precies een abstracte syntaxisboom gemaakt?

Het korte antwoord is dat je stapels gebruikt. Dit is een goed voorbeeld, maar ik “zal het toepassen op een AST.

Ter info, dit is Edsger Dijkstras Shunting-Yard-algoritme .

In dit geval zal ik een operatorstapel en een expressiestapel gebruiken. Aangezien getallen in de meeste talen als uitdrukkingen worden beschouwd, gebruik ik de uitdrukkingsstapel om ze op te slaan.

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

(Wees alsjeblieft aardig over mijn code. Ik weet dat het “niet robuust is; het moet gewoon pseudocode zijn.)

Hoe dan ook, zoals je kunt zien aan de code, willekeurig expressies kunnen operanden zijn voor andere expressies. Als je de volgende invoer hebt:

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

de code die ik schreef zou deze AST produceren:

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

En als u vervolgens de code voor die AST wilt produceren, doet u een Postorder Tree Traversal . Wanneer je bezoekt een leaf-node (met een nummer), je genereert een constante omdat de compiler de operandwaarden moet kennen. Wanneer je een node bezoekt met een operator, genereer je de juiste instructie van de operator. Bijvoorbeeld de “+” operator geeft je een “add” -instructie.

Comments

• Dit werkt voor r operators die associativiteit van links naar rechts hebben, niet van rechts naar links.
• @Simon, het zou extreem eenvoudig zijn om de mogelijkheid voor rechts-naar-links operators toe te voegen. Het eenvoudigste zou zijn om een opzoektabel toe te voegen en als een operator van rechts naar links draait, keert u eenvoudig de volgorde van de operanden om.
• @Simon Als u beide wilt ondersteunen, ‘ het is beter om het rangeerterrein-algoritme in zijn volle glorie op te zoeken. Volgens algoritmen is dat ‘ een absolute cracker.

Er is een significant verschil tussen hoe een AST typisch wordt afgebeeld in een test (een boom met getallen / variabelen op de bladknooppunten en symbolen op binnenknooppunten) en hoe deze feitelijk wordt geïmplementeerd.

De typische implementatie van een AST (in een OO-taal) maakt veel gebruik van polymorfisme. De knooppunten in de AST worden doorgaans geïmplementeerd met een verscheidenheid aan klassen, die allemaal afkomstig zijn van een gemeenschappelijke ASTNode -klasse. Voor elk syntactisch construct in de taal die u aan het verwerken bent, is er een klasse om dat construct in de AST weer te geven, zoals ConstantNode (voor constanten, zoals 0x10 of 42), VariableNode (voor variabelenamen), AssignmentNode (voor toewijzingsbewerkingen), ExpressionNode (voor algemene uitdrukkingen), enz.
Elk specifiek knooppunttype geeft aan of dat knooppunt kinderen heeft, hoeveel en mogelijk van welk type. Een ConstantNode heeft doorgaans geen kinderen, een AssignmentNode heeft er twee en een ExpressionBlockNode kan een willekeurig aantal kinderen hebben.

De AST wordt gebouwd door de parser, die weet welke constructie het zojuist heeft geparseerd, zodat het het juiste soort AST-knooppunt kan construeren.

Bij het passeren de AST, het polymorfisme van de knooppunten komt echt in het spel. De basis ASTNode definieert de bewerkingen die kunnen worden uitgevoerd op de knooppunten, en elk specifiek knooppunttype implementeert die bewerkingen op de specifieke manier voor die specifieke taalconstructie.

Het bouwen van de AST op basis van de brontekst is ” simpelweg ” parseren . Hoe het precies wordt gedaan, hangt af van de geparseerde formele taal en de implementatie. Je zou parser-generators kunnen gebruiken zoals menhir (voor Ocaml) , GNU bison met flex, of ANTLR etc etc. Het wordt vaak gedaan ” handmatig ” door een recursieve descent-parser te coderen (zie dit antwoord waarin wordt uitgelegd waarom). Het contextuele aspect van parsing wordt vaak elders gedaan (symbooltabellen, attributen, …).

In de praktijk zijn AST echter veel complexer dan je denkt. In een compiler zoals GCC bewaart de AST bijvoorbeeld bronlocatie-informatie en wat typinformatie. Lees meer over Generic Trees en GIMPLE in GCC en kijk in de gcc / tree.def . Overweeg, als u C of C ++ of Fortran of Ada wilt verwerken, het schrijven van uw eigen GCC-plug-in . Kijk trouwens ook in de verouderde GCC MELT (die ik heb ontworpen & geïmplementeerd), deze is relevant voor uw vraag. Lees het Dragon-boek . Zie ook dit conceptrapport voor referenties, en het RefPerSys -project en de broncode van veel andere open source -projecten (inclusief Ocaml of Guile of SBCL of Jq ) op github of gitlab als voorbeelden.

Reacties

• Ik ‘ maak een Lua-interpreter om de brontekst te ontleden en om te zetten in een array in JS. Kan ik het als een AST beschouwen? Ik ‘ m zou zoiets als dit moeten doen: --My comment #1 print("Hello, ".."world.") transformeert naar `[{” type “: ” – “, ” content “: ” Mijn reactie # 1 “}, {” type “: ” call “, ” naam “: ” print “, ” argumenten “: [[{” type “: ” str “, ” actie “: ” .. “, ” content “: ” Hallo, “}, {” type “: ” str “, ” content “: ” world. “}]]}] “Ik denk dat het ‘ veel eenvoudiger is in JS dan elke andere taal!
• @TheProHands Dit zou worden beschouwd als tokens, niet als een AST.

Ik weet dat deze vraag 4+ jaar oud is, maar ik vind dat ik een meer gedetailleerd antwoord moet geven.

Abstracte syntaxis Bomen worden niet anders gemaakt dan andere bomen; de meer waarachtige bewering in dit geval is dat syntaxisboomknooppunten een variadisch aantal knooppunten hebben ZOALS NODIG.

Een voorbeeld is binaire uitdrukkingen zoals 1 + 2 Een eenvoudige uitdrukking zoals dat zou een enkel hoofdknooppunt creëren met daarin een rechter- en linkerknooppunt dat de gegevens over de getallen bevat.In de C-taal “zou het er ongeveer zo uitzien

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

Je vraag was ook hoe te doorkruisen? In dit geval heet het Bezoekende knooppunten . Voor het bezoeken van elk knooppunt moet u elk knooppunttype gebruiken om te bepalen hoe de gegevens van elk syntaxisknooppunt moeten worden geëvalueerd.

Hier is nog een voorbeeld van dat in C, waar ik gewoon de inhoud van elk knooppunt afdruk:

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

Merk op hoe de functie recursief bezoekt elk knooppunt volgens het type knooppunt waar we “mee te maken hebben.

Laten we een meer complex voorbeeld toevoegen, een if instructieconstructie! Bedenk dat if-instructies kan ook een optionele else-clausule hebben. Laten we de if-else-instructie toevoegen aan onze oorspronkelijke knooppuntstructuur. Onthoud dat if-statements zelf ook if-statements kunnen hebben, dus een soort recursie binnen ons knooppuntsysteem kan optreden. Andere instructies zijn optioneel, dus het veld elsestmt kan NULL zijn, wat de recursieve bezoekersfunctie kan negeren.

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

terug in onze knooppunt bezoekersafdrukfunctie genaamd AST_PrintNode, kunnen we de if statement AST-constructie verwerken door deze C-code toe te voegen:

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; 

Zo simpel is het! Concluderend, de syntaxisboom is niet veel meer dan een boom van een getagde vereniging van de boom en zijn gegevens zelf!