Aula 14: Projeto de Linguagens e AST

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

  • Entender o padrão Visitor.
  • Estruturar a AST para suportar múltiplas passadas.

Motivação em projeto de linguagens

Decisões de projeto de linguagem (sintaxe, conjuntos de tipos, estruturas de controle) não são apenas estéticas: elas determinam diretamente:

  • A forma e a complexidade da AST.
  • O esforço necessário para implementar análise semântica e geração de código.
  • A capacidade de aplicar otimizações posteriormente.

Linguagens modernas (como Rust, Kotlin, Swift) são desenhadas pensando explicitamente em como serão compiladas, e não apenas em como serão usadas pelo programador.

Conteúdo

A Árvore Sintática Abstrata (AST) é a peça central do compilador: o parser a constrói e sai de cena; semântica, otimização e geração de código trabalham sobre a AST.

flowchart TB
  Parser[Parser] --> AST[AST]
  AST --> V1[TypeCheckVisitor]
  AST --> V2[CodeGenVisitor]
  AST --> V3[PrettyPrintVisitor]
  V1 --> AST
  V2 --> AST
  V3 --> AST

Por que AST e não Parse Tree?

  • Parse Tree (Árvore Concreta): Contém cada detalhe da gramática (“Termo”, “Fator”, parênteses, ponto-e-vírgula). É ruidosa e difícil de navegar.
  • AST: Contém apenas a essência lógica. Um nó Soma tem apenas dois filhos (Esq, Dir). Parênteses viram a estrutura da árvore em si.

O Padrão Visitor

O maior desafio da AST é a extensibilidade. Queremos adiconar novas operações (Checar Tipos, Gerar Código, Printar) sem ter que modificar as dezenas de classes da AST (IfNode, WhileNode, AddNode, etc).

O Design Pattern Visitor resolve isso: 1. As classes da AST têm apenas um método: accept(Visitor v). 2. A lógica fica em classes externas que implementam a interface Visitor. - TypeCheckVisitor - CodeGenerationVisitor - PrettyPrintVisitor

Isso permite modularizar o compilador perfeitamente.

Conexões com o projeto Mini-Pascal

  • A Etapa 1 do projeto foca na definição das classes da AST e na organização do Visitor:
    • É o momento de escolher bons nomes, separar responsabilidades e garantir que a árvore representa bem a gramática de Mini-Pascal.
    • Decisões ruins aqui cobram um preço alto nas etapas posteriores (type checking e geração de código).
  • Um design de AST bem pensado facilita:
    • Implementar múltiplos visitantes (checagem de tipos, geração de bytecode, pretty-print).
    • Escrever testes unitários focados em subárvores específicas.

Perguntas de reflexão

  • Em que pontos faz sentido "simplificar" a AST (por exemplo, fundindo nós da Parse Tree) para facilitar as fases posteriores?
  • Quais trade-offs existem entre uma AST muito próxima da gramática versus uma AST mais abstrata e orientada à semântica?

Resumo

  • AST captura a estrutura lógica do programa; Visitor permite várias passadas (tipos, código, pretty-print) sem alterar as classes da AST.
  • Cada nó da AST implementa accept(Visitor); cada visitante implementa um método por tipo de nó. Isso mantém o compilador modular e extensível.

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 5 e 6.
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

Última atualização: 08/03/2026

De volta ao topo