januar 28, 2021
Articles
Ingen kommentarer

Hvordan blir det opprettet et abstrakt syntaks-tre?

Jeg tror jeg forstår målet med en AST, og jeg har bygget et par trestrukturer før, men aldri en AST. Jeg er mest forvirret fordi nodene er tekst og ikke tall, så jeg kan ikke tenke på en fin måte å legge inn et token / streng når jeg analyserer noe kode.

For eksempel, når jeg så på diagrammer over AST «, var variabelen og dens verdi bladnoder til et likhetstegn. Dette gir full mening for meg, men hvordan ville jeg gjøre for å implementere dette? Jeg antar at jeg kan gjøre det fra sak til sak, slik at når jeg snubler over et «=» bruker jeg det som en node, og legger til verdien som er analysert foran «=» som bladet. Det virker bare galt, fordi jeg sannsynligvis må lage saker for tonnevis av ting, avhengig av syntaksen.

Og så kom jeg på et annet problem, hvordan krysses treet? Går jeg helt ned i høyden, og går tilbake opp en node når jeg treffer bunnen, og gjør det samme for naboen?

Jeg har sett mange diagrammer på AST, men Jeg kunne ikke finne et ganske enkelt eksempel på en i kode, noe som sannsynligvis ville hjelpe.

Kommentarer

  • Nøkkelbegrepet du ‘ mangler er rekursjon . Rekursjon er en slags kontraintuitiv, og den ‘ er forskjellig for hver elev når den endelig ‘ klikk ‘ med dem, men uten rekursjon er det rett og slett ingen måte å forstå parsing (og mange andre beregningsemner også ).
  • Jeg får rekursjon, jeg tenkte bare at det ‘ ville være vanskelig å implementere det i dette tilfellet. Jeg ville egentlig bruke rekursjon og endte opp med mange saker som ikke ‘ ikke fungerer for en generell løsning. Gdhoward ‘ s svar hjelper meg mye akkurat nå.
  • Det kan være trening å bygge en RPN-kalkulator som en øvelse. Det vil ikke svare på spørsmålet ditt, men kan lære noen nødvendige ferdigheter.
  • Jeg har faktisk bygget en RPN-kalkulator før. Svarene hjalp meg veldig, og jeg tror jeg kan lage en grunnleggende AST nå. Takk!

Svar

Det korte svaret er at du bruker stabler. Dette er et godt eksempel, men jeg vil bruke det til en AST.

FYI, dette er Edsger Dijkstra «s Shunting-Yard Algorithm .

I dette tilfellet vil jeg bruke en operatørstak og en uttrykksstak. Siden tall er ansett som uttrykk på de fleste språk, vil jeg bruke uttrykkstakken til å lagre 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 snill med koden min. Jeg vet at den ikke er robust; den skal bare være pseudokode.)

Uansett, som du kan se fra koden, vilkårlig uttrykk kan være operander til andre uttrykk. Hvis du har følgende innspill: 

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

koden jeg skrev ville produsere denne AST: 

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

Og så når du vil produsere koden for den AST, gjør du en Gjennomgang av ordre treet . Når du besøker en bladnode (med et tall), genererer du en konstant fordi kompilatoren trenger å kjenne operandverdiene. Når du besøker en node med en operatør, genererer du den riktige instruksjonen fra operatøren. For eksempel «+» operatøren gir deg en «legg til» instruksjon.

Kommentarer

  • Dette fungerer fo r operatører som har fra venstre til høyre associativitet, ikke fra høyre til venstre.
  • @Simon, det ville være ekstremt enkelt å legge til muligheten for operatører fra høyre til venstre. Det enkleste ville være å legge til et oppslagstabell, og hvis en operatør høyre mot venstre, bare snu rekkefølgen på operandene.
  • @Simon Hvis du vil støtte begge deler, ‘ har det bedre å slå opp shunt yard-algoritmen i sin fulle prakt. Som algoritmer går, er ‘ en absolutt krakker.

Svar

Det er en signifikant forskjell mellom hvordan en AST typisk er avbildet i testen (et tre med tall / variabler ved bladnodene og symboler ved indre noder) og hvordan det faktisk implementeres.

Det typiske implementering av en AST (på et OO-språk) gjør tung bruk av polymorfisme. Nodene i AST er vanligvis implementert med en rekke klasser, som alle kommer fra en felles ASTNode klasse. For hver syntaktiske konstruksjon i språket du behandler, vil det være en klasse for å representere den konstruksjonen i AST, for eksempel ConstantNode (for konstanter, for eksempel 0x10 eller 42), VariableNode (for variabelnavn), AssignmentNode (for oppdragsoperasjoner), ExpressionNode (for generiske uttrykk) osv.
Hver spesifikke nodetype angir om den noden har barn, hvor mange og muligens av hvilken type. En ConstantNode vil vanligvis ikke ha barn, en AssignmentNode vil ha to og en ExpressionBlockNode har et hvilket som helst antall barn.

AST blir bygget av parseren, som vet hvilken konstruksjon den nettopp har analysert, slik at den kan konstruere riktig type AST-node.

Når du krysser AST, polymorfismen i nodene kommer virkelig inn i bildet. Basen ASTNode definerer operasjonene som kan utføres på nodene, og hver spesifikke nodetype implementerer disse operasjonene på den spesifikke måten for den aktuelle språkkonstruksjonen.

Svar

Å bygge AST fra kildeteksten er » ganske enkelt » parsing . Hvor nøyaktig det gjøres, avhenger av det analyserte formelle språket og gjennomføringen. Du kan bruke parsergeneratorer som menhir (for Ocaml) , GNU bison med flex, eller ANTLR osv. Det gjøres ofte » manuelt » ved å kode noen rekursiv nedstigningsparser (se dette svaret forklarer hvorfor). Det kontekstuelle aspektet ved parsing gjøres ofte andre steder (symboltabeller, attributter, ….).

Imidlertid er AST i praksis mye mer komplisert enn det du tror. I en kompilator som GCC beholder AST for eksempel informasjon om kildeplassering og litt informasjon om skriving. Les om Generiske trær og GIMPLE i GCC og se inn i gcc / tree.def . Tenk, hvis du vil behandle C eller C ++ eller Fortran eller Ada, skriver du din egen GCC-plugin . BTW, se også inne i det foreldede GCC MELT (som jeg har designet & implementert), det er relevant for din spørsmål. Les Dragon-boken . Se også dette utkastet for referanser, og RefPerSys -prosjektet og kildekoden til mange andre åpen kildekode -prosjekter (inkludert Ocaml eller Guile eller SBCL eller Jq ) på github eller gitlab som eksempler.

Kommentarer

  • Jeg ‘ Jeg lager en Lua-tolk for å analysere kildetekst og transformere i en matrise i JS. Kan jeg betrakte det som en AST? Jeg ‘ skal gjøre noe sånt som dette: --My comment #1 print("Hello, ".."world.") forvandles til `[{» skriv «: » – «, » content «: » Min kommentar # 1 «}, {» skriv «: » ring «, » navn «: » skriv ut «, » argumenter «: [[{{div div = «0edb01244e»>

type «: » str «, » handling «: » .. «, » innhold «: » Hei, «}, {» skriv «: » str «, » innhold «: » verden. «}]]}] `Jeg tror det ‘ er mye enklere i JS enn hvilket som helst annet språk!

  • @TheProHands Dette betraktes som tokens, ikke som en AST.

    • Svar

    Jeg vet at dette spørsmålet er 4+ år gammelt, men jeg føler at jeg bør legge til et mer detaljert svar.

    Abstrakte syntaks Trær er ikke skapt annerledes enn andre trær; den mer sanne påstanden i dette tilfellet er at syntaks-tre-noder har en variabel mengde noder SOM TRENGES.

    Et eksempel er binære uttrykk som 1 + 2 Et enkelt uttrykk som som ville skape en enkelt rotnode som inneholdt en høyre og venstre node som inneholder dataene om tallene.På C-språk ville 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; };

    Spørsmålet ditt var også hvordan man skulle krysse? Traversering i dette tilfellet kalles Besøksnoder . Å besøke hver node krever at du bruker hver nodetype for å bestemme hvordan du skal evaluere dataene til hver syntaksnode.

    Her er et annet eksempel på det i C hvor jeg bare skriver ut innholdet i 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; } }

    Legg merke til hvordan funksjonen rekursivt besøker hver node i henhold til hvilken type node vi har å gjøre med.

    La oss legge til et mer komplekst eksempel, en if -konstruksjon! Husk at hvis utsagn kan også ha en valgfri annet ledd. La oss legge til if-else-setningen i vår opprinnelige nodestruktur. Husk at hvis utsagn i seg selv også kan ha hvis utsagn, så kan det oppstå en slags rekursjon i vårt nodesystem. Andre utsagn er valgfrie, så elsestmt -feltet kan være NULL som den rekursive besøksfunksjonen 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; };

    tilbake i vår utskriftsfunksjon for noderbesøkende kalt AST_PrintNode, kan vi imøtekomme if AST-konstruksjon ved å legge til denne C-koden: 

    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! Avslutningsvis er syntakstreet ikke mye mer enn et tre av en merket forening av treet og dets data selv!

    Legg igjen en kommentar

    Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *