Hur exakt skapas ett abstrakt syntaxträd?

Det korta svaret är att du använder stackar. Detta är ett bra exempel, men jag kommer att tillämpa det på en AST.

FYI, det här är Edsger Dijkstra ”s Shunting-Yard Algorithm .

I det här fallet använder jag en operatörstack och en uttrycksstack. Eftersom siffror betraktas som uttryck på de flesta språk kommer jag att använda uttrycksstacken för att lagra 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()  

(Var snäll med min kod. Jag vet att den inte är robust; den ska bara vara pseudokod.)

Hur som helst, som du kan se från koden, godtycklig uttryck kan vara operander till andra uttryck. Om du har följande inmatning:

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

skulle koden jag skrev producera denna AST:

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

Och när du sedan vill producera koden för den AST gör du en Traversal för postorderträd . När du besöker en bladnod (med ett nummer) genererar du en konstant eftersom kompilatorn behöver känna till operandvärdena. När du besöker en nod med en operatör genererar du lämplig instruktion från operatören. Till exempel ”+” operatören ger dig en ”lägg till” instruktion.

Kommentarer

• Detta fungerar för r-operatörer som har vänster till höger associativitet, inte höger till vänster.
• @Simon, det skulle vara extremt enkelt att lägga till möjligheten för höger-till-vänster-operatörer. Det enklaste skulle vara att lägga till en uppslagstabell och om en operatör höger till vänster, helt enkelt vända ordningen på operanderna.
• @Simon Om du vill stödja båda, så ’ är bättre att leta upp växlingsalgoritmen i sin fulla ära. Som algoritmer går är ’ en absolut krackare.

Det finns en signifikant skillnad mellan hur en AST typiskt avbildas i testet (ett träd med siffror / variabler vid bladnoder och symboler vid inre noder) och hur det faktiskt implementeras.

Det typiska implementering av en AST (på ett OO-språk) använder polymorfism i hög grad. Noderna i AST implementeras vanligtvis med en mängd olika klasser, alla härledda från en gemensam ASTNode -klass. För varje syntaktisk konstruktion på det språk du bearbetar kommer det att finnas en klass för att representera den konstruktionen i AST, till exempel ConstantNode (för konstanter, till exempel 0x10 eller 42), VariableNode (för variabelnamn), AssignmentNode (för tilldelningsoperationer), ExpressionNode (för generiska uttryck) etc.
Varje specifik nodtyp anger om den noden har barn, hur många och möjligen av vilken typ. En ConstantNode har vanligtvis inga barn, en AssignmentNode har två och en ExpressionBlockNode burk har valfritt antal barn.

AST byggs av analysatorn, som vet vilken konstruktion den just har analyserat, så att den kan konstruera rätt typ av AST-nod.

När du korsar AST, polymorfismen i noderna spelar verkligen in. Basen ASTNode definierar de operationer som kan utföras på noderna, och varje specifik nodtyp implementerar dessa operationer på det specifika sättet för den specifika språkkonstruktionen.

Att bygga AST från källtexten är ” helt enkelt ” tolkning . Hur exakt det görs beror på det analyserade formella språket och genomförandet. Du kan använda parsergeneratorer som menhir (för Ocaml) , GNU bison med flex, eller ANTLR etc etc. Det görs ofta ” manuellt ” genom att koda någon recursiv nedstigningsparser (se detta svar förklarar varför). Den kontextuella aspekten av parsing görs ofta någon annanstans (symboltabeller, attribut, …).

I praktiken är AST dock mycket mer komplex än vad du tror. Till exempel, i en kompilator som GCC behåller AST källplatsinformation och lite typinformation. Läs om Generiska träd och GIMPLE i GCC och titta inuti dess gcc / tree.def . Tänk, om du vill bearbeta C eller C ++ eller Fortran eller Ada, skriv ditt eget GCC-plugin . BTW, titta också inuti det föråldrade GCC MELT (som jag har designat & implementerat), det är relevant för din fråga. Läs Dragon book . Se även detta utkast -rapport för referenser och RefPerSys -projektet och källkoden för många andra öppen källkod -projekt (inklusive Ocaml eller Guile eller SBCL eller Jq ) på github eller gitlab som exempel.

Kommentarer

• Jag ’ Jag gör en Lua-tolk för att analysera källtext och transformera i en matris i JS. Kan jag betrakta det som en AST? Jag ’ jag ska göra något liknande: --My comment #1 print("Hello, ".."world.") förvandlas till `[{” typ ”: ” – ”, ” content ”: ” Min kommentar # 1 ”}, {” typ ”: ” ring ”, ” namn ”: ” skriv ut ”, ” argument ”: [[{” typ ”: ” str ”, ” åtgärd ”: ” .. ”, ” innehåll ”: ” Hej, ”}, {” typ ”: ” str ”, ” innehåll ”: ” värld. ”}]]}] `Jag tror att det ’ är mycket enklare i JS än vilket annat språk som helst!
• @TheProHands Detta betraktas som tokens, inte som en AST.

Jag vet att den här frågan är 4+ år gammal men jag tycker att jag borde lägga till ett mer detaljerat svar.

Abstrakta syntax Träd skapas inte annorlunda än andra träd; det mer sanna påståendet i det här fallet är att syntaxträdnoder har en varierande mängd noder SOM BEHÖVS.

Ett exempel är binära uttryck som 1 + 2 Ett enkelt uttryck som som skulle skapa en enda rotnod med en höger och vänster nod som innehåller data om siffrorna.På C-språk skulle det ”se ut 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; }; 

Din fråga var också hur man ska korsa? Korsning i detta fall kallas Besöksnoder . Att besöka varje nod kräver att du använder varje nodtyp för att avgöra hur varje Syntax-nods data ska utvärderas.

Här är ett annat exempel på det i C där jag helt enkelt skriver ut innehållet i varje nod:

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

Lägg märke till hur funktionen rekursivt besöker varje nod enligt vilken typ av nod vi har att göra med.

Låt oss lägga till ett mer komplext exempel, en if -konstruktion! Kom ihåg att om uttalanden kan också ha en valfri annars-sats. Låt oss lägga till if-else-satsen i vår ursprungliga nodstruktur. Kom ihåg att om uttalanden själva också kan ha om uttalanden, så kan ett slags rekursion inom vårt nodsystem uppstå. Annat uttalanden är valfria så att fältet elsestmt kan vara NULL som den rekursiva besökarfunktionen kan ignorera.

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

tillbaka i vår nodbesöksutskriftsfunktion som heter AST_PrintNode, kan vi rymma if AST-konstruktion genom att lägga till denna C-kod:

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å enkelt som det! Sammanfattningsvis är syntaxträdet inte mycket mer än ett träd av en märkt sammansättning av trädet och dess data själv!