Acho que entendo o objetivo de um AST e já construí algumas estruturas de árvore antes, mas nunca um AST. Estou bastante confuso porque os nós são texto e não número, então não consigo pensar em uma maneira legal de inserir um token / string enquanto estou analisando algum código.
Por exemplo, quando olhei para os diagramas de AST “s, a variável e seu valor eram nós folha com um sinal de igual. Isso faz todo o sentido para mim, mas como eu faria para implementar isso? Eu acho que posso fazer isso caso a caso, de modo que quando eu topar com um “=”, eu o uso como um nó e adiciono o valor analisado antes do “=” como a folha. Parece errado, porque provavelmente eu “d tem que criar casos para toneladas e toneladas de coisas, dependendo da sintaxe.
E então me deparei com outro problema, como a árvore é atravessada? Devo descer toda a altura e voltar a subir um nó quando chego ao fundo, e faço o mesmo para o vizinho?
Eu vi toneladas de diagramas em ASTs, mas Não consegui encontrar um exemplo bastante simples de um no código, o que provavelmente ajudaria.
Comentários
- O conceito-chave que você ‘ o que falta é recursão . A recursão é um tanto contra-intuitiva e ‘ é diferente para cada aluno quando finalmente ‘ clique ‘ com eles, mas sem recursão, simplesmente não há maneira de entender a análise (e muitos outros tópicos computacionais também ).
- Recebo recursão, apenas pensei que ‘ seria difícil implementá-lo neste caso. Na verdade, eu queria usar recursão e acabei com muitos casos que não ‘ não funcionariam para uma solução geral. A resposta de Gdhoward ‘ está me ajudando muito agora.
- Pode ser um exercício construir uma calculadora RPN como um exercício. Não vai responder à sua pergunta, mas pode ensinar algumas habilidades necessárias.
- Na verdade, eu já construí uma calculadora RPN antes. As respostas me ajudaram muito e acho que posso fazer um AST básico agora. Obrigado!
Resposta
A resposta curta é que você usa pilhas. Este é um bom exemplo, mas vou aplicá-lo a um AST.
Para sua informação, este é Edsger Dijkstra “s Algoritmo de Shunting-Yard .
Neste caso, usarei uma pilha de operadores e uma pilha de expressões. Como os números são considerados expressões na maioria das linguagens, usarei a pilha de expressões para armazená-los.
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()
(Por favor, seja gentil com meu código. Eu sei que ele “não é robusto; é apenas um pseudocódigo.)
De qualquer forma, como você pode ver pelo código, é arbitrário expressões podem ser operandos para outras expressões. Se você tiver a seguinte entrada:
5 * 3 + (4 + 2 % 2 * 8) o código que escrevi produziria este AST:
+ / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 E então, quando você deseja produzir o código para esse AST, você faz um Post Order Tree Traversal . Quando você visita um nó folha (com um número), você gera uma constante porque o compilador precisa saber os valores do operando. Quando você visita um nó com um operador, você gera a instrução apropriada do operador. Por exemplo, o “+” operador dá a você uma instrução “adicionar”.
Comentários
- Isso funciona para r operadores que possuem associatividade da esquerda para a direita, não da direita para a esquerda.
- @Simon, seria extremamente simples adicionar a capacidade de operadores da direita para a esquerda. O mais simples seria adicionar uma tabela de pesquisa e, se um operador da direita para a esquerda, simplesmente inverter a ordem dos operandos.
- @Simon Se quiser oferecer suporte a ambos, você ‘ é melhor procurar o algoritmo do pátio de manobras em toda a sua glória. No que diz respeito aos algoritmos, esse ‘ é um cracker absoluto.
Resposta
Há uma diferença significativa entre como um AST é normalmente representado no teste (uma árvore com números / variáveis nos nós folha e símbolos nos nós internos) e como ele é realmente implementado.
O típico a implementação de um AST (em uma linguagem OO) faz uso intenso de polimorfismo. Os nós na AST são tipicamente implementados com uma variedade de classes, todas derivando de uma classe ASTNode comum. Para cada construção sintática na linguagem que você está processando, haverá uma classe para representar essa construção no AST, como ConstantNode (para constantes, como 0x10 ou 42), VariableNode (para nomes de variáveis), AssignmentNode (para operações de atribuição), ExpressionNode (para expressões genéricas), etc.
Cada tipo de nó específico especifica se aquele nó tem filhos, quantos e possivelmente de que tipo. Um ConstantNode normalmente não terá filhos, um AssignmentNode terá dois e um ExpressionBlockNode pode tem qualquer número de filhos.
O AST é construído pelo analisador, quem sabe qual construção ele acabou de analisar, para que possa construir o tipo certo de Nó AST.
Ao atravessar o AST, o polimorfismo dos nós realmente entra em jogo. A base ASTNode define as operações que podem ser realizadas nos nós, e cada tipo de nó específico implementa essas operações da maneira específica para aquela construção de linguagem particular.
Resposta
Construir o AST a partir do texto de origem é ” simplesmente ” análise . Como exatamente isso é feito depende da linguagem formal analisada e da implementação. Você pode usar geradores de analisador como menhir (para Ocaml) , GNU bison com flex ou ANTLR etc. etc. Geralmente é feito ” manualmente ” codificando alguns analisador descendente recursivo (consulte esta resposta explicando o porquê). O aspecto contextual da análise é geralmente feito em outro lugar (tabelas de símbolos, atributos, ….).
No entanto, na prática, os AST são muito mais complexos do que você acredita. Por exemplo, em um compilador como o GCC , o AST mantém as informações de localização da fonte e algumas informações de digitação. Leia sobre Árvores genéricas e GIMPLE no GCC e olhe dentro de seu gcc / tree.def . Considere, se você deseja processar C ou C ++ ou Fortran ou Ada, escrever seu próprio plugin GCC . BTW, olhe também dentro do obsoleto GCC MELT (que eu projetei & implementado), é relevante para o seu pergunta. Leia o livro do Dragão . Consulte também este relatório de rascunho para referências e o projeto RefPerSys e o código-fonte de muitos outros projetos de código aberto (incluindo Ocaml ou Guile ou SBCL ou Jq ) em github ou gitlab como exemplos.
Comentários
- Eu ‘ estou fazendo um interpretador Lua para analisar o texto-fonte e transformar em um array em JS. Posso considerá-lo um AST? Eu ‘ devo fazer algo assim:
--My comment #1 print("Hello, ".."world.")transforma para `[{” tipo “: ” – “, ” conteúdo “: ” Meu comentário nº 1 “}, {” type “: ” chame “, ” nome “: ” print “, ” argumentos “: [[{” type “: ” str “, ” ação “: ” .. “, ” conteúdo “: ” Olá, “}, {” digite “: ” str “, ” conteúdo “: ” mundo. “}]]}] `Acho que ‘ é muito mais simples em JS do que qualquer outro idioma! - @TheProHands Isso seria considerado tokens, não um AST.
Resposta
Sei que esta pergunta tem mais de 4 anos, mas acho que devo adicionar uma resposta mais detalhada.
Árvores de sintaxe abstrata não são criadas de maneira diferente de outras árvores; a afirmação mais verdadeira neste caso é que os nós da Árvore Sintaxe têm uma quantidade variável de nós COMO NECESSÁRIO.
Um exemplo são expressões binárias como 1 + 2 Uma expressão simples como isso criaria um único nó raiz contendo um nó direito e um nó esquerdo que contém os dados sobre os números.Na linguagem C, seria algo como
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; }; Sua pergunta também era como fazer a travessia? A travessia, neste caso, é chamada de Visitando nós . Visitar cada nó requer que você use cada tipo de nó para determinar como avaliar os dados de cada nó da sintaxe.
Aqui está outro exemplo disso em C onde eu simplesmente imprimo o conteúdo de cada 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; } } Observe como a função visita recursivamente cada nó de acordo com o tipo de nó com o qual estamos lidando.
Vamos adicionar um exemplo mais complexo, uma construção de instrução if! Lembre-se de que as instruções if também pode ter uma cláusula else opcional. Vamos adicionar a instrução if-else à nossa estrutura de nó original. Lembre-se de que as próprias instruções if também podem ter instruções if, portanto, pode ocorrer um tipo de recursão em nosso sistema de nós. Outras declarações são opcionais, portanto o campo elsestmt pode ser NULL, o que a função de visitante recursiva pode ignorar.
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; }; voltar em nossa função de impressão do visitante do nó chamada AST_PrintNode, podemos acomodar a construção AST da instrução if adicionando este código 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; Tão simples quanto isso! Em conclusão, a Árvore Sintaxe não é muito mais do que uma árvore de uma união marcada da árvore e seus próprios dados!