Brainfuck é uma linguagem de programação esotérica com apenas 8 instruções, o que a torna perfeita para aprender os fundamentos de construção de compiladores. Apesar da simplicidade, Brainfuck é Turing-completa — qualquer programa pode ser escrito nela. Neste projeto, vamos construir tanto um interpretador quanto um compilador que traduz Brainfuck para bytecode otimizado e o executa em uma máquina virtual.
Este walkthrough cobre o pipeline completo de um compilador: tokenização, construção de AST, otimização e execução. Esses conceitos se aplicam diretamente a linguagens reais e são a base da ciência da computação.
O Que Vamos Construir
Um compilador Brainfuck completo com:
- Tokenizador que filtra caracteres não-instrucionais
- Parser que constrói uma AST com suporte a loops aninhados
- Otimizador que mescla operações repetidas (
+++viraAdd(3)) - Máquina virtual (VM) que executa bytecode otimizado
- Interpretador direto para comparação de performance
- Modo de execução com estatísticas (contagem de instruções)
As 8 instruções Brainfuck: > (avança ponteiro), < (recua ponteiro), + (incrementa célula), - (decrementa célula), . (imprime caractere), , (lê caractere), [ (início de loop), ] (fim de loop).
Estrutura do Projeto
compilador-bf/
├── Cargo.toml
└── src/
├── main.rs
├── tokenizer.rs
├── ast.rs
├── otimizador.rs
└── vm.rs
Configurando o Projeto
cargo new compilador-bf
cd compilador-bf
[package]
name = "compilador-bf"
version = "0.1.0"
edition = "2021"
Passo 1: Tokenizador e AST
O tokenizador filtra todos os caracteres que não são instruções Brainfuck. Em seguida, o parser constrói uma árvore sintática onde loops ([...]) são representados como nós com filhos.
Crie o arquivo src/tokenizer.rs:
/// Token Brainfuck
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Token {
Avanca, // >
Recua, // <
Incrementa, // +
Decrementa, // -
Imprime, // .
Le, // ,
AbreLaco, // [
FechaLaco, // ]
}
/// Converte o código-fonte em uma lista de tokens, ignorando comentários
pub fn tokenizar(fonte: &str) -> Vec<Token> {
fonte
.chars()
.filter_map(|c| match c {
'>' => Some(Token::Avanca),
'<' => Some(Token::Recua),
'+' => Some(Token::Incrementa),
'-' => Some(Token::Decrementa),
'.' => Some(Token::Imprime),
',' => Some(Token::Le),
'[' => Some(Token::AbreLaco),
']' => Some(Token::FechaLaco),
_ => None, // Qualquer outro caractere é comentário
})
.collect()
}
Crie o arquivo src/ast.rs:
use crate::tokenizer::Token;
/// Nó da árvore sintática abstrata
#[derive(Debug, Clone)]
pub enum No {
Avanca,
Recua,
Incrementa,
Decrementa,
Imprime,
Le,
Laco(Vec<No>), // Contém os nós dentro do loop
}
/// Constrói a AST a partir dos tokens
pub fn construir_ast(tokens: &[Token]) -> Result<Vec<No>, String> {
let (nos, posicao) = analisar_bloco(tokens, 0, false)?;
if posicao < tokens.len() {
return Err(format!(
"']' inesperado na posição {} (sem '[' correspondente)",
posicao
));
}
Ok(nos)
}
fn analisar_bloco(
tokens: &[Token],
mut pos: usize,
dentro_laco: bool,
) -> Result<(Vec<No>, usize), String> {
let mut nos = Vec::new();
while pos < tokens.len() {
match tokens[pos] {
Token::Avanca => nos.push(No::Avanca),
Token::Recua => nos.push(No::Recua),
Token::Incrementa => nos.push(No::Incrementa),
Token::Decrementa => nos.push(No::Decrementa),
Token::Imprime => nos.push(No::Imprime),
Token::Le => nos.push(No::Le),
Token::AbreLaco => {
let (corpo, nova_pos) = analisar_bloco(tokens, pos + 1, true)?;
nos.push(No::Laco(corpo));
pos = nova_pos;
}
Token::FechaLaco => {
if !dentro_laco {
return Err(format!(
"']' inesperado na posição {} (sem '[' correspondente)",
pos
));
}
return Ok((nos, pos));
}
}
pos += 1;
}
if dentro_laco {
return Err("'[' sem ']' correspondente (laço não fechado)".to_string());
}
Ok((nos, pos))
}
#[cfg(test)]
mod testes {
use super::*;
use crate::tokenizer::tokenizar;
#[test]
fn testar_ast_simples() {
let tokens = tokenizar("++[>+<-].");
let ast = construir_ast(&tokens).unwrap();
assert_eq!(ast.len(), 3); // ++, [>+<-], .
}
#[test]
fn testar_laco_nao_fechado() {
let tokens = tokenizar("[+");
assert!(construir_ast(&tokens).is_err());
}
#[test]
fn testar_fecha_sem_abrir() {
let tokens = tokenizar("+]");
assert!(construir_ast(&tokens).is_err());
}
}
Passo 2: O Otimizador
O otimizador mescla operações consecutivas iguais em uma única instrução com contagem. Por exemplo, +++ se torna Somar(3) e >>> se torna MoverDireita(3). Isso reduz drasticamente o número de instruções executadas.
Crie o arquivo src/otimizador.rs:
use crate::ast::No;
/// Instrução otimizada (bytecode)
#[derive(Debug, Clone)]
pub enum Instrucao {
/// Move o ponteiro para a direita N posições
MoverDireita(usize),
/// Move o ponteiro para a esquerda N posições
MoverEsquerda(usize),
/// Soma N ao valor da célula atual
Somar(u8),
/// Subtrai N do valor da célula atual
Subtrair(u8),
/// Imprime o caractere da célula atual
Imprimir,
/// Lê um caractere para a célula atual
Ler,
/// Início de loop: se a célula atual for 0, pula para depois do LoopFim
LoopInicio(usize), // índice do LoopFim correspondente
/// Fim de loop: se a célula atual não for 0, volta para LoopInicio
LoopFim(usize), // índice do LoopInicio correspondente
/// Zera a célula atual (otimização de [-])
Zerar,
}
/// Otimiza a AST e gera bytecode
pub fn otimizar(nos: &[No]) -> Vec<Instrucao> {
let mut instrucoes = Vec::new();
gerar_instrucoes(nos, &mut instrucoes);
resolver_saltos(&mut instrucoes);
instrucoes
}
fn gerar_instrucoes(nos: &[No], saida: &mut Vec<Instrucao>) {
let mut i = 0;
while i < nos.len() {
match &nos[i] {
No::Avanca => {
let contagem = contar_consecutivos(nos, i, |n| matches!(n, No::Avanca));
saida.push(Instrucao::MoverDireita(contagem));
i += contagem;
}
No::Recua => {
let contagem = contar_consecutivos(nos, i, |n| matches!(n, No::Recua));
saida.push(Instrucao::MoverEsquerda(contagem));
i += contagem;
}
No::Incrementa => {
let contagem = contar_consecutivos(nos, i, |n| matches!(n, No::Incrementa));
saida.push(Instrucao::Somar(contagem as u8));
i += contagem;
}
No::Decrementa => {
let contagem = contar_consecutivos(nos, i, |n| matches!(n, No::Decrementa));
saida.push(Instrucao::Subtrair(contagem as u8));
i += contagem;
}
No::Imprime => {
saida.push(Instrucao::Imprimir);
i += 1;
}
No::Le => {
saida.push(Instrucao::Ler);
i += 1;
}
No::Laco(corpo) => {
// Otimização: [-] e [+] zeram a célula
if corpo.len() == 1
&& (matches!(corpo[0], No::Decrementa)
|| matches!(corpo[0], No::Incrementa))
{
saida.push(Instrucao::Zerar);
} else {
saida.push(Instrucao::LoopInicio(0)); // placeholder
gerar_instrucoes(corpo, saida);
saida.push(Instrucao::LoopFim(0)); // placeholder
}
i += 1;
}
}
}
}
/// Conta quantos nós consecutivos satisfazem a condição
fn contar_consecutivos<F>(nos: &[No], inicio: usize, condicao: F) -> usize
where
F: Fn(&No) -> bool,
{
let mut contagem = 0;
let mut pos = inicio;
while pos < nos.len() && condicao(&nos[pos]) {
contagem += 1;
pos += 1;
}
contagem
}
/// Resolve os endereços de salto dos loops
fn resolver_saltos(instrucoes: &mut [Instrucao]) {
let mut pilha: Vec<usize> = Vec::new();
for i in 0..instrucoes.len() {
match instrucoes[i] {
Instrucao::LoopInicio(_) => {
pilha.push(i);
}
Instrucao::LoopFim(_) => {
if let Some(inicio) = pilha.pop() {
instrucoes[i] = Instrucao::LoopFim(inicio);
instrucoes[inicio] = Instrucao::LoopInicio(i);
}
}
_ => {}
}
}
}
A otimização mais impactante é reconhecer o padrão [-] (decrementa até zero), que aparece constantemente em programas Brainfuck. Em vez de executar um loop inteiro, simplesmente zeramos a célula.
Passo 3: A Máquina Virtual
A VM executa o bytecode otimizado. Ela mantém uma fita de memória (30.000 células, como no Brainfuck original) e um ponteiro.
Crie o arquivo src/vm.rs:
use crate::otimizador::Instrucao;
use std::io::{self, Read, Write};
/// Tamanho da fita de memória
const TAMANHO_FITA: usize = 30_000;
/// Máquina virtual para executar bytecode Brainfuck
pub struct MaquinaVirtual {
fita: Vec<u8>,
ponteiro: usize,
instrucoes_executadas: u64,
}
impl MaquinaVirtual {
pub fn new() -> Self {
Self {
fita: vec![0u8; TAMANHO_FITA],
ponteiro: 0,
instrucoes_executadas: 0,
}
}
/// Executa um programa (lista de instruções otimizadas)
pub fn executar(&mut self, programa: &[Instrucao]) -> io::Result<()> {
let mut pc: usize = 0; // program counter
while pc < programa.len() {
self.instrucoes_executadas += 1;
match &programa[pc] {
Instrucao::MoverDireita(n) => {
self.ponteiro = (self.ponteiro + n) % TAMANHO_FITA;
}
Instrucao::MoverEsquerda(n) => {
self.ponteiro = (self.ponteiro + TAMANHO_FITA - n) % TAMANHO_FITA;
}
Instrucao::Somar(n) => {
self.fita[self.ponteiro] =
self.fita[self.ponteiro].wrapping_add(*n);
}
Instrucao::Subtrair(n) => {
self.fita[self.ponteiro] =
self.fita[self.ponteiro].wrapping_sub(*n);
}
Instrucao::Imprimir => {
let caractere = self.fita[self.ponteiro];
io::stdout().write_all(&[caractere])?;
io::stdout().flush()?;
}
Instrucao::Ler => {
let mut buffer = [0u8; 1];
match io::stdin().read_exact(&mut buffer) {
Ok(()) => self.fita[self.ponteiro] = buffer[0],
Err(_) => self.fita[self.ponteiro] = 0,
}
}
Instrucao::LoopInicio(fim) => {
if self.fita[self.ponteiro] == 0 {
pc = *fim; // pula para depois do fim do loop
}
}
Instrucao::LoopFim(inicio) => {
if self.fita[self.ponteiro] != 0 {
pc = *inicio; // volta para o início do loop
}
}
Instrucao::Zerar => {
self.fita[self.ponteiro] = 0;
}
}
pc += 1;
}
Ok(())
}
/// Retorna estatísticas de execução
pub fn estatisticas(&self) -> Estatisticas {
Estatisticas {
instrucoes_executadas: self.instrucoes_executadas,
celulas_usadas: self.fita.iter().filter(|&&c| c != 0).count(),
valor_maximo: self.fita.iter().copied().max().unwrap_or(0),
}
}
/// Reseta a VM para um novo programa
pub fn resetar(&mut self) {
self.fita.fill(0);
self.ponteiro = 0;
self.instrucoes_executadas = 0;
}
}
/// Estatísticas de execução
pub struct Estatisticas {
pub instrucoes_executadas: u64,
pub celulas_usadas: usize,
pub valor_maximo: u8,
}
impl std::fmt::Display for Estatisticas {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
writeln!(f, "--- Estatísticas ---")?;
writeln!(f, "Instruções executadas: {}", self.instrucoes_executadas)?;
writeln!(f, "Células utilizadas: {}", self.celulas_usadas)?;
writeln!(f, "Valor máximo na fita: {}", self.valor_maximo)
}
}
Passo 4: Juntando Tudo no main.rs
O ponto de entrada permite executar programas Brainfuck de um arquivo ou do modo interativo.
mod ast;
mod otimizador;
mod tokenizer;
mod vm;
use std::env;
use std::fs;
use std::io::{self, BufRead, Write};
fn executar_programa(fonte: &str, mostrar_estatisticas: bool) {
// Pipeline: fonte -> tokens -> AST -> bytecode otimizado -> execução
let tokens = tokenizer::tokenizar(fonte);
let nos = match ast::construir_ast(&tokens) {
Ok(nos) => nos,
Err(e) => {
eprintln!("Erro de parsing: {}", e);
return;
}
};
let bytecode = otimizador::otimizar(&nos);
println!(
"[Compilado: {} tokens -> {} nós AST -> {} instruções otimizadas]",
tokens.len(),
contar_nos(&nos),
bytecode.len()
);
let mut maquina = vm::MaquinaVirtual::new();
if let Err(e) = maquina.executar(&bytecode) {
eprintln!("\nErro de execução: {}", e);
return;
}
println!(); // Nova linha após a saída do programa
if mostrar_estatisticas {
println!("{}", maquina.estatisticas());
}
}
fn contar_nos(nos: &[ast::No]) -> usize {
nos.iter()
.map(|no| match no {
ast::No::Laco(corpo) => 1 + contar_nos(corpo),
_ => 1,
})
.sum()
}
fn modo_interativo() {
println!("=== Compilador Brainfuck em Rust ===");
println!("Digite código Brainfuck (uma linha por vez).");
println!("Comandos especiais:");
println!(" :arquivo <caminho> - Executa arquivo .bf");
println!(" :stats - Ativa/desativa estatísticas");
println!(" :sair - Encerra o programa\n");
let stdin = io::stdin();
let mut mostrar_stats = false;
loop {
print!("bf> ");
io::stdout().flush().unwrap();
let mut linha = String::new();
if stdin.lock().read_line(&mut linha).unwrap() == 0 {
break;
}
let entrada = linha.trim();
if entrada.is_empty() {
continue;
}
if entrada == ":sair" {
println!("Até logo!");
break;
}
if entrada == ":stats" {
mostrar_stats = !mostrar_stats;
println!(
"Estatísticas: {}",
if mostrar_stats { "ATIVADAS" } else { "DESATIVADAS" }
);
continue;
}
if let Some(caminho) = entrada.strip_prefix(":arquivo ") {
match fs::read_to_string(caminho.trim()) {
Ok(fonte) => executar_programa(&fonte, mostrar_stats),
Err(e) => eprintln!("Erro ao ler arquivo: {}", e),
}
continue;
}
executar_programa(entrada, mostrar_stats);
}
}
fn main() {
let args: Vec<String> = env::args().collect();
match args.len() {
1 => modo_interativo(),
2 => {
let caminho = &args[1];
match fs::read_to_string(caminho) {
Ok(fonte) => executar_programa(&fonte, true),
Err(e) => eprintln!("Erro ao ler '{}': {}", caminho, e),
}
}
_ => {
eprintln!("Uso: {} [arquivo.bf]", args[0]);
eprintln!("Sem argumentos: modo interativo");
}
}
}
Como Executar
# Compilar
cargo build --release
# Modo interativo
cargo run
# Exemplo: Hello World em Brainfuck
bf> ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
[Compilado: 106 tokens -> 36 nós AST -> 29 instruções otimizadas]
Hello World!
# Executar a partir de um arquivo
echo "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++." > hello.bf
cargo run -- hello.bf
# Executar os testes
cargo test
Desafios para Expandir
- Compilação para Assembly: Em vez de bytecode, gere código Assembly x86-64 que pode ser montado com NASM e executado nativamente, comparando a performance com a VM.
- Mais otimizações: Implemente otimizações como copy loops (
[->+<]copia o valor para a célula vizinha) e scan loops ([>]encontra a próxima célula zero). - Depurador interativo: Adicione um modo de depuração passo a passo que mostra o estado da fita, a posição do ponteiro e a instrução atual.
- Transpilação para C: Gere código C equivalente ao programa Brainfuck e compile-o com GCC para obter um executável nativo extremamente rápido.
- Visualização da fita: Implemente uma visualização em tempo real da fita de memória no terminal usando caracteres ANSI, mostrando o ponteiro e os valores das células.
Veja Também
- Vec: Vetores Dinâmicos — a fita de memória e listas de instruções
- Módulo IO — leitura e escrita de caracteres
- Trabalhando com Strings — manipulação do código-fonte
- Iteradores em Rust — processamento funcional de tokens
- Pattern Matching Avançado — correspondência de padrões na compilação