Azt hiszem, megértem az AST célját, és korábban már építettem néhány fa szerkezetet, de soha nem AST-t. Többnyire zavart vagyok. mert a csomópontok szövegek és nem számok, ezért nem tudok elképzelni egy jó módot egy token / string bevitelére, amikor néhány kódot elemzek.
Például, amikor megnéztem az AST diagramjait, a változó és az értéke egyenlőségjelű csomópontok voltak. Ez számomra teljesen logikus, de hogyan tudnám ezt végrehajtani? azt hiszem, eseti alapon meg tudom csinálni, hogy amikor egy “=” -be botlom, azt csomópontként használom, és hozzáadom a “=” előtti elemzett értéket levélként. Csak rossznak tűnik, mert valószínűleg “d” tonna és rengeteg dologra van szükség, a szintaxistól függően.
És akkor újabb problémám támadt, hogy hogyan halad a fa? Végigmegyek a magasságon, és visszamegyek egy csomópontra, amikor eltaláltam az alját, és ugyanezt tegyem a szomszédjához is?
Rengeteg diagramot láttam az AST-ken, de Nem találtam egy meglehetősen egyszerű példát a kódra, amely valószínűleg segítene.
Megjegyzések
- A kulcsfogalom, amelyet ‘ hiányzik rekurzió . A rekurzió ellentétes értelmű, és ‘ minden tanuló számára más, amikor végre ‘ kattintson ‘ velük, de rekurzió nélkül egyszerűen nincs mód az értelmezés megértésére (és nagyon sok más számítási témára is) ).
- Rekurziót kapok, csak azt gondoltam, hogy ‘ nehéz ebben az esetben megvalósítani. Valójában rekurziót akartam használni, és végül sok olyan eset, amely nem ‘ nem működne egy általános megoldás mellett. Gdhoward ‘ válasza segít nekem nagyon sok.
- Lehetséges, hogy gyakorlatként felépít egy RPN számológépet . Ez nem válaszol a kérdésedre, de megtaníthat néhány szükséges készséget.
- Valójában korábban készítettem egy RPN kalkulátort. A válaszok sokat segítettek nekem, és azt hiszem, most már elkészíthetek egy alap AST-t. Köszönöm!
Válasz
A rövid válasz az, hogy veremeket használ. Ez jó példa, de alkalmazom egy AST-re.
FYI, ez Edsger Dijkstra Shunting-Yard algoritmus .
Ebben az esetben egy operátor verem és egy kifejezés verem lesz. Mivel a számok a legtöbb nyelvben kifejezéseknek számítanak, a kifejezés verem használatával tárolom őket.
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()
(Kérem, legyen kedves a kódommal kapcsolatban. Tudom, hogy nem robusztus; csak álkódnak kell lennie.)
Mindenesetre, amint a kódból is látható, önkényes a kifejezések lehetnek operandusok más kifejezésekhez. Ha a következő bemenettel rendelkezik:
5 * 3 + (4 + 2 % 2 * 8) az általam írt kód létrehozta ezt az AST-t:
+ / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 És amikor elő akarja állítani az adott AST kódját, akkor egy rendelési fa áthaladást hajt végre . meglátogat egy levélcsomópontot (számmal), konstansot generál, mert a fordítónak ismernie kell az operandusértékeket. Amikor egy csomópontot meglátogat egy operátorral, akkor létrehozza a megfelelő utasítást az operátortól. Például a “+” operátor ad egy “hozzáadás” utasítást.
Megjegyzések
- Ez működik r operátorok, akik balról jobbra asszociativitással rendelkeznek, nem pedig jobbról balra.
- @Simon, rendkívül egyszerű lenne hozzáadni a képességet a jobbról balra operátorok számára. A legegyszerűbb az, ha egy keresőtáblát adunk hozzá, és ha egy operátor jobbról balra, egyszerűen fordítsuk meg az operandusok sorrendjét.
- @Simon Ha mindkettőt támogatni szeretné, akkor ‘ jobb, ha teljes dicsőségében megkeresi a tolató udvar algoritmusát . Az algoritmusok előrehaladtával ez a ‘ abszolút cracker.
Válasz
Jelentős különbség van abban, hogy az AST-t hogyan ábrázolják a tesztben (egy fa, amelynek számai / változói vannak a levélcsomópontokban, és szimbólumok a belső csomópontokban), és hogyan valósítják meg valójában.
A tipikus Az AST (egy OO nyelven) megvalósításakor a polimorfizmus erősen felhasználásra kerül. Az AST csomópontjai általában különféle osztályokkal valósulnak meg, amelyek mindegyike egy közös ASTNode osztályból származik. Az általad feldolgozott nyelv minden szintaktikai konstrukciójához lesz egy osztály, amely az adott konstrukciót az AST-ben képviseli, például ConstantNode (konstansok esetén, például 0x10 vagy 42), VariableNode (változónevekhez), AssignmentNode (hozzárendelési műveletekhez), ExpressionNode (általános kifejezésekhez) stb.
Minden egyes csomóponttípus meghatározza, hogy az adott csomópontnak vannak-e gyermekei, hány és esetleg milyen típusú. A ConstantNode -nek általában nem lesz gyermeke, egy AssignmentNode -nek kettő, egy ExpressionBlockNode -nek pedig tetszőleges számú gyermeke van.
Az AST-t az elemző készíti el, aki tudja, hogy melyik konstrukciót elemezte éppen, így elkészítheti a megfelelő típusú AST-csomópontot.
Utazáskor az AST, a csomópontok polimorfizmusa játszik igazán szerepet. Az ASTNode alap meghatározza a csomópontokon végrehajtható műveleteket, és minden egyes csomóponttípus végrehajtja ezeket a műveleteket az adott nyelvi konstrukció sajátos módján.
Válasz
Az AST felépítése a forrásszövegből ” egyszerűen ” elemzés . Hogy pontosan hogyan történik, az értelmezett hivatalos nyelvtől és a megvalósítástól függ. Használhat olyan elemzőgenerátorokat, mint menhir (az Ocaml számára) , GNU bison flex vagy ANTLR stb. használatával. Gyakran ” manuálisan ” néhány rekurzív süllyesztő elemző kódolásával (lásd: ezt a választ , amely elmagyarázza a miérteket). Az elemzés kontextus szerinti aspektusát gyakran máshol hajtják végre (szimbólumtáblák, attribútumok, stb.).
A gyakorlatban azonban az AST sokkal összetettebb, mint amiben hiszel. Például egy olyan fordítóban, mint a GCC , az AST megőrzi a forrás helyét és néhány gépelési információt. Olvassa el a Általános fák és a GIMPLE tudnivalókat a GCC-ben, és nézze meg a gcc / tree.def . Fontolja meg, hogy ha a C vagy a C ++, vagy a Fortran vagy az Ada dolgot akarja feldolgozni, írja meg saját GCC bővítményét . BTW, nézzen bele az elavult GCC MELT oldalba (amelyet & megvalósítottam), ez releváns az Ön számára kérdés. Olvassa el a Sárkány könyvet . Lásd még ezt a jelentéstervezetet referenciaként, valamint a RefPerSys projektet és sokak forráskódját. egyéb nyílt forráskódú projekt (beleértve a Ocaml vagy Guile vagy SBCL vagy Jq ) a github vagy gitlab példaként.
Megjegyzések
- I ‘ Lua tolmácsot készítek a forrásszöveg elemzésére és egy tömbben való átalakításra JS-ben. AST-nak tekinthetem? Én ‘ ilyesmit kéne tennem:
--My comment #1 print("Hello, ".."world.")átalakul “[{” típus “: ” – “, ” content “: ” 1. megjegyzésem “}, {” típus “: ” hívás “, ” név “: ” print “, ” érvek “: [[{” type “: ” str “, ” művelet “: ” .. “, ” tartalom “: ” Kedves, “}, {” type “: ” str “, ” tartalom “: ” világ. “}]]]}]] “Szerintem ‘ sokkal egyszerűbb a JS-ben, mint bármely más nyelv! - @TheProHands Ezt tokeneknek tekintjük, nem pedig AST-nek.
Válasz
Tudom, hogy ez a kérdés már több mint 4 éves, de úgy érzem, hogy részletesebb választ kellene adnom. az igazabb állítás ebben az esetben az, hogy a Szintaxisfa csomópontokban szükség szerint sokféle csomópont van.
Példaként említhetjük a bináris kifejezéseket, például a 1 + 2 ez egyetlen gyökércsomópontot hozna létre, amely egy jobb és bal csomópontot tartalmaz, amely a számok adatait tárolja.C nyelven valami ilyesmi lehet:
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; }; A kérdésed az is volt, hogy hogyan lehet áthaladni? Ebben az esetben a bejárást Látogató csomópontok . Az egyes csomópontok meglátogatásához minden csomópont-típust kell használni az egyes Szintaxis-csomópontok adatainak kiértékeléséhez.
Itt van egy másik példa erre a C-ben, ahol egyszerűen kinyomtatom az egyes csomópontok tartalmát:
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; } } Figyelje meg, hogy a függvény hogyan látogat rekurzív módon mindegyik csomópont attól függően, hogy milyen típusú csomópontokkal van dolgunk.
Adjunk hozzá egy összetettebb példát, egy if utasításszerkezetet! Ne feledje, hogy tartalmazhat opcionális else záradékot is. Adjuk hozzá az if-else utasítást az eredeti csomópontstruktúránkhoz. Ne feledje, hogy ha maguknak a kijelentéseknek is lehetnek if utasításai, akkor egyfajta rekurzió léphet fel a csomópont rendszerünkön belül. A többi utasítás nem kötelező, így az elsestmt mező NULL lehet, amelyet a rekurzív látogató függvény figyelmen kívül hagyhat.
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; }; vissza a AST_PrintNode elnevezésű csomópont látogatói nyomtatási függvényünkben a if utasítás AST konstrukcióját elhelyezhetjük a C kód hozzáadásával:
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; Ennyire egyszerű! Összefoglalva, a Szintaxisfa nem sokkal több, mint a fa és maga adatainak címkézett egyesülésének fája!