0Pricing
C Academy · Aula

Avaliando a árvore

Calcule o resultado.

Avaliando a árvore é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.

Percorrendo a AST

A avaliação é um percurso em pós-ordem: primeiro calculamos os filhos e depois os combinamos com o operador do nó. Uma folha numérica simplesmente retorna seu valor.

Esse interpretador que percorre a árvore é o back-end mais simples que um interpretador pode ter.

A assinatura de eval

Nosso avaliador recebe um ponteiro para um nó e retorna um número inteiro. Como a árvore é recursiva, a função também é.

Em linguagens de ponto flutuante, o senhor retornaria um double ou um valor com tipo identificado.

int eval(Node *n);  /* returns the integer value of the subtree */

Avaliando uma folha

O caso-base interrompe a recursão. Quando um nó é um número, seu valor é a resposta para essa subárvore.

Toda descida recursiva precisa alcançar um caso-base; caso contrário, nunca terminaria.

int eval(Node *n) {
  if (n->kind == N_NUM) {
    return n->value;
  }
  /* ... handle N_BINOP below ... */
  return 0;
}

Avaliando um BinOp

Para um nó operador, percorremos recursivamente os dois filhos e depois aplicamos o operador. Avaliar a esquerda antes da direita produz a ordem usual da esquerda para a direita.

Um switch sobre o caractere do operador mantém a lógica legível.

int eval(Node *n) {
  if (n->kind == N_NUM) return n->value;
  int l = eval(n->bin.left);
  int r = eval(n->bin.right);
  switch (n->bin.op) {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

Protegendo a divisão por zero

A divisão inteira por zero é um comportamento indefinido em C e normalmente encerra o processo. Um interpretador seguro verifica primeiro o divisor.

Relatar um erro claro em tempo de execução é melhor do que provocar um SIGFPE descontrolado.

#include <stdio.h>
#include <stdlib.h>

static int safe_div(int a, int b) {
  if (b == 0) {
    fprintf(stderr, "runtime error: division by zero\n");
    exit(1);
  }
  return a / b;
}

Avaliação de ponta a ponta

Aqui, uma árvore construída manualmente para (2 + 3) * 4 é avaliada como 20. O mesmo eval executaria qualquer árvore produzida pelo analisador sintático.

Execute o programa para confirmar que o percurso em pós-ordem calcula a resposta correta.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static int eval(Node *n){
  if (n->is_num) return n->value;
  int l = eval(n->l), r = eval(n->r);
  switch (n->op){
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

int main(void){
  Node *ast = B('*', B('+', N(2), N(3)), N(4));
  printf("%d\n", eval(ast));
  return 0;
}

Profundidade da pilha

Cada operador aninhado adiciona um quadro à pilha de chamadas de C. Uma expressão profundamente aninhada, como uma com mil pares de parênteses, pode estourá-la.

A maioria das expressões reais é rasa, mas um interpretador robusto pode usar uma pilha explícita para garantir segurança.

Dobramento de constantes

Como a avaliação e a análise sintática compartilham a árvore, o senhor pode otimizá-la. Se os dois filhos de um nó binário forem números, poderá calcular o resultado uma vez e substituir o nó por uma folha.

Esse dobramento de constantes é uma otimização clássica de interpretadores.

/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
  if (n->kind == N_BINOP) {
    n->bin.left  = fold(n->bin.left);
    n->bin.right = fold(n->bin.right);
    if (n->bin.left->kind == N_NUM &&
        n->bin.right->kind == N_NUM)
      return num(eval(n));
  }
  return n;
}

Liberando a árvore

Os nós alocados no heap precisam ser liberados. Uma liberação em pós-ordem visita os filhos antes do pai, espelhando a avaliação.

Esquecer isso causa um vazamento de memória a cada expressão executada pelo interpretador.

void free_tree(Node *n) {
  if (n->kind == N_BINOP) {
    free_tree(n->bin.left);
    free_tree(n->bin.right);
  }
  free(n);
}

Menos unário

A negação, como em -5, precisa ser tratada. Uma opção é usar um nó unário; outra é transformar -x em 0 - x durante a análise sintática.

De qualquer forma, a avaliação continua sendo um simples percurso recursivo.

/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
  bump();
  return binop('-', num(0), parse_factor());
}

Por que percorrer a árvore?

Interpretadores que percorrem árvores são fáceis de escrever e depurar, embora tenham algum custo de velocidade. Linguagens como as primeiras versões de Ruby usavam esse modelo antes de migrar para máquinas virtuais de código de bytes.

Agora adicionaremos variáveis para que o interpretador possa memorizar valores.

Verificação rápida

Raciocine sobre a ordem em que eval visita os nós.

Recapitulação

O senhor implementou um avaliador recursivo: caso-base para folhas, recursão para BinOp, proteção contra divisão por zero, além da liberação da árvore e do dobramento de constantes.

Agora o interpretador calcula qualquer AST aritmética. A próxima etapa é adicionar variáveis.

Perguntas Frequentes

A aula “Avaliando a árvore” é grátis?

Sim — o texto completo de “Avaliando a árvore” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.

O que vou aprender em “Avaliando a árvore”?

Calcule o resultado. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar C Academy?

Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.

Quanto tempo leva a aula “Avaliando a árvore”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de C Academy?

Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Tokenizando a entrada
  2. Analisando expressões
  3. Avaliando a árvore
  4. Adicionando variáveis
← Voltar para C Academy