Kuinka abstrakti syntaksipuu luodaan tarkalleen?

Lyhyt vastaus on, että käytät pinoja. Tämä on hyvä esimerkki, mutta sovellan sitä AST: hen.

FYI, tämä on Edsger Dijkstra Vaihtopiha-algoritmi .

Tässä tapauksessa käytän operaattoripinoa ja lausekepinoa. Koska numeroita pidetään lausekkeina useimmilla kielillä, käytän lausekepinoa niiden tallentamiseen.

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

(Ole kiltti koodissani. Tiedän, että se ei ole vankka; sen pitäisi vain olla pseudokoodi.)

Joka tapauksessa, kuten koodista voi nähdä, mielivaltainen lausekkeet voivat olla operandeja muille lausekkeille. Jos sinulla on seuraava syöttö:

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

kirjoittamani koodi tuottaisi tämän AST: n:

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

Ja sitten kun haluat tuottaa koodin kyseiselle AST: lle, teet postitustilauspuun läpikulun . vierailet lehtisolmussa (numerolla), luodaan vakio, koska kääntäjän on tiedettävä operandiarvot. Kun vierailet solmussa operaattorin kanssa, luot operaattorilta sopivan käskyn. Esimerkiksi ”+” operaattori antaa sinulle ”lisäys” -komennon.

Kommentit

• Tämä toimii r-operaattoreita, joilla on vasemmalta oikealle -liittyvyys, ei oikealta vasemmalle.
• @Simon, olisi erittäin helppoa lisätä valmiudet oikealta vasemmalle -operaattoreille. Yksinkertaisin olisi lisätä hakutaulukko ja jos operaattori oikealta vasemmalle, käännä vain operandien järjestys.
• @Simon Jos haluat tukea molempia, ’ on parempi etsiä vaihto-piha-algoritmi sen täydellisessä loistossa. Algoritmien kulkiessa ’ on ehdoton cracker.

AST: n tyypillinen kuvaus testissä (puu, jossa on numerot / muuttujat lehtisolmuissa ja symbolit sisäsolmuissa) ja sen todellinen toteutus eroavat toisistaan.

Tyypillinen AST: n käyttöönotto (OO-kielellä) käyttää voimakkaasti polymorfismia. AST: n solmut toteutetaan tyypillisesti useilla luokilla, jotka kaikki johtuvat yhteisestä ASTNode luokasta. Jokaiselle käsitellyn kielen syntaktiselle rakenteelle on luokka, joka edustaa kyseistä rakennetta AST: ssä, kuten ConstantNode (vakioille, kuten 0x10 tai 42), VariableNode (muuttujien nimille), AssignmentNode (määritystoiminnoille), ExpressionNode (yleisille lausekkeille) jne.
Jokainen solmutyyppi määrittää, onko kyseisellä solmulla lapsia, kuinka monta ja mahdollisesti minkä tyyppistä. ConstantNode ei yleensä ole lapsia, AssignmentNode on kaksi ja ExpressionBlockNode voi sinulla on mikä tahansa määrä lapsia.

AST saa jäsennin, joka tietää minkä rakenteen se on juuri jäsennetty, jotta se voi rakentaa oikeanlaisen AST-solmun.

Kun kulkee AST, solmujen polymorfismi tulee todella pelaamaan. Tukiasema ASTNode määrittelee toiminnot, jotka voidaan suorittaa solmuille, ja kukin tietty solmutyyppi toteuttaa nämä toiminnot tietyllä tavalla kyseiselle kielirakenteelle.

AST: n rakentaminen lähdetekstistä on ” yksinkertaisesti ” jäsentäminen . Se, miten se tehdään, riippuu jäsennetystä virallisesta kielestä ja toteutuksesta. Voit käyttää jäsenningeneraattoreita, kuten menhir (Ocamlille) , GNU bison kanssa flex tai ANTLR jne. jne. Se tehdään usein ” manuaalisesti ” koodaamalla jokin rekursiivinen laskeutumisen jäsennin (katso tämä vastaus selittää miksi). Parsinnan kontekstuaalinen osa tehdään usein muualla (symbolitaulukot, attribuutit jne.).

Käytännössä AST ovat kuitenkin paljon monimutkaisempia kuin uskot. Esimerkiksi kääntäjässä, kuten GCC , AST pitää lähteen sijaintitiedot ja joitain kirjoitustietoja. Lue geneerisistä puista ja GIMPLE GCC: stä ja katso sen gcc / tree.def . Harkitse, jos haluat käsitellä C: tä tai C ++: ta tai Fortrania tai Adaa, kirjoittamalla oman GCC-laajennuksen . BTW, katso myös vanhentuneen GCC-sulan (jonka olen suunnitellut & toteuttanut) sisälle, se on merkitystä kysymys. Lue lohikäärmekirja . Katso myös tämä luonnos -raportti viitteiksi, RefPerSys -projekti ja monien lähdekoodi muut avoimen lähdekoodin projektit (mukaan lukien Ocaml tai Guile tai SBCL tai Jq ) github tai gitlab esimerkkeinä.

Kommentit

• I ’ m tekemällä Lua-tulkin jäsentämään lähdetekstiä ja muuntamaan taulukossa JS: ssä. Voinko pitää sitä AST: ksi? Minun ’ minun pitäisi tehdä jotain tällaista: --My comment #1 print("Hello, ".."world.") muuntuu muotoon [{” kirjoita ”: ” – ”, ” content ”: ” Kommenttini # 1 ”}, {” type ”: ” kutsu ”, ” nimi ”: ” tulosta ”, ” argumentit ”: [[{” tyyppi ”: ” str ”, ” toiminto ”: ” .. ”, ” sisältö ”: ” Hei, ”}, {” type ”: ” str ”, ” sisältö ”: ” maailma. ”}]]]]]] ”Mielestäni se on ’ paljon yksinkertaisempi JS: ssä kuin mikä tahansa muu kieli!
• @TheProHands Tätä pidetään merkkeinä, ei AST: nä.

Tiedän, että tämä kysymys on yli 4 vuotta vanha, mutta mielestäni minun pitäisi lisätä tarkempi vastaus.

Abstraktin syntaksin puut luodaan eri tavalla kuin muut puut; totta toteamus tässä tapauksessa on, että syntaksipuun solmuissa on vaihteleva määrä solmuja tarpeen mukaan.

Esimerkki on binaarilausekkeet, kuten 1 + 2 Yksinkertainen lauseke kuten joka loisi yhden juurisolmun, jolla on oikea ja vasen solmu, joka pitää sisällään tietoja numeroista.C-kielellä se ”näyttää jotain tältä:

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

Kysymyksesi oli myös kuinka kulkea? Tässä tapauksessa liikkumista kutsutaan nimellä Vierailusolmut . Kunkin solmun vieraileminen edellyttää, että käytät kutakin solmutyyppiä määrittämään, miten kunkin syntaksisolmun tiedot arvioidaan.

Tässä on toinen esimerkki C: stä, jossa tulostan yksinkertaisesti jokaisen solmun sisällön:

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

Huomaa, kuinka funktio vierailee rekursiivisesti kukin solmu sen mukaan, minkä tyyppisen solmun kanssa olemme tekemisissä.

Lisätään monimutkaisempi esimerkki if -lausekekonstruktio! Muistathan, että jos lauseet voi olla myös valinnainen muu lauseke. Lisätään ”if-else” käsky alkuperäiseen solmurakenteeseen. Muista, että jos lausekkeilla itsellään voi olla myös if-lauseita, niin solmujärjestelmässämme voi tapahtua eräänlainen rekursio. Muut lauseet ovat valinnaisia, joten elsestmt -kenttä voi olla NULL, jonka rekursiivinen vierailijafunktio voi jättää huomioimatta.

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

takaisin solmun vierailijoiden tulostustoiminnossa nimeltä AST_PrintNode voimme sijoittaa if -lausekkeen AST-rakenteen lisäämällä tämän C-koodin:

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; 

Niin yksinkertaista! Yhteenvetona voidaan todeta, että syntaksipuu ei ole paljon muuta kuin puun ja sen tietojen tunnisteellisen yhdistelmän puu!