Quando eu decidi aprender como a JVM funciona por dentro, eu precisava de uma linguagem simples o suficiente pra não atrapalhar o aprendizado. Algo onde eu pudesse focar na mecânica do compilador sem me perder na complexidade da linguagem fonte.

Brainfuck foi a escolha óbvia.

Esse é o primeiro post de uma série de três onde a gente vai construir, do zero, um compilador que transforma código Brainfuck em bytecode JVM executável. Sem dependências externas, sem framework, só Node.js puro. No final da série, você vai ter um compilador que gera arquivos .class válidos que rodam direto no java.

O código completo tá no GitHub. Nesse primeiro post, a gente vai construir o interpretador - que é a base pra tudo que vem depois.

O que é Brainfuck

Brainfuck é uma linguagem de programação esotérica criada em 1993 por Urban Müller. Ela tem 8 comandos. Oito. E ainda assim é Turing-completa - ou seja, em teoria, você pode computar qualquer coisa que qualquer outra linguagem computa.

O modelo de execução é simples:

• Uma fita de memória com 30.000 células, cada uma armazenando um byte (0-255)
• Um ponteiro que aponta pra célula atual
• Entrada e saída (stdin/stdout)

Os 8 comandos:

Comando	O que faz
+	Incrementa o valor da célula atual
-	Decrementa o valor da célula atual
>	Move o ponteiro uma célula pra direita
<	Move o ponteiro uma célula pra esquerda
.	Imprime o valor da célula atual como caractere ASCII
,	Lê um byte da entrada e armazena na célula atual
[	Se a célula atual é zero, pula pro ] correspondente
]	Se a célula atual não é zero, volta pro [ correspondente

Qualquer outro caractere é ignorado - o que significa que você pode escrever comentários livremente no meio do código.

Um exemplo simples

Pra imprimir a letra “A” (código ASCII 65), você precisa colocar o valor 65 na célula e usar .:

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ .

São 65 sinais de + seguidos de um .. Funciona, mas é feio. Uma forma mais elegante:

++++++++[>++++++++<-]>+.

O que isso faz:

1. Coloca 8 na célula 0
2. Entra no loop [...]
3. Move pra célula 1, soma 8, volta pra célula 0, subtrai 1
4. O loop roda 8 vezes, então célula 1 fica com 64 (8 x 8)
5. Move pra célula 1, soma 1 (agora é 65)
6. Imprime: “A”

Esse padrão de multiplicação com loops é a base de qualquer programa Brainfuck não-trivial.

Fase 1: o tokenizer

O tokenizer é a parte mais simples de todo o projeto. A gente precisa pegar o código fonte e extrair só os caracteres válidos, descartando tudo que não é um dos 8 comandos.

const VALID_TOKENS = new Set(['+', '-', '>', '<', '[', ']', '.', ',']);

function tokenizeBrainfuck(code) {
  const tokens = [];

  for (let i = 0; i < code.length; i++) {
    if (VALID_TOKENS.has(code[i])) {
      tokens.push(code[i]);
    }
  }

  return tokens;
}

Dado o input ++[>+<-] este texto é ignorado ., o tokenizer retorna:

['+', '+', '[', '>', '+', '<', '-', ']', '.']

Simples assim. Todos os espaços, letras e pontuação que não são comandos Brainfuck somem.

Fase 2: o parser e a Representação Intermediária

Em vez de executar os tokens diretamente, a gente vai transformar eles numa Representação Intermediária (IR). A IR é uma lista de instruções que descrevem o programa de forma mais estruturada.

Por que não executar os tokens diretamente? Dois motivos:

1. Otimização: podemos combinar operações consecutivas. ++++ não precisa ser 4 instruções separadas - é uma instrução só com valor 4.
2. Desacoplamento: a IR permite que a gente separe o parser do backend. Hoje o backend é um interpretador JavaScript, mas na parte 3 da série vai ser um gerador de bytecode JVM. A IR é a mesma.

As instruções da IR

Instrução	O que faz
increment n	Soma n à célula atual (n pode ser negativo)
move_head h	Move o ponteiro pra posição absoluta h
jump_eqz i	Se célula atual == 0, pula pra instrução i
jump_neqz i	Se célula atual != 0, pula pra instrução i
input	Lê um byte da entrada
output	Escreve a célula atual na saída
halt	Fim do programa

Combinando operações consecutivas

A otimização mais importante do parser é combinar operações do mesmo tipo. A função handleSubsequent faz isso:

function handleSubsequent(tokens, charMap, token, pos) {
  let value = charMap[token];
  let newPos = pos;

  while (newPos + 1 < tokens.length && tokens[newPos + 1] in charMap) {
    newPos++;
    value += charMap[tokens[newPos]];
  }

  return { inc: value, newPos };
}

O charMap mapeia cada token pro seu valor numérico. Pra incrementos: {'+': 1, '-': -1}. Pra movimentos: {'>': 1, '<': -1}.

O que isso nos dá na prática:

Tokens	IR gerada
++++	{ type: 'increment', inc: 4 }
+++--	{ type: 'increment', inc: 1 }
++--	Nenhuma instrução (se cancela)
>>>>	{ type: 'move_head', head: 4 }
>><<	Nenhuma instrução (volta pro mesmo lugar)

Essa otimização é simples mas faz diferença. Um “Hello World” em Brainfuck tem centenas de + e - consecutivos.

Resolvendo os jumps

A parte mais complicada do parser é resolver os pares [ e ]. A gente usa uma pilha (loopStack) pra rastrear os colchetes abertos:

function parseBrainfuck(code) {
  const tokens = tokenizeBrainfuck(code);
  const instructions = [];
  const loopStack = [];
  let pointer = 0;

  for (let pos = 0; pos < tokens.length; pos++) {
    const token = tokens[pos];

    switch (token) {
      case '+':
      case '-': {
        const result = handleSubsequent(tokens, {'+': 1, '-': -1}, token, pos);
        if (result.inc !== 0) {
          instructions.push({ type: 'increment', inc: result.inc });
        }
        pos = result.newPos;
        break;
      }

      case '>':
      case '<': {
        const result = handleSubsequent(tokens, {'>': 1, '<': -1}, token, pos);
        pointer += result.inc;
        if (result.inc !== 0) {
          instructions.push({ type: 'move_head', head: pointer });
        }
        pos = result.newPos;
        break;
      }

      case '.':
        instructions.push({ type: 'output' });
        break;

      case ',':
        instructions.push({ type: 'input' });
        break;

      case '[':
        loopStack.push(instructions.length);
        instructions.push({ type: 'jump_eqz', jmp: -1 }); // placeholder
        break;

      case ']': {
        const openIndex = loopStack.pop();
        if (openIndex === undefined) {
          throw new Error('Unmatched ]');
        }
        instructions[openIndex].jmp = instructions.length + 1;
        instructions.push({ type: 'jump_neqz', jmp: openIndex + 1 });
        break;
      }
    }
  }

  if (loopStack.length > 0) {
    throw new Error('Unmatched [');
  }

  instructions.push({ type: 'halt' });
  return instructions;
}

O truque é o seguinte:

1. Quando encontra [, empilha o índice da instrução atual e emite um jump_eqz com destino -1 (placeholder).
2. Quando encontra ], desempilha o índice do [ correspondente.
3. Atualiza o jmp do [ pra apontar pra instrução depois do ].
4. O ] aponta de volta pra instrução depois do [.

Visualmente:

Instruções:  [0]  [1]  [2]  [3]  [4]  [5]  [6]
             inc  jeqz inc  inc  jneqz inc  halt
                  jmp→5          jmp→2

O jump_eqz na posição 1 pula pra posição 5 (saída do loop) se a célula é zero. O jump_neqz na posição 4 volta pra posição 2 (início do corpo do loop) se a célula não é zero.

O ponteiro absoluto

Uma decisão de design que vale mencionar: o move_head usa posição absoluta, não relativa. O parser mantém uma variável pointer que rastreia a posição virtual do ponteiro durante o parsing.

Isso simplifica a geração de bytecode lá na parte 3, porque na JVM a gente pode simplesmente fazer sipush valor; istore_2 pra definir o ponteiro, sem precisar carregar o valor atual e somar.

Fase 3: o interpretador

Com a IR pronta, o interpretador é direto. É um loop de fetch-decode-execute:

function executeBrainfuck(code, memory = new Uint8Array(30000)) {
  const instructions = parseBrainfuck(code);
  let pointer = 0;
  let pc = 0;
  const output = [];

  while (pc < instructions.length) {
    const instruction = instructions[pc];

    if (instruction.type === 'halt') break;

    switch (instruction.type) {
      case 'increment':
        memory[pointer] = (memory[pointer] + instruction.inc) & 0xFF;
        break;

      case 'move_head':
        pointer = instruction.head;
        break;

      case 'output':
        process.stdout.write(String.fromCharCode(memory[pointer]));
        break;

      case 'input':
        // lê um byte de stdin
        memory[pointer] = readByte();
        break;

      case 'jump_eqz':
        if (memory[pointer] === 0) {
          pc = instruction.jmp;
          continue; // pula o pc++ no final
        }
        break;

      case 'jump_neqz':
        if (memory[pointer] !== 0) {
          pc = instruction.jmp;
          continue;
        }
        break;
    }

    pc++;
  }

  return { cells: memory, currentCell: pointer };
}

Alguns detalhes que vale notar.

O & 0xFF no incremento garante que o valor fica no range de um byte (0-255). Se uma célula tá com 255 e você incrementa, ela volta pra 0. Se tá com 0 e decrementa, vai pra 255. É o comportamento esperado de Brainfuck.

O continue nos jumps é necessário porque a gente não quer incrementar o pc quando um salto é tomado. O jmp já aponta pra instrução correta. Sem o continue, o pc++ no final do loop rodaria e a gente pularia uma instrução.

O String.fromCharCode transforma o valor numérico da célula no caractere ASCII correspondente. Célula com 65 imprime “A”, com 72 imprime “H”.

Testando

Pra verificar que tudo funciona, a gente pode rodar o clássico “Hello, World!” em Brainfuck:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>
---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

Se tudo deu certo, o output é Hello, World!.

Você pode testar manualmente ou escrever testes automatizados. O projeto BrainJuck usa o test runner nativo do Node.js (node:test):

import { describe, it } from 'node:test';
import assert from 'node:assert';

describe('tokenizer', () => {
  it('extrai apenas tokens válidos', () => {
    const tokens = tokenizeBrainfuck('++ comentario >> .');
    assert.deepStrictEqual(tokens, ['+', '+', '>', '>', '.']);
  });
});

describe('parser', () => {
  it('combina incrementos consecutivos', () => {
    const ir = parseBrainfuck('++++---');
    assert.equal(ir[0].type, 'increment');
    assert.equal(ir[0].inc, 1);
  });

  it('elimina movimentos que se cancelam', () => {
    const ir = parseBrainfuck('>><<');
    assert.equal(ir[0].type, 'halt');
  });
});

Recapitulando

Até aqui a gente construiu:

1. Um tokenizer que extrai os 8 comandos válidos do código fonte
2. Um parser que transforma tokens em IR, com otimizações de combinação
3. Um interpretador que executa a IR

O pipeline completo:

Código fonte (.bf) -> Tokenizer -> Parser -> IR -> Interpretador -> Output

A IR é o que conecta o parser ao backend. No próximo post, a gente vai trocar o interpretador por um gerador de bytecode JVM. Mas antes disso, a gente precisa entender o formato .class da JVM - que é o assunto da parte 2.

O código desse post tá em geeksilva97/brainjuck. Os commits relevantes são os primeiros do projeto - em especial o a171e9a (functional brainfuck) e o 437d37c (the simplest parser ever).

Por hoje é só. Abraços.