Interpretador Brainfuck em Zig — Tutorial Passo a Passo

7 min de leitura
zig interpretador brainfuck parsing intermediário tutorial

Interpretador Brainfuck em Zig — Tutorial Passo a Passo

Neste tutorial, vamos construir um interpretador completo da linguagem Brainfuck em Zig. Brainfuck é uma linguagem esotérica com apenas 8 comandos, mas é Turing-completa. Implementá-la é um excelente exercício para entender interpretadores, manipulação de memória e parsing de loops.

O Que Vamos Construir

Nosso interpretador vai:

  • Executar programas Brainfuck completos
  • Suportar loops aninhados ([ e ])
  • Validar programas antes da execução (brackets balanceados)
  • Ler programas de arquivos ou da linha de comando
  • Incluir modo de depuração que mostra o estado da memória

Por Que Este Projeto?

Brainfuck é a menor linguagem Turing-completa prática. Implementar seu interpretador nos ensina conceitos fundamentais de linguagens de programação: fetch-decode-execute, program counter, ponteiro de dados e jump tables. Em Zig, podemos fazer isso com controle total sobre a memória.

Pré-requisitos

Referência Rápida: Comandos Brainfuck

ComandoAção
>Move o ponteiro para a direita
<Move o ponteiro para a esquerda
+Incrementa a célula atual
-Decrementa a célula atual
.Imprime a célula atual como ASCII
,Lê um byte da entrada
[Se célula = 0, pula para depois do ] correspondente
]Se célula != 0, volta para o [ correspondente

Passo 1: Estrutura do Projeto

mkdir brainfuck-interpreter
cd brainfuck-interpreter
zig init

Passo 2: Validação e Pré-processamento

Antes de executar, precisamos validar o programa e construir uma tabela de saltos para os loops. Isso é mais eficiente do que procurar o bracket correspondente durante a execução.

const std = @import("std");
const io = std.io;
const mem = std.mem;
const fs = std.fs;

const TAMANHO_MEMORIA = 30000;

const ErrosBrainfuck = error{
    BracketDesbalanceado,
    PonteiroForaDosLimites,
    ProgramaVazio,
};

/// Pré-computa a tabela de saltos para os brackets [ e ].
/// Para cada '[' no índice i, tabela[i] contém o índice do ']' correspondente,
/// e vice-versa. Isso permite pular loops em O(1).
fn construirTabelaDeSaltos(
    programa: []const u8,
    allocator: mem.Allocator,
) ![]usize {
    const tabela = try allocator.alloc(usize, programa.len);
    errdefer allocator.free(tabela);

    var pilha = std.ArrayList(usize).init(allocator);
    defer pilha.deinit();

    for (programa, 0..) |c, i| {
        switch (c) {
            '[' => {
                try pilha.append(i);
            },
            ']' => {
                if (pilha.items.len == 0) {
                    return ErrosBrainfuck.BracketDesbalanceado;
                }
                const abertura = pilha.pop();
                tabela[abertura] = i;
                tabela[i] = abertura;
            },
            else => {},
        }
    }

    if (pilha.items.len != 0) {
        return ErrosBrainfuck.BracketDesbalanceado;
    }

    return tabela;
}

Decisão de design: Usamos uma tabela de saltos pré-computada em vez de buscar brackets durante execução. Isso transforma o custo de loop de O(n) para O(1) e é como interpretadores reais funcionam.

Passo 3: O Interpretador

/// Estado do interpretador Brainfuck.
/// Contém a memória (fita), o ponteiro de dados,
/// o program counter e a tabela de saltos.
const Interpretador = struct {
    memoria: [TAMANHO_MEMORIA]u8,
    ponteiro: usize,
    pc: usize, // program counter
    programa: []const u8,
    tabela_saltos: []usize,
    modo_debug: bool,

    const Self = @This();

    pub fn init(programa: []const u8, tabela: []usize, debug: bool) Self {
        var interp = Self{
            .memoria = [_]u8{0} ** TAMANHO_MEMORIA,
            .ponteiro = 0,
            .pc = 0,
            .programa = programa,
            .tabela_saltos = tabela,
            .modo_debug = debug,
        };
        _ = &interp;
        return interp;
    }

    /// Executa o programa Brainfuck completo.
    pub fn executar(self: *Self) !void {
        const stdout = io.getStdOut().writer();
        const stdin = io.getStdIn().reader();

        while (self.pc < self.programa.len) {
            const instrucao = self.programa[self.pc];

            switch (instrucao) {
                '>' => {
                    if (self.ponteiro >= TAMANHO_MEMORIA - 1) {
                        return ErrosBrainfuck.PonteiroForaDosLimites;
                    }
                    self.ponteiro += 1;
                },
                '<' => {
                    if (self.ponteiro == 0) {
                        return ErrosBrainfuck.PonteiroForaDosLimites;
                    }
                    self.ponteiro -= 1;
                },
                '+' => {
                    self.memoria[self.ponteiro] +%= 1; // wrapping add
                },
                '-' => {
                    self.memoria[self.ponteiro] -%= 1; // wrapping sub
                },
                '.' => {
                    try stdout.writeByte(self.memoria[self.ponteiro]);
                },
                ',' => {
                    self.memoria[self.ponteiro] = stdin.readByte() catch 0;
                },
                '[' => {
                    if (self.memoria[self.ponteiro] == 0) {
                        self.pc = self.tabela_saltos[self.pc];
                    }
                },
                ']' => {
                    if (self.memoria[self.ponteiro] != 0) {
                        self.pc = self.tabela_saltos[self.pc];
                    }
                },
                else => {
                    // Comentário — ignorar qualquer outro caractere
                },
            }

            if (self.modo_debug and (instrucao == '>' or instrucao == '<' or
                instrucao == '+' or instrucao == '-'))
            {
                try self.imprimirDebug(stdout);
            }

            self.pc += 1;
        }
    }

    /// Imprime o estado atual da memória para depuração.
    fn imprimirDebug(self: *const Self, writer: anytype) !void {
        try writer.print("\n[DEBUG] PC={d} PTR={d} | ", .{ self.pc, self.ponteiro });

        // Mostra as primeiras 20 células com destaque na célula atual
        const limite = @min(20, TAMANHO_MEMORIA);
        for (0..limite) |i| {
            if (i == self.ponteiro) {
                try writer.print("[{d}]", .{self.memoria[i]});
            } else {
                try writer.print(" {d} ", .{self.memoria[i]});
            }
        }
        try writer.print("\n", .{});
    }
};

Passo 4: Exemplos de Programas Brainfuck

Vamos incluir alguns programas de exemplo embutidos no nosso interpretador:

/// Programas de exemplo embutidos para demonstração.
const Exemplos = struct {
    /// "Hello World!" — o clássico
    const hello_world =
        "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]" ++
        ">>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";

    /// Soma dois números (lê dois dígitos ASCII, imprime a soma)
    const soma =
        ",>," ++ // lê dois dígitos
        "[<+>-]" ++ // soma o segundo no primeiro
        "<" ++ // volta ao resultado
        "------------------------------------------------." // ajusta ASCII e imprime
    ;

    /// Imprime os números de 0 a 9
    const contagem =
        "++++++++++++++++++++++++++++++++++++++++++++++++." ++ // '0'
        ">++++++++++<" ++ // newline = 10
        "[>.<+.[-]" ++ // imprime, incrementa, imprime
        "++++++++++++++++++++++++++++++++++++++++++++++++." ++ // reset para '0'
        ">]";

    /// Copia a entrada para a saída (cat)
    const cat = ",[.,]";
};

Passo 5: Função Main e CLI

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const stdout = io.getStdOut().writer();
    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);

    var programa: []const u8 = undefined;
    var programa_alocado: ?[]u8 = null;
    defer if (programa_alocado) |p| allocator.free(p);
    var debug = false;

    // Parsing de argumentos
    if (args.len < 2) {
        // Sem argumentos: modo interativo
        try stdout.print(
            \\
            \\  ==========================================
            \\     BRAINFUCK INTERPRETER - Zig
            \\  ==========================================
            \\  Uso: brainfuck <arquivo.bf>
            \\       brainfuck -e "<codigo>"
            \\       brainfuck --exemplo hello
            \\  Flags: -d para modo debug
            \\  ==========================================
            \\
            \\  Exemplos disponiveis: hello, soma, cat
            \\  Executando "Hello World" como demonstracao...
            \\
            \\
        , .{});
        programa = Exemplos.hello_world;
    } else {
        var i: usize = 1;
        while (i < args.len) : (i += 1) {
            const arg = args[i];
            if (mem.eql(u8, arg, "-d") or mem.eql(u8, arg, "--debug")) {
                debug = true;
            } else if (mem.eql(u8, arg, "-e")) {
                i += 1;
                if (i < args.len) {
                    programa = args[i];
                }
            } else if (mem.eql(u8, arg, "--exemplo")) {
                i += 1;
                if (i < args.len) {
                    const nome = args[i];
                    if (mem.eql(u8, nome, "hello")) {
                        programa = Exemplos.hello_world;
                    } else if (mem.eql(u8, nome, "soma")) {
                        programa = Exemplos.soma;
                    } else if (mem.eql(u8, nome, "cat")) {
                        programa = Exemplos.cat;
                    } else {
                        try stdout.print("Exemplo desconhecido: {s}\n", .{nome});
                        return;
                    }
                }
            } else {
                // Tratar como arquivo
                const conteudo = fs.cwd().readFileAlloc(allocator, arg, 1024 * 1024) catch |err| {
                    try stdout.print("Erro ao ler arquivo '{s}': {}\n", .{ arg, err });
                    return;
                };
                programa_alocado = conteudo;
                programa = conteudo;
            }
        }
    }

    // Validar e construir tabela de saltos
    const tabela = construirTabelaDeSaltos(programa, allocator) catch |err| {
        switch (err) {
            ErrosBrainfuck.BracketDesbalanceado => {
                try stdout.print("Erro: brackets [ ] desbalanceados no programa\n", .{});
                return;
            },
            else => return err,
        }
    };
    defer allocator.free(tabela);

    // Executar
    var interp = Interpretador.init(programa, tabela, debug);
    interp.executar() catch |err| {
        switch (err) {
            ErrosBrainfuck.PonteiroForaDosLimites => {
                try stdout.print("\nErro: ponteiro saiu dos limites da memoria (0-{d})\n", .{TAMANHO_MEMORIA - 1});
            },
            else => {
                try stdout.print("\nErro durante execucao: {}\n", .{err});
            },
        }
    };

    try stdout.print("\n", .{});
}

Passo 6: Testes

test "tabela de saltos simples" {
    const programa = "[+-]";
    const tabela = try construirTabelaDeSaltos(programa, std.testing.allocator);
    defer std.testing.allocator.free(tabela);

    try std.testing.expectEqual(@as(usize, 3), tabela[0]); // '[' -> ']'
    try std.testing.expectEqual(@as(usize, 0), tabela[3]); // ']' -> '['
}

test "tabela de saltos aninhada" {
    const programa = "[[]]";
    const tabela = try construirTabelaDeSaltos(programa, std.testing.allocator);
    defer std.testing.allocator.free(tabela);

    try std.testing.expectEqual(@as(usize, 3), tabela[0]);
    try std.testing.expectEqual(@as(usize, 2), tabela[1]);
    try std.testing.expectEqual(@as(usize, 1), tabela[2]);
    try std.testing.expectEqual(@as(usize, 0), tabela[3]);
}

test "brackets desbalanceados" {
    const resultado = construirTabelaDeSaltos("[[]", std.testing.allocator);
    try std.testing.expectError(ErrosBrainfuck.BracketDesbalanceado, resultado);
}

test "bracket fechando sem abrir" {
    const resultado = construirTabelaDeSaltos("]", std.testing.allocator);
    try std.testing.expectError(ErrosBrainfuck.BracketDesbalanceado, resultado);
}

test "programa sem brackets" {
    const programa = "+++.";
    const tabela = try construirTabelaDeSaltos(programa, std.testing.allocator);
    defer std.testing.allocator.free(tabela);
    // Não deve dar erro
}

Compilando e Executando

# Compilar e rodar o Hello World embutido
zig build run

# Executar um arquivo Brainfuck
zig build run -- programa.bf

# Executar código inline
zig build run -- -e "++++++++[>++++++++++<-]>++.--."

# Modo debug
zig build run -- -d -e "+++>++<."

# Rodar testes
zig build test

Conceitos Aprendidos

  • Tabela de saltos para otimizar loops
  • Wrapping arithmetic (+%=, -%=) para overflow intencional
  • Union types para representar instruções
  • Validação de entrada antes da execução
  • Leitura de arquivos com a stdlib

Próximos Passos

Explore Mais

🚀 Primeiros Passos 🔧 Build System 📋 Receitas Prontas 💼 Vagas e Carreira ❓ FAQ (50 Perguntas) 🔄 Migrar de Outra Linguagem

Artigos relacionados

Continue aprendendo Zig

Explore mais tutoriais e artigos em português para dominar a linguagem Zig.

📚 Ver Todos os Tutoriais 💬 Junte-se à Comunidade