Cât de exact este creat un arbore de sintaxă abstractă?

Răspunsul scurt este că utilizați stive. Acesta este un bun exemplu, dar îl voi aplica unui AST.

FYI, acesta este Algoritmul Shunting-Yard .

În acest caz, voi folosi o stivă de operator și o stivă de expresie. Deoarece numerele sunt considerate expresii în majoritatea limbilor, voi folosi stiva de expresii pentru a le stoca.

 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ă rugăm să fiți amabili cu codul meu. Știu că nu este robust; se presupune că este doar pseudocod.)

Oricum, după cum puteți vedea din cod, arbitrar expresiile pot fi operanzi la alte expresii. Dacă aveți următoarea intrare:

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

codul pe care l-am scris ar produce acest AST:

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

Și atunci când doriți să produceți codul pentru AST respectiv, faceți o Transmiterea arborelui de comandă . vizitați un nod frunză (cu un număr), generați o constantă deoarece compilatorul trebuie să cunoască valorile operandului. Când vizitați un nod cu un operator, generați instrucțiunile corespunzătoare de la operator. De exemplu, „+” operatorul vă oferă o instrucțiune „adăugați”.

Comentarii

• Acest lucru funcționează pentru r operatorii care au asociativitate de la stânga la dreapta, nu de la dreapta la stânga.
• @Simon, ar fi extrem de simplu să adăugați capacitatea operatorilor de la dreapta la stânga. Cel mai simplu ar fi să adăugați un tabel de căutare și dacă un operator de la dreapta la stânga, inversați pur și simplu ordinea operanzilor.
• @ Simon Dacă doriți să le susțineți pe ambele, ‘ ar fi mai bine să căutați algoritmul de șantier în plină glorie. Pe măsură ce algoritmii merg, ‘ este un cracker absolut.

Există o diferență semnificativă între modul în care un AST este reprezentat în mod obișnuit în test (un arbore cu numere / variabile la nodurile frunze și simboluri la nodurile interioare) și modul în care este implementat de fapt.

implementarea unui AST (într-un limbaj OO) folosește intens polimorfismul. Nodurile din AST sunt de obicei implementate cu o varietate de clase, toate derivând dintr-o clasă comună ASTNode. Pentru fiecare construcție sintactică în limba pe care o prelucrați, va exista o clasă pentru reprezentarea acestei construcții în AST, cum ar fi ConstantNode (pentru constante, cum ar fi 0x10 sau 42), VariableNode (pentru numele variabilelor), AssignmentNode (pentru operații de atribuire), ExpressionNode (pentru expresii generice) etc.
Fiecare tip de nod specific specifică dacă acel nod are copii, câți și, eventual, de ce tip. Un ConstantNode nu va avea de obicei copii, un AssignmentNode va avea doi și un ExpressionBlockNode aveți orice număr de copii.

AST este construit de analizor, care știe ce construcție tocmai a analizat, deci poate construi tipul corect de nod AST.

Atunci când traversați AST, polimorfismul nodurilor intră într-adevăr în joc. Baza ASTNode definește operațiunile care pot fi efectuate pe noduri și fiecare tip de nod specific implementează acele operații în mod specific pentru acel construct de limbaj particular.

Construirea AST din textul sursă este ” pur și simplu ” analiză . Modul exact în care se face depinde de limbajul formal analizat și de implementare. Puteți utiliza generatoare de parser, cum ar fi menhir (pentru Ocaml) , GNU bison cu flex, sau ANTLR etc. etc. Se face adesea ” manual ” prin codificarea unor analizor recursiv descendent (consultați acest răspuns explicând de ce). Aspectul contextual al analizei se face adesea în altă parte (tabele de simboluri, atribute, ….).

Cu toate acestea, în practică AST sunt mult mai complexe decât ceea ce credeți. De exemplu, într-un compilator precum GCC AST păstrează informații despre locația sursă și unele informații de tastare. Citiți despre Copaci generici și GIMPLE în GCC și căutați în gcc / tree.def . Luați în considerare, dacă doriți să procesați C sau C ++ sau Fortran sau Ada, scriindu-vă propriul plugin GCC . BTW, uitați-vă și în interiorul caducului GCC MELT (pe care l-am proiectat & implementat), este relevant pentru dvs. întrebare. Citiți cartea Dragon . Consultați, de asemenea, acest raport pentru referințe și proiectul RefPerSys și codul sursă al multor alte proiecte open source (inclusiv Ocaml sau Guile sau SBCL sau Jq ) pe github sau gitlab ca exemple.

Comentarii

• ‘ fac un interpret Lua pentru a analiza textul sursă și a transforma într-o matrice în JS. Pot să-l consider un AST? ‘ ar trebui să fac așa ceva: --My comment #1 print("Hello, ".."world.") se transformă în `[{” tastați „: ” – „, ” content „: ” Comentariul meu # 1 „}, {” tip „: ” apel „, ” nume „: ” print „, ” argumente „: [[{” tastați „: ” str „, ” acțiune „: ” .. „, ” conținut „: ” Bună ziua, „}, {” tastați „: ” str „, ” conținut „: ” lume. „}]]}] „Cred că ‘ este mult mai simplu în JS decât orice altă limbă!
• @TheProHands Acest lucru ar fi considerat jetoane, nu un AST.

Știu că această întrebare are peste 4 ani, dar consider că ar trebui să adaug un răspuns mai detaliat.

Sintaxa abstractă a arborilor nu este creată diferit de ceilalți copaci; afirmația mai adevărată în acest caz este că nodurile din Arborele de Sintaxă au o cantitate variabilă de noduri CÂȚI ESTE NECESARĂ.

Un exemplu sunt expresiile binare precum 1 + 2 O expresie simplă ca care ar crea un singur nod rădăcină care deține un nod dreapta și stânga care deține datele despre numere.În limbajul C, ar arăta ceva de genul

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

Întrebarea dvs. a fost și cum să traversați? Traversarea în acest caz se numește Vizitarea nodurilor . Vizitarea fiecărui nod necesită utilizarea fiecărui tip de nod pentru a determina modul de evaluare a datelor fiecărui nod de sintaxă.

Iată un alt exemplu în C în care pur și simplu imprim conținutul fiecărui 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; } } 

Observați cum funcția vizitează recursiv fiecare nod în funcție de ce tip de nod avem de-a face.

Să adăugăm un exemplu mai complex, o construcție de instrucțiuni if! Amintiți-vă că, dacă instrucțiunile poate avea, de asemenea, o clauză else opțională. Să adăugăm instrucțiunea if-else la structura noastră de nod originală. Amintiți-vă că dacă instrucțiunile în sine pot avea și instrucțiuni if, atunci poate apărea un fel de recursivitate în sistemul nostru de noduri. Instrucțiunile Else sunt opționale, astfel încât câmpul elsestmt poate fi NULL pe care funcția de vizitator recursiv îl poate ignora.

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

înapoi în funcția de tipărire a vizitatorului nodului numită AST_PrintNode, putem găzdui declarația if construit AST adăugând acest cod 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; 

La fel de simplu! În concluzie, Arborele sintaxei nu este mult mai mult decât un arbore al unei uniuni etichetate a arborelui și a datelor sale în sine!