A Árvore Sintática Abstrata (AST)

Estrutura, não sequência

Uma lista de tokens é só uma sequência linear — não captura que * tem prioridade sobre +, nem que parênteses agrupam subexpressões. O parser resolve isso: consome a lista de tokens e constrói uma Árvore Sintática Abstrata (AST).

Na AST, cada nodo representa uma construção da linguagem. Uma expressão 1 + 2 * 3 vira uma árvore onde * é filho de + — o que garante que a multiplicação acontece antes. A ordem de operações emerge naturalmente da estrutura da gramática.

Explore a AST de expressões

Edite a expressão ou escolha um exemplo. Veja a AST construída em tempo real como árvore visual. Cada tipo de nodo tem uma cor.

Parser descendente recursivo

// Recursive descent parser — um método por nível de precedência

class Parser {
  constructor(tokens) { this.tokens = tokens; this.pos = 0; }
  peek()  { return this.tokens[this.pos]; }
  next()  { return this.tokens[this.pos++]; }

  // Cada método lida com um nível de precedência
  parseExpr()   { return this.parseAddSub(); }

  parseAddSub() {
    let left = this.parseMulDiv();
    while (["+", "-"].includes(this.peek()?.value)) {
      const op = this.next().value;
      left = { type: "BinOp", op, left, right: this.parseMulDiv() };
    }
    return left;
  }

  parseMulDiv() {
    let left = this.parsePrimary();
    while (["*", "/"].includes(this.peek()?.value)) {
      const op = this.next().value;
      left = { type: "BinOp", op, left, right: this.parsePrimary() };
    }
    return left;
  }

  parsePrimary() {
    const t = this.next();
    if (t.type === "NUMBER") return { type: "Num", value: t.value };
    if (t.type === "IDENT")  return { type: "Id",  value: t.value };
    if (t.value === "(")  {
      const expr = this.parseExpr();
      this.next(); // consume ")"
      return expr;
    }
  }
}

Gramática BNF

// Gramática BNF para expressões aritméticas
// (define a estrutura que o parser reconhece)

expr       ::= comparison
comparison ::= addition (('<' | '>' | '==' | '!=') addition)?
addition   ::= term (('+' | '-') term)*
term       ::= unary (('*' | '/') unary)*
unary      ::= '-' unary | primary
primary    ::= NUMBER | IDENTIFIER | '(' expr ')'

// "1 + 2 * 3" → parser gera:
//   BinOp(+, Num(1), BinOp(*, Num(2), Num(3)))
// Ordem de operações emerge naturalmente da gramática!

Construa um parser de expressões

Mini projeto: implemente um parser recursivo descendente para expressões aritméticas com os 4 operadores, parênteses e variáveis. Retorne a AST como objeto JS. Teste: (2 + 3) * 4, a - b / c.

Projeto principal: estenda o parser para suportar statements: let x = expr, if (cond) block else block, while (cond) block, e print expr. Gere a AST completa de um programa de 10 linhas.

Desafio extra: implemente um pretty printer: dada uma AST, regenere o código fonte formatado (com indentação correta para blocos if/while). Isso é como ferramentas como Prettier funcionam — transformam AST em código formatado.

Teste sua intuição

Onde você encontra isso