Etapa 1: Infraestrutura e AST

Published

17/03/2026

Modified

17/03/2026

Objetivos

  • Compreender o padrão de projeto Composite para representar hierarquias.
  • Definir a representação interna do código fonte: a Árvore Sintática Abstrata (AST).
  • Implementar a Tabela de Símbolos inicial.

Fundamentação Teórica

A AST (Abstract Syntax Tree) é a estrutura de dados central de um compilador. Ela descarta detalhes sintáticos irrelevantes (como parênteses e vírgulas) e mantém a estrutura lógica do programa.

Cada nó da árvore representa uma construção da linguagem (uma soma, um if, uma declaração). Em Java, isso tipicamente é implementado com uma classe base abstrata e várias subclasses.

Atividades Práticas

1. Hierarquia de Classes da AST

Crie um pacote br.com.comcet.tp1.ast. Abaixo está um esqueleto mínimo sugerido; você pode (e deve) refiná‑lo conforme for entendendo melhor a linguagem:

  • AstNode (abstrata): Classe base. Pode ter campos como line e column para rastreamento de erro.
    • Expression (abstrata): Representa algo que avalia para um valor.
      • BinaryExpression: Guarda pelo menos Expression left, Expression right, String operator.
      • Outras expressões que você julgar necessárias (por exemplo UnaryExpression, Literal, Identifier).
    • Command (abstrata): Representa uma ação.
      • Pelo menos um comando simples, como AssignmentCommand (Identifier id, Expression expr).
      • Outros comandos poderão ser adicionados depois (ex.: IfCommand, WhileCommand, PrintCommand, BlockCommand).
    • Program: O nó raiz, contendo declarações e o corpo principal.

Guia de raciocínio: sempre que na linguagem você tiver “coisas que se comportam do mesmo jeito” (todas são expressões, ou todos são comandos), faz sentido ter uma classe abstrata em comum (Expression, Command) e especializações concretas para cada caso específico. Pense primeiro em exemplos de código (em Mini‑Pascal ou Java) e tente desenhar a árvore para eles; a hierarquia de classes deve refletir essa árvore.

Exemplo rápido de programa e nós correspondentes

Considere o programa Mini‑Pascal abaixo:

var x : integer;
x := 10 + 5;

Uma possível visão em termos de nós da AST (usando as classes sugeridas) é:

  • Um nó Program na raiz.
    • Dentro dele, algum tipo de nó que represente a declaração de x (você pode modelar esse nó como achar melhor nesta etapa).
    • Um nó AssignmentCommand, representando x := 10 + 5;, com:
      • Identifier("x") como alvo da atribuição.
      • Uma BinaryExpression para 10 + 5, com:
        • Literal(10) como left.
        • Literal(5) como right.
        • "+" como operator.

Outras formas de modelar são possíveis, desde que a estrutura da árvore reflita claramente quem é o comando, quem são as expressões e quais são os literais/identificadores.

2. Tabela de Símbolos (Symbol Table)

A tabela de símbolos armazena informações sobre os identificadores (variáveis). Crie a classe SymbolTable: - Deve possuir um Map<String, Symbol>. - Métodos necessários: - add(String name, Symbol symbol): Tenta adicionar, erro se já existir. - get(String name): Busca um símbolo, retorna nulo se não existir.

O objeto Symbol deve guardar, por enquanto: - Nome. - Tipo (Integer, Boolean, String) - pode ser null nesta etapa. - Valor (opcional, para interpretadores).

3. Interface do Scanner (Preparação)

Defina uma interface simples para abstrair a leitura de tokens, que será implementada na Etapa 2.

public interface IScanner {
    Token nextToken();
}

E a classe Token:

public record Token(TokenType type, String text) {}

Se você não está acostumado com record em Java: é uma forma concisa de declarar uma classe imutável com campos, construtor, equals, hashCode e toString gerados automaticamente. O código acima é equivalente (de maneira simplificada) a algo como:

public final class Token {
    private final TokenType type;
    private final String text;

    public Token(TokenType type, String text) {
        this.type = type;
        this.text = text;
    }

    public TokenType type() { return type; }
    public String text() { return text; }

    // equals, hashCode e toString gerados pelo compilador
}

Você pode usar record ou uma classe “tradicional”; o importante é que Token tenha esses dois campos acessíveis.

4. Impressão da AST como árvore indentada

Nesta etapa, ainda não temos parser nem execução. Para entender e depurar a AST, queremos uma forma legível de visualizar a árvore resultante.

Em vez de usar toString() em uma linha (que vira um “macarrão” difícil de ler), vamos adotar um método que imprima a árvore com indentação por nível.

Requisitos

  • Cada nó da AST deve ser capaz de imprimir a si mesmo e seus filhos em formato de árvore.
  • A saída deve ser determinística (mesma AST → mesma impressão).
  • A indentação deve refletir a estrutura (filhos “mais para a direita”).

Um formato possível para x := 10 + 5;:

AssignmentCommand
  Identifier("x")
  BinaryExpression +
    Literal(10)
    Literal(5)

Sugestão de implementação

Na classe base AstNode, defina:

public abstract class AstNode {
    public final String printTree() {
        StringBuilder sb = new StringBuilder();
        printTree(sb, 0);
        return sb.toString();
    }

    protected abstract void printTree(StringBuilder sb, int level);

    protected String indent(int level) {
        return "  ".repeat(level); // 2 espaços por nível
    }
}

E, em cada nó concreto, implemente printTree chamando recursivamente os filhos. Por exemplo:

public final class Literal extends Expression {
    private final int value;

    @Override
    protected void printTree(StringBuilder sb, int level) {
        sb.append(indent(level))
          .append("Literal(").append(value).append(")\n");
    }
}

public final class AssignmentCommand extends Command {
    private final Identifier id;
    private final Expression expr;

    @Override
    protected void printTree(StringBuilder sb, int level) {
        sb.append(indent(level)).append("AssignmentCommand\n");
        id.printTree(sb, level + 1);
        expr.printTree(sb, level + 1);
    }
}

Você pode ainda sobrescrever toString() em AstNode para delegar para printTree() (por exemplo, retornando a árvore em uma única string).

O que entregar

  1. Código Fonte: Classes da AST e Tabela de Símbolos implementadas.
  2. Impressão da AST: Implementação de printTree() (ou classe equivalente, como AstPrinter) que mostre a árvore com indentação.
  3. Teste Automatizado (JUnit): Uma classe de teste que:
    • constrói manualmente uma pequena árvore (ex: x := 10 + 5) e verifica sua estrutura (tipos de nós, valores básicos);
    • testa operações básicas da SymbolTable (add/get e erro para duplicados).
  4. Teste Manual (Opcional, mas recomendado): Uma classe MainAST que instancia manualmente uma pequena árvore (ex: x := 10 + 5) e imprime sua estrutura (printTree()) para inspeção visual.

Exemplo de teste manual

// Representando: x := 10 + 5;
Expression dez = new Literal("10");
Expression cinco = new Literal("5");
Expression soma = new BinaryExpression(dez, cinco, "+");
Command atrib = new AssignmentCommand(new Identifier("x"), soma);
System.out.println(atrib.printTree());

Exemplo de teste automatizado (JUnit)

Crie um teste em src/test/java/br/com/comcet/tp1/AstAndSymbolTableTest.java (ajuste o pacote conforme o seu projeto):

package br.com.comcet.tp1;

import br.com.comcet.tp1.ast.*;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class AstAndSymbolTableTest {

    @Test
    void criaAstAtribuicaoSoma() {
        // Representando: x := 10 + 5;
        Expression dez = new Literal(10);
        Expression cinco = new Literal(5);
        Expression soma = new BinaryExpression(dez, cinco, "+");
        Command atrib = new AssignmentCommand(new Identifier("x"), soma);

        assertTrue(atrib instanceof AssignmentCommand);
        AssignmentCommand a = (AssignmentCommand) atrib;
        assertEquals("x", a.id().name()); // ou getName(), conforme sua implementação

        assertTrue(a.expr() instanceof BinaryExpression);
        BinaryExpression b = (BinaryExpression) a.expr();
        assertEquals("+", b.operator());
        assertTrue(b.left() instanceof Literal);
        assertTrue(b.right() instanceof Literal);
    }

    @Test
    void symbolTableAddGet() {
        SymbolTable st = new SymbolTable();

        Symbol sx = new Symbol("x", null, null);
        st.add("x", sx);

        assertSame(sx, st.get("x"));
        assertNull(st.get("y"));
    }

    @Test
    void symbolTableNaoPermiteDuplicado() {
        SymbolTable st = new SymbolTable();
        st.add("x", new Symbol("x", null, null));

        assertThrows(IllegalArgumentException.class, () -> {
            st.add("x", new Symbol("x", null, null));
        });
    }
}

Execute:

mvn test

Observações sobre testes e ligação com a Etapa 2

  • Não haverá testes ocultos nesta etapa.
    Todos os casos de teste usados na correção serão visíveis e baseados em ideias semelhantes aos exemplos de JUnit apresentados acima.
  • O foco aqui é que você pense o desenho da AST e da Tabela de Símbolos, não “adivinhar” contratos secretos.
  • Algumas classes/nomeclaturas, porém, são especialmente importantes porque serão reutilizadas na Etapa 2:
    • Token, TokenType e IScanner (interface do scanner).
    • A ideia de uma AST com nós como Literal, Identifier, BinaryExpression, AssignmentCommand (mesmo que você acrescente outros).
  • Procure manter esses nomes e assinaturas estáveis, pois a especificação da Etapa 2 (trabalho/etapa2-lexico.qmd) assume a existência deles para construir o analisador léxico e, depois, o parser.
Back to top