Jak přesně je vytvořen strom abstraktní syntaxe?

Krátká odpověď je, že používáte hromádky. Toto je dobrý příklad, ale použiji jej na AST.

FYI, toto je Algoritmus posunovacího dvora .

V tomto případě použiji zásobník operátorů a zásobník výrazů. Protože čísla jsou ve většině jazyků považována za výrazy, k jejich uložení použiji zásobník výrazů.

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

(Buďte prosím o mém kódu milí. Vím, že to není robustní; měl by to být jen pseudokód.)

Každopádně, jak vidíte z kódu, libovolné výrazy mohou být operandy jiných výrazů. Pokud máte následující vstup:

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

kód, který jsem napsal, by vytvořil toto AST:

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

A poté, když chcete vytvořit kód pro tento AST, proveďte Proškolení stromu objednávky . Když navštívíte uzel listu (s číslem), vygenerujete konstantu, protože překladač potřebuje znát hodnoty operandu. Když navštívíte uzel s operátorem, vygenerujete příslušnou instrukci od operátora. Například znak „+“ operátor vám dá instrukci „přidat“.

Komentáře

• Toto funguje pro r operátory, které mají asociativitu zleva doprava, nikoli zprava doleva.
• @Simon, bylo by extrémně jednoduché přidat možnosti pro operátory zprava doleva. Nejjednodušší by bylo přidat vyhledávací tabulku a pokud je operátor zprava doleva, jednoduše obráťte pořadí operandů.
• @Simon Pokud chcete podporovat oba, ‚ je lepší hledat algoritmus posunovacího dvora v plné kráse. Jak algoritmy jdou, je to ‚ absolutní cracker.

Existuje významný rozdíl mezi tím, jak je typicky v testu zobrazen AST (strom s čísly / proměnnými v uzlech listu a symboly ve vnitřních uzlech) a jak je ve skutečnosti implementován.

Typický implementace AST (v jazyce OO) velmi využívá polymorfismus. Uzly v AST jsou obvykle implementovány s různými třídami, všechny jsou odvozeny od běžné ASTNode třídy. Pro každý syntaktický konstrukt v jazyce, který zpracováváte, bude existovat třída pro reprezentaci tohoto konstruktu v AST, například ConstantNode (pro konstanty, například 0x10 nebo 42), VariableNode (pro názvy proměnných), AssignmentNode (pro operace přiřazení), ExpressionNode (pro obecné výrazy) atd.
Každý konkrétní typ uzlu určuje, zda má tento uzel děti, kolik a případně jakého typu. ConstantNode obvykle nebude mít žádné děti, AssignmentNode bude mít dvě a ExpressionBlockNode může mít libovolný počet dětí.

AST sestavuje syntaktický analyzátor, který ví, jaký konstrukt právě analyzoval, takže může vytvořit správný druh uzlu AST.

Při procházení AST, polymorfismus uzlů skutečně vstupuje do hry. Základní ASTNode definuje operace, které lze na uzlech provádět, a každý konkrétní typ uzlu implementuje tyto operace konkrétním způsobem pro daný konkrétní jazykový konstrukt.

Vytváření AST ze zdrojového textu je “ jednoduše “ analýza . Jak přesně se to dělá, záleží na analyzovaném formálním jazyce a implementaci. Můžete použít generátory analyzátorů jako menhir (pro Ocaml) , GNU bison s flex nebo ANTLR atd. Často se to děje “ ručně “ kódováním nějakého syntaktického analyzátoru sestupu (viz tato odpověď vysvětlující proč). Kontextový aspekt syntaktické analýzy se často provádí jinde (tabulky symbolů, atributy, ….).

V praxi jsou však AST mnohem složitější než to, čemu věříte. Například v kompilátoru jako GCC udržuje AST informace o umístění zdroje a některé informace o psaní. Přečtěte si o Obecných stromech a GIMPLE v GCC a podívejte se do jeho gcc / tree.def . Zvažte, pokud chcete zpracovat C nebo C ++ nebo Fortran nebo Ada, napsat svůj vlastní plugin GCC . BTW, podívejte se také dovnitř zastaralé GCC MELT (kterou jsem navrhl & implementován), je relevantní pro váš otázka. Přečtěte si knihu Dragon . Viz také tento koncept přehledu referencí a projekt RefPerSys a zdrojový kód mnoha další open source projekty (včetně Ocaml nebo Guile nebo SBCL nebo Jq ) na github nebo gitlab jako příklady.

Komentáře

• I ‚ vytvářím tlumočníka Lua, který analyzuje zdrojový text a transformuje se do pole v JS. Mohu to považovat za AST? Mám ‚ udělat něco takového: --My comment #1 print("Hello, ".."world.") se transformuje na „[{“ typ „: “ – „, “ content „: “ Můj komentář č. 1 „}, {“ typ „: “ volání „, “ name „: “ tisk „, “ argumenty „: [[{“ zadejte „: “ str „, “ akce „: “ .. „, “ obsah „: “ Dobrý den, „}, {“ typ „: “ str „, “ obsah „: “ svět. „}]]}]] „Myslím, že ‚ je v JS mnohem jednodušší než jakýkoli jiný jazyk!
• @TheProHands To by bylo považováno za tokeny, nikoli za AST.

Vím, že tato otázka je stará více než 4 roky, ale mám pocit, že bych měl přidat podrobnější odpověď.

Abstrakt Syntaxe Stromy se nevytvářejí nijak odlišně od ostatních stromů; pravdivějším tvrzením v tomto případě je, že uzly Syntax Tree mají podle potřeby variadické množství uzlů.

Příkladem jsou binární výrazy jako 1 + 2 Jednoduchý výraz jako to by vytvořilo jediný kořenový uzel, který bude mít pravý a levý uzel, který obsahuje data o číslech.V jazyce C to „vypadá nějak jako

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

Vaše otázka byla také, jak procházet? Traverzování se v tomto případě nazývá Návštěvní uzly . Při návštěvě každého uzlu je nutné použít každý typ uzlu k určení, jak vyhodnotit data každého uzlu Syntaxe.

Zde je další příklad toho v C, kde jednoduše vytisknu obsah každého uzlu:

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

Všimněte si, jak funkce rekurzivně navštěvuje každý uzel podle toho, s jakým typem uzlu jednáme.

Pojďme přidat komplexnější příklad, konstrukci příkazu if! Připomeňme, že pokud příkazy může mít také volitelnou klauzuli else. Pojďme přidat příkaz if-else do naší původní struktury uzlu. Nezapomeňte, že pokud samotné příkazy mohou mít i příkazy if, může dojít k jakési rekurzi v rámci našeho uzlového systému. Jiné příkazy jsou volitelné, takže pole elsestmt může mít hodnotu NULL, kterou může rekurzivní funkce návštěvníka ignorovat.

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

zpět v naší tiskové funkci návštěvníka uzlu s názvem AST_PrintNode můžeme přizpůsobit konstrukci příkazu if AST přidáním tohoto kódu 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; 

Tak jednoduché! Závěrem lze říci, že Syntax Tree není nic jiného než strom označeného spojení stromu a jeho dat samotných!