Hvordan oprettes der nøjagtigt et abstrakt syntaks-træ?

Det korte svar er, at du bruger stakke. Dette er et godt eksempel, men jeg anvender det til en AST.

FYI, dette er Edsger Dijkstra “s Shunting-Yard-algoritme .

I dette tilfælde bruger jeg en operatørstak og en udtrykstak. Da tal betragtes som udtryk på de fleste sprog, bruger jeg udtryksstakken til at gemme dem.

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

(Vær venlig pæn med min kode. Jeg ved, at den ikke er robust; den skal bare være pseudokode.)

Alligevel, som du kan se fra koden, vilkårlig udtryk kan være operander til andre udtryk. Hvis du har følgende input:

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

vil koden jeg skrev producere denne AST:

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

Og når du derefter vil fremstille koden til den AST, skal du foretage en Gennemgang af postordretræ . Når du besøger en bladknude (med et tal), genererer du en konstant, fordi compileren har brug for at kende operandværdierne. Når du besøger en node med en operator, genererer du den relevante instruktion fra operatøren. For eksempel “+” operatøren giver dig en “tilføj” instruktion.

Kommentarer

• Dette fungerer fo r operatører, der har venstre mod højre associativitet, ikke højre mod venstre.
• @Simon, det ville være ekstremt simpelt at tilføje muligheden for operatører fra højre til venstre. Det enkleste ville være at tilføje et opslagstabel, og hvis en operatør højre mod venstre, skal du blot vende rækkefølgen af operanderne.
• @Simon Hvis du vil støtte begge dele, skal du ‘ har det bedre at kigge op på shunt yard-algoritmen i sin fulde pragt. Som algoritmer går, er ‘ en absolut krakker.

Der er en signifikant forskel mellem, hvordan en AST typisk er afbildet i testen (et træ med tal / variabler ved bladknudepunkter og symboler ved indvendige knudepunkter), og hvordan det faktisk implementeres.

Det typiske implementering af en AST (på et OO-sprog) gør tung brug af polymorfisme. Knudepunkterne i AST implementeres typisk med en række forskellige klasser, der alle stammer fra en fælles ASTNode klasse. For hver syntaktisk konstruktion på det sprog, du behandler, vil der være en klasse til at repræsentere den konstruktion i AST, såsom ConstantNode (for konstanter, såsom 0x10 eller 42), VariableNode (for variabelnavne), AssignmentNode (til tildelingsoperationer), ExpressionNode (til generiske udtryk) osv.
Hver specifik nodetype angiver, om den node har børn, hvor mange og muligvis af hvilken type. En ConstantNode har typisk ingen børn, en AssignmentNode har to og en ExpressionBlockNode har et hvilket som helst antal børn.

AST bliver bygget af parseren, der ved, hvilken konstruktion den lige har analyseret, så den kan konstruere den rigtige type AST-knude.

Når du kører AST, polymorfismen af knudepunkterne kommer virkelig i spil. Basen ASTNode definerer de operationer, der kan udføres på noderne, og hver specifik nodetype implementerer disse operationer på den specifikke måde for den pågældende sprogkonstruktion.

Bygning af AST fra kildeteksten er ” simpelthen ” parsing . Hvor nøjagtigt det gøres afhænger af det analyserede formelle sprog og implementeringen. Du kan bruge parsergeneratorer som menhir (til Ocaml) , GNU bison med flex eller ANTLR osv. Det gøres ofte ” manuelt ” ved at kode nogle rekursiv nedstigningsparser (se dette svar forklarer hvorfor). Det kontekstuelle aspekt ved parsing udføres ofte andre steder (symboltabeller, attributter, ….).

I praksis er AST imidlertid meget mere komplekse end hvad du tror. I en kompilator som GCC beholder AST f.eks. Kildeplaceringsoplysninger og nogle indtastningsoplysninger. Læs om Generiske træer og GIMPLE i GCC og se inde i dens gcc / tree.def . Overvej, hvis du vil behandle C eller C ++ eller Fortran eller Ada, skal du skrive dit eget GCC-plugin . BTW, se også inde i det forældede GCC MELT (som jeg har designet & implementeret), det er relevant for din spørgsmål. Læs Dragon-bog . Se også dette udkast -rapport for referencer og RefPerSys -projektet og kildekoden til mange andre open source projekter (inklusive Ocaml eller Guile eller SBCL eller Jq ) på github eller gitlab som eksempler.

Kommentarer

• Jeg ‘ Jeg laver en Lua-tolk til at analysere kildetekst og transformere i en matrix i JS. Kan jeg betragte det som en AST? Jeg ‘ skal gøre noget som dette: --My comment #1 print("Hello, ".."world.") forvandles til `[{” type “: ” – “, ” indhold “: ” Min kommentar # 1 “}, {” skriv “: ” kald “, ” navn “: ” print “, ” argumenter “: [[{{div div = “0edb01244e”>

Jeg ved, at dette spørgsmål er 4+ år, men jeg føler, at jeg skal tilføje et mere detaljeret svar.

Abstrakte syntaks Træer skabes ikke anderledes end andre træer; jo mere sand påstand i dette tilfælde er, at syntaks-træ-noder har en variabel mængde noder, SOM NØDVENDIGT.

Et eksempel er binære udtryk som 1 + 2 Et simpelt udtryk som der ville skabe en enkelt rodknude, der holder en højre og venstre knude, der indeholder data om numrene.På C-sprog lignede det noget som

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

Dit spørgsmål var også, hvordan man krydser? I dette tilfælde hedder vi Besøgsnoder . At besøge hver node kræver, at du bruger hver nodetype til at bestemme, hvordan du vurderer dataene for hver Syntax-node.

Her er et andet eksempel på det i C, hvor jeg blot udskriver indholdet af hver node:

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

Bemærk hvordan funktionen rekursivt besøger hver node i henhold til hvilken type node vi har at gøre med.

Lad os tilføje et mere komplekst eksempel, en if sætningskonstruktion! Husk at hvis udsagn kan også have en valgfri ellers klausul. Lad os tilføje if-else-sætningen til vores oprindelige nodestruktur. Husk, at hvis udsagn i sig selv også kan have hvis udsagn, så kan der opstå en slags rekursion inden for vores knudesystem. Andre udsagn er valgfri, så elsestmt -feltet kan være NULL, som den rekursive besøgende kan ignorere.

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

tilbage i vores knudepunktsudskrivningsfunktion kaldet AST_PrintNode, kan vi rumme if AST-konstruktion ved at tilføje denne C-kode:

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; 

Så simpelt som det! Afslutningsvis er syntaks-træet ikke meget mere end et træ af en mærket forening af træet og dets data selv!