Come viene creato esattamente un albero di sintassi astratto?

La risposta breve è che usi gli stack. Questo è un buon esempio, ma lo applicherò a un AST.

Cordiali saluti, questo è il Shunting-Yard Algorithm .

In questo caso, userò uno stack di operatori e uno stack di espressioni. Poiché i numeri sono considerati espressioni nella maggior parte delle lingue, userò lo stack di espressioni per memorizzarli.

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

(Sii gentile con il mio codice. So che non è robusto; dovrebbe essere solo uno pseudocodice.)

Comunque, come puoi vedere dal codice, arbitrario le espressioni possono essere operandi per altre espressioni. Se hai il seguente input:

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

il codice che ho scritto produrrebbe questo AST:

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

E poi, quando vuoi produrre il codice per quellAST, esegui un Post Order Tree Traversal . Quando visiti un nodo foglia (con un numero), generi una costante perché il compilatore ha bisogno di conoscere i valori delloperando. Quando visiti un nodo con un operatore, generi listruzione appropriata dalloperatore. Ad esempio, il “+” ti dà unistruzione “add”.

Commenti

• Funziona per r operatori che hanno lassociatività da sinistra a destra, non da destra a sinistra.
• @Simon, sarebbe estremamente semplice aggiungere la funzionalità per gli operatori da destra a sinistra. Il più semplice sarebbe aggiungere una tabella di ricerca e se un operatore da destra a sinistra, invertire semplicemente lordine degli operandi.
• @Simon Se vuoi supportare entrambi, ‘ è meglio cercare l algoritmo di smistamento nel suo massimo splendore. Come funzionano gli algoritmi, questo ‘ è un vero e proprio cracker.

Esiste una differenza significativa tra il modo in cui un AST viene tipicamente rappresentato nel test (un albero con numeri / variabili sui nodi foglia e simboli sui nodi interni) e come viene effettivamente implementato.

limplementazione di un AST (in un linguaggio OO) fa un uso massiccio del polimorfismo. I nodi nellAST sono tipicamente implementati con una varietà di classi, tutte derivanti da una classe ASTNode comune. Per ogni costrutto sintattico nella lingua che stai elaborando, ci sarà una classe per rappresentare quel costrutto nellAST, come ConstantNode (per le costanti, come 0x10 o 42), VariableNode (per nomi di variabili), AssignmentNode (per operazioni di assegnazione), ExpressionNode (per espressioni generiche), ecc.
Ogni tipo di nodo specifico specifica se quel nodo ha figli, quanti e possibilmente di che tipo. Un ConstantNode normalmente non ha figli, un AssignmentNode ne avrà due e un ExpressionBlockNode può avere un numero qualsiasi di figli.

LAST viene costruito dal parser, chissà quale costrutto ha appena analizzato, in modo che possa costruire il giusto tipo di nodo AST.

Quando si attraversa lAST, il polimorfismo dei nodi entra davvero in gioco. La base ASTNode definisce le operazioni che possono essere eseguite sui nodi e ogni specifico tipo di nodo implementa tali operazioni nel modo specifico per quel particolare costrutto di linguaggio.

La creazione dellAST dal testo di origine è ” semplicemente ” analisi . Il modo esatto in cui viene eseguito dipende dal linguaggio formale analizzato e dallimplementazione. Puoi utilizzare generatori di parser come menhir (per Ocaml) , GNU bison con flex o ANTLR ecc. ecc. Spesso è fatto ” manualmente ” codificando un parser discendente ricorsivo (vedi questa risposta che spiega perché). Laspetto contestuale dellanalisi è spesso svolto altrove (tabelle di simboli, attributi, …).

Tuttavia, in pratica gli AST sono molto più complessi di quanto si crede. Ad esempio, in un compilatore come GCC , lAST conserva le informazioni sulla posizione della sorgente e alcune informazioni sulla digitazione. Leggi alberi generici e GIMPLE in GCC e guarda allinterno del suo gcc / tree.def . Considera, se desideri elaborare C o C ++ o Fortran o Ada, di scrivere il tuo plug-in GCC . A proposito, guarda anche allinterno dellobsoleto GCC MELT (che ho progettato & implementato), è pertinente al tuo domanda. Leggi il libro sul drago . Consulta anche questa bozza del rapporto per i riferimenti e il progetto RefPerSys e il codice sorgente di molti altri progetti open source (inclusi Ocaml o Guile o SBCL o Jq ) su github o gitlab come esempi.

Commenti

• Io ‘ sto creando un interprete Lua per analizzare il testo sorgente e trasformarlo in un array in JS. Posso considerarlo un AST? ‘ dovrei fare qualcosa del genere: --My comment #1 print("Hello, ".."world.") si trasforma in “[{” digita “: ” – “, ” content “: ” Il mio commento # 1 “}, {” digita “: ” chiama “, ” name “: ” print “, ” argomenti “: [[{” tipo “: ” str “, ” azione “: ” .. “, ” contenuto “: ” Ciao, “}, {” digita “: ” str “, ” content “: ” world. “}]]}] “Penso che ‘ sia molto più semplice in JS rispetto qualsiasi altra lingua!
• @TheProHands Questo sarebbe considerato token, non un AST.

So che questa domanda ha più di 4 anni, ma sento di dover aggiungere una risposta più dettagliata.

Gli alberi sintattici astratti non sono creati diversamente dagli altri alberi; laffermazione più vera in questo caso è che i nodi dellalbero della sintassi hanno una quantità variadica di nodi QUANTO RICHIESTO.

Un esempio sono espressioni binarie come 1 + 2 Una semplice espressione come ciò creerebbe un singolo nodo radice che contiene un nodo destro e uno sinistro che contengono i dati sui numeri.In linguaggio C, “sarebbe simile a

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

La tua domanda era anche come attraversare? Lattraversamento in questo caso si chiama Visita ai nodi . La visita a ogni nodo richiede lutilizzo di ogni tipo di nodo per determinare come valutare i dati di ogni nodo di sintassi.

Ecco un altro esempio di quello in C dove stampo semplicemente il contenuto di ogni nodo:

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

Nota come la funzione visita ricorsivamente ogni nodo in base al tipo di nodo con cui abbiamo a che fare.

Aggiungiamo un esempio più complesso, un costrutto di istruzioni if! Ricorda che le istruzioni if può anche avere una clausola else opzionale. Aggiungiamo listruzione if-else alla nostra struttura del nodo originale. Ricorda che le istruzioni if stesse possono anche avere istruzioni if, quindi può verificarsi una sorta di ricorsione allinterno del nostro sistema di nodi. Le istruzioni Else sono facoltative, quindi il campo elsestmt può essere NULL e la funzione visitatore ricorsiva può ignorare.

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

indietro nella nostra funzione di stampa del visitatore del nodo chiamata AST_PrintNode, possiamo ospitare il costrutto AST dellistruzione if aggiungendo questo codice 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; 

Così semplice! In conclusione, lalbero della sintassi non è molto più che un albero di ununione taggata dellalbero e dei suoi dati stessi!