C Academy · Aula

Analisando expressões

Construa uma árvore sintática.

Analisando expressões é uma aula grátis de C Academy no CoddyKit. Esta é a aula 2 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.

Dos Tokens à Árvore

A análise sintática transforma um fluxo plano de tokens em uma árvore de sintaxe abstrata (AST) estruturada. A árvore codifica a precedência e o agrupamento que os tokens brutos apenas sugerem.

Para 3 + 4 * 2, a AST aninha a multiplicação sob a adição, portanto o resultado é 11, não 14.

Formato de um Node da AST

Cada Node é uma folha numérica ou uma operação binária com dois filhos. Uma estrutura com etiqueta e uma união mantém a memória compacta.

O caractere do operador distingue +, -, * e / durante a execução.

typedef struct Node {
  enum { N_NUM, N_BINOP } kind;
  union {
    int value;                 /* N_NUM */
    struct {                   /* N_BINOP */
      char op;
      struct Node *left, *right;
    } bin;
  };
} Node;

Alocando Nodes

Dois construtores pequenos alocam Nodes no heap. Construir a árvore de baixo para cima significa que as folhas são criadas primeiro e depois envolvidas em Nodes de operadores.

Em um interpretador de produção, você controlaria essas alocações para liberá-las posteriormente.

#include <stdlib.h>

static Node *num(int v) {
  Node *n = malloc(sizeof *n);
  n->kind = N_NUM; n->value = v;
  return n;
}

static Node *binop(char op, Node *l, Node *r) {
  Node *n = malloc(sizeof *n);
  n->kind = N_BINOP;
  n->bin.op = op; n->bin.left = l; n->bin.right = r;
  return n;
}

A gramática

Usamos uma gramática clássica de precedência. expr trata de + e -, term trata de * e /, e factor trata de números e parênteses.

Como as regras de maior precedência ficam mais abaixo, a multiplicação automaticamente se liga com mais força do que a adição.

/* Grammar (EBNF):
   expr   = term   { ('+' | '-') term } ;
   term   = factor { ('*' | '/') factor } ;
   factor = NUMBER | '(' expr ')' ; */

Correspondência de tokens

Um auxiliar expect consome um token do tipo exigido ou aborta. Ele é o contrato do analisador sintático com o analisador léxico.

Reutilizamos os auxiliares de antevisão cur e bump da lição sobre análise léxica.

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

static void expect(TokKind k) {
  if (cur().kind != k) {
    fprintf(stderr, "parse error: unexpected token\n");
    exit(1);
  }
  bump();
}

Analisando um fator

Um fator é o átomo da gramática: ou um número literal, ou uma subexpressão entre parênteses. Os parênteses retornam recursivamente a parse_expr.

É essa recursão que dá nome aos analisadores sintáticos de descida recursiva.

static Node *parse_expr(void);

static Node *parse_factor(void) {
  if (cur().kind == TOK_NUM) {
    int v = cur().value; bump();
    return num(v);
  }
  expect(TOK_LPAREN);
  Node *e = parse_expr();
  expect(TOK_RPAREN);
  return e;
}

Analisando um termo

Um termo analisa um fator e, em seguida, repete enquanto encontra * ou /, incorporando cada operador em um nó binário associativo à esquerda.

Associatividade à esquerda significa que 8 / 4 / 2 é analisado como (8 / 4) / 2 = 1.

static Node *parse_term(void) {
  Node *left = parse_factor();
  while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
    char op = (cur().kind == TOK_STAR) ? '*' : '/';
    bump();
    left = binop(op, left, parse_factor());
  }
  return left;
}

Analisando uma expressão

A regra de nível superior espelha parse_term, mas trata de + e -. Cada camada chama a regra de precedência imediatamente superior, portanto a árvore fica aninhada corretamente.

Essa estrutura de três funções é o coração do analisador sintático.

static Node *parse_expr(void) {
  Node *left = parse_term();
  while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
    char op = (cur().kind == TOK_PLUS) ? '+' : '-';
    bump();
    left = binop(op, left, parse_term());
  }
  return left;
}

Inspecionando a árvore

Este programa analisa uma expressão e a imprime novamente com todos os parênteses, revelando como a precedência foi resolvida.

O formatador percorre recursivamente a mesma estrutura de nós criada pelo analisador sintático.

#include <stdio.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 void show(Node *n){
  if (n->is_num){ printf("%d", n->value); return; }
  printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}

int main(void){
  /* 3 + 4 * 2  ->  (3 + (4 * 2)) */
  Node *ast = B('+', N(3), B('*', N(4), N(2)));
  show(ast); printf("\n");
  return 0;
}

Evitando a recursão à esquerda

Uma gramática ingênua como expr = expr '+' term faria parse_expr chamar a si mesma indefinidamente. A descida recursiva não consegue lidar com recursão direta à esquerda.

Reescrever a regra como um laço while sobre { '+' term } elimina completamente a recursão infinita.

Por que uma AST?

A AST separa a sintaxe da execução. A mesma árvore pode ser avaliada, otimizada ou compilada para código de bytes sem ser analisada novamente.

Agora percorreremos essa árvore para calcular seu valor.

Verificação rápida

Considere como as camadas da gramática impõem a precedência.

Recapitulação

O senhor escreveu um analisador sintático de descida recursiva: estruturas de nós da AST, construtores e as funções expr/term/factor que codificam a precedência e a associatividade à esquerda.

A árvore resultante está pronta para ser avaliada.

Perguntas Frequentes

A aula “Analisando expressões” é grátis?

Sim — o texto completo de “Analisando expressões” é 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 “Analisando expressões”?

Construa uma árvore sintática. 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 2 de 4.

Quanto tempo leva a aula “Analisando expressões”?

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

← Voltar para C Academy