Arvores Sintaticas (ASTs)

Modulo 4 · Aula 1 ~25 min de leitura Nivel: Intermediario

Video da aula estara disponivel em breve

Parse Tree vs. AST

A parse tree (árvore de derivação, ou árvore concreta) reflete fielmente todas as produções da gramática, incluindo não-terminais intermediários. A AST (Abstract Syntax Tree, ou árvore abstrata) simplifica, mantendo apenas a informação semanticamente relevante. Segundo Aho, Sethi e Ullman (Dragon Book, Cap. 2.5 e 5.2), a AST é a representação intermediária central usada pelas fases de análise semântica, otimização e geração de código.

Definição formal: uma AST é uma árvore rotulada onde:

Cada nó interno representa um operador ou construção da linguagem (operação binária, atribuição, if-else, chamada de função)
Cada folha representa um operando (literal numérico, string, identificador)
A estrutura da árvore codifica a precedência e associatividade das operações — sem precisar de parênteses ou não-terminais auxiliares

Diagrama

Expressão: 2 + 3 * 4

Parse Tree (concreta):             AST (abstrata):
        expr                            +
       / | \                           / \
    expr '+' term                     2    *
     |       / | \                        / \
   term   term '*' factor               3    4
     |      |        |
  factor  factor   NUMBER(4)
     |      |
  NUMBER(2) NUMBER(3)

A parse tree tem 11 nós. A AST tem 5.
A AST descarta não-terminais intermediários e parênteses —
mantém apenas a estrutura semântica.

Outro exemplo: (2 + 3) * 4

Parse Tree:                         AST:
        expr                            *
       / | \                           / \
    term '*' factor                   +    4
   / | \       |                     / \
  '(' expr ')' NUMBER(4)            2    3
     / | \
  expr '+' term
   |         |
  term      factor
   |         |
  factor   NUMBER(3)
   |
  NUMBER(2)

Parse tree: 15 nós.  AST: 5 nós.
Os parênteses desaparecem na AST — a estrutura da árvore
já codifica que + é avaliado antes de *.

Definindo Nós da AST em Python

Em compiladores modernos, os nós da AST são definidos como tipos de dados algébricos (em linguagens funcionais) ou como hierarquias de classes (em OO). Em Python, dataclass oferece uma sintaxe concisa que se aproxima dos tipos algébricos:

Python

from dataclasses import dataclass
from typing import List, Optional, Union

# Tipo union para expressões e statements
Expr = Union['NumberLit', 'StringLit', 'Identifier',
             'BinOp', 'UnaryOp', 'FuncCall']
Stmt = Union['Assignment', 'IfStmt', 'WhileStmt', 'ReturnStmt']

# --- Nós de expressão ---
@dataclass
class NumberLit:
    value: float
    line: int = 0  # informação de localização para mensagens de erro

@dataclass
class StringLit:
    value: str
    line: int = 0

@dataclass
class Identifier:
    name: str
    line: int = 0

@dataclass
class BinOp:
    op: str
    left: Expr
    right: Expr
    line: int = 0

@dataclass
class UnaryOp:
    op: str        # '-', 'not'
    operand: Expr
    line: int = 0

@dataclass
class FuncCall:
    name: str
    args: List[Expr]
    line: int = 0

# --- Nós de statement ---
@dataclass
class Assignment:
    target: Identifier
    value: Expr
    line: int = 0

@dataclass
class IfStmt:
    condition: Expr
    then_body: List[Stmt]
    else_body: Optional[List[Stmt]]
    line: int = 0

@dataclass
class WhileStmt:
    condition: Expr
    body: List[Stmt]
    line: int = 0

@dataclass
class ReturnStmt:
    value: Optional[Expr]
    line: int = 0

# Construir a AST de: resultado = taxa * 100 + bonus
ast_tree = Assignment(
    target=Identifier("resultado"),
    value=BinOp(
        op="+",
        left=BinOp(
            op="*",
            left=Identifier("taxa"),
            right=NumberLit(100)
        ),
        right=Identifier("bonus")
    )
)
print(ast_tree)

Representação em C

Em compiladores escritos em C (como GCC, que originalmente era C puro), a AST é representada com structs, enums e unions — equivalente ao pattern matching de linguagens funcionais:

/* Nós da AST em C — estilo tagged union */
typedef enum {
    NODE_NUM, NODE_ID, NODE_BINOP,
    NODE_UNARY, NODE_ASSIGN, NODE_IF
} NodeKind;

typedef struct ASTNode {
    NodeKind kind;
    int line;  /* localização no fonte */
    union {
        struct { double value; } num;
        struct { char *name; } id;
        struct {
            char op;
            struct ASTNode *left, *right;
        } binop;
        struct {
            char op;
            struct ASTNode *operand;
        } unary;
        struct {
            char *target;
            struct ASTNode *value;
        } assign;
    } data;
} ASTNode;

/* Construtores */
ASTNode* make_num(double val, int line) {
    ASTNode *n = calloc(1, sizeof(ASTNode));
    n->kind = NODE_NUM;
    n->line = line;
    n->data.num.value = val;
    return n;
}

ASTNode* make_binop(char op, ASTNode *l, ASTNode *r, int line) {
    ASTNode *n = calloc(1, sizeof(ASTNode));
    n->kind = NODE_BINOP;
    n->line = line;
    n->data.binop.op = op;
    n->data.binop.left = l;
    n->data.binop.right = r;
    return n;
}

/* Percorrer e avaliar */
double eval_node(ASTNode *n) {
    switch (n->kind) {
        case NODE_NUM:
            return n->data.num.value;
        case NODE_BINOP: {
            double l = eval_node(n->data.binop.left);
            double r = eval_node(n->data.binop.right);
            switch (n->data.binop.op) {
                case '+': return l + r;
                case '-': return l - r;
                case '*': return l * r;
                case '/': return l / r;
            }
        }
        default: return 0;
    }
}

Visitor Pattern

O Visitor pattern (GoF Design Patterns) permite percorrer a AST e executar operações diferentes em cada tipo de nó sem modificar as classes dos nós. Cada fase do compilador que precisa percorrer a AST (type checker, otimizador, gerador de código) é implementada como um Visitor separado:

Python

class ASTVisitor:
    """Visitor base — despacha para visit_TipoDoNó."""
    def visit(self, node):
        method = f'visit_{type(node).__name__}'
        visitor = getattr(self, method, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        raise NotImplementedError(f"Sem visitor para {type(node).__name__}")

class Evaluator(ASTVisitor):
    """Visitor 1: avalia expressões numéricas."""
    def __init__(self):
        self.env = {}

    def visit_NumberLit(self, node):
        return node.value

    def visit_Identifier(self, node):
        return self.env.get(node.name, 0)

    def visit_BinOp(self, node):
        left = self.visit(node.left)
        right = self.visit(node.right)
        ops = {'+': lambda a,b: a+b, '-': lambda a,b: a-b,
               '*': lambda a,b: a*b, '/': lambda a,b: a/b}
        return ops[node.op](left, right)

    def visit_Assignment(self, node):
        value = self.visit(node.value)
        self.env[node.target.name] = value
        return value

# Uso
evaluator = Evaluator()
evaluator.env = {'taxa': 0.15, 'bonus': 50}
result = evaluator.visit(ast_tree)
print(f"resultado = {result}")  # resultado = 65.0

class PrettyPrinter(ASTVisitor):
    """Visitor 2: imprime a AST como código."""
    def visit_NumberLit(self, node): return str(node.value)
    def visit_Identifier(self, node): return node.name
    def visit_BinOp(self, node):
        return f"({self.visit(node.left)} {node.op} {self.visit(node.right)})"
    def visit_Assignment(self, node):
        return f"{node.target.name} = {self.visit(node.value)}"

class DotGenerator(ASTVisitor):
    """Visitor 3: gera representação Graphviz DOT da AST."""
    def __init__(self):
        self.counter = 0
        self.lines = ["digraph AST {"]

    def _id(self):
        self.counter += 1
        return f"n{self.counter}"

    def visit_NumberLit(self, node):
        nid = self._id()
        self.lines.append(f'  {nid} [label="{node.value}"];')
        return nid

    def visit_BinOp(self, node):
        nid = self._id()
        self.lines.append(f'  {nid} [label="{node.op}"];')
        lid = self.visit(node.left)
        rid = self.visit(node.right)
        self.lines.append(f"  {nid} -> {lid};")
        self.lines.append(f"  {nid} -> {rid};")
        return nid

    def to_dot(self):
        self.lines.append("}")
        return "\n".join(self.lines)

printer = PrettyPrinter()
print(printer.visit(ast_tree))  # resultado = ((taxa * 100) + bonus)

Python ast Module Deep Dive

Python

import ast

# Python expõe sua própria AST via o módulo ast
code = 'resultado = taxa * 100 + bonus'
tree = ast.parse(code)

# Visualizar a AST
print(ast.dump(tree, indent=2))

# NodeVisitor do Python — mesmo padrão Visitor
class NameCollector(ast.NodeVisitor):
    def __init__(self):
        self.names = set()
    def visit_Name(self, node):
        self.names.add(node.id)
        self.generic_visit(node)

collector = NameCollector()
collector.visit(tree)
print(f"Variáveis usadas: {collector.names}")
# Variáveis usadas: {'resultado', 'taxa', 'bonus'}

# NodeTransformer — modifica a AST (Visitor que retorna nós novos)
class ConstantFolder(ast.NodeTransformer):
    """Otimização: calcula expressões constantes em compile-time."""
    def visit_BinOp(self, node):
        self.generic_visit(node)  # visita filhos primeiro (bottom-up)
        if isinstance(node.left, ast.Constant) and isinstance(node.right, ast.Constant):
            try:
                result = eval(compile(ast.Expression(node), '<ast>', 'eval'))
                return ast.Constant(value=result)
            except:
                pass
        return node

# NodeTransformer vs NodeVisitor:
# NodeVisitor percorre sem modificar (análise, coleta)
# NodeTransformer pode substituir nós (otimização, transformação)

No harness.os

O conceito de AST vai muito além de compiladores. Qualquer representação hierárquica de dados pode ser modelada como uma árvore e percorrida com o Visitor pattern. O knowledge graph do harness.os é um exemplo direto: projects contêm domains, que contêm concerns, que contêm knowledge chunks — uma árvore cuja "gramática" é Project → Domain* → Concern* → Knowledge*.

Cada operação que o harness.os precisa executar sobre essa árvore (contar tokens, filtrar por domínio, calcular estatísticas, gerar relatórios) é implementada como um Visitor separado — exatamente como no compilador. A separação entre a estrutura de dados (nós da AST) e as operações (Visitors) permite adicionar novas análises sem modificar a representação existente.

Python

@dataclass
class HarnessNode:
    pass

@dataclass
class Project(HarnessNode):
    slug: str
    domains: List['Domain']

@dataclass
class Domain(HarnessNode):
    name: str
    concerns: List['Concern']

@dataclass
class Concern(HarnessNode):
    name: str
    knowledge: List['Knowledge']

@dataclass
class Knowledge(HarnessNode):
    title: str
    content: str
    tokens: int  # custo em tokens

class TokenCounter(ASTVisitor):
    """Conta tokens totais por concern — para token economy."""
    def visit_Project(self, node):
        return sum(self.visit(d) for d in node.domains)
    def visit_Domain(self, node):
        return sum(self.visit(c) for c in node.concerns)
    def visit_Concern(self, node):
        return sum(self.visit(k) for k in node.knowledge)
    def visit_Knowledge(self, node):
        return node.tokens

Homework

AST completa: Estenda a definição de nós da AST para suportar: WhileStmt, ForStmt, FuncDef (com parâmetros tipados e corpo), e ArrayAccess (ex: a[i+1]). Construa manualmente a AST para um programa com pelo menos 5 statements usando esses nós.
Três Visitors: Implemente três Visitors sobre a AST: (a) Evaluator que avalia expressões com variáveis, (b) PrettyPrinter que regenera código formatado a partir da AST, (c) DotGenerator que gera a representação Graphviz DOT para visualização. Teste com a expressão (2 + 3) * 4 - 1.
AST em C: Implemente a representação de AST em C usando tagged unions (como mostrado nesta aula). Implemente os construtores make_num, make_id, make_binop, make_assign, e a função eval_node que avalia a árvore. Compile e teste com pelo menos 3 expressões diferentes.
Módulo ast do Python: Use o módulo ast do Python para: (a) parsear um programa Python com pelo menos 10 linhas, (b) implementar um NodeVisitor que coleta todas as chamadas de função e seus argumentos, (c) implementar um NodeTransformer que substitui todas as constantes numéricas por seus valores dobrados. Verifique que o código transformado executa corretamente.

Resumo

Parse tree é concreta (reflete a gramática); AST é abstrata (reflete a semântica)
A AST descarta não-terminais auxiliares e parênteses — a estrutura da árvore codifica precedência
Nós da AST são modelados com dataclasses em Python ou tagged unions em C
Todo nó deve incluir informação de localização (linha) para mensagens de erro
Visitor pattern permite operações na árvore sem modificar os nós (Evaluator, PrettyPrinter, DotGenerator)
Python ast.NodeVisitor (análise) e ast.NodeTransformer (transformação) são Visitors built-in
O knowledge graph do harness.os é uma árvore percorrida com Visitors

Verifique seu entendimento

Qual é a principal diferença entre uma parse tree e uma AST?

Parse tree é gerada por parsers top-down; AST por parsers bottom-up
A AST omite não-terminais intermediários e mantém apenas a estrutura semântica
ASTs só existem em linguagens tipadas estaticamente
Parse trees são mais eficientes em memória

Verifique seu entendimento

Qual a vantagem do Visitor pattern sobre colocar a lógica diretamente nos nós da AST?

Executa mais rápido porque evita chamadas virtuais
Ocupa menos memória por nó
Permite adicionar novas operações sem modificar as classes dos nós
Garante que a árvore é percorrida em ordem correta

Aula anterior3.3 Parsing Bottom-Up Proxima aula4.2 Tabela de Simbolos