Revisitando Let’s Build a Compiler

• Projeto que reimplementa o tutorial ‘Let’s Build a Compiler’, de Jack Crenshaw, publicado entre 1988 e 1995, usando Python e WebAssembly
• O original usava Pascal e assembly Motorola 68000, mas nesta releitura foi convertido para código executável em um ambiente moderno
• O ponto central do tutorial é implementar diretamente um parser recursivo descendente (recursive-descent parser) e adotar uma abordagem que gera código assembly real desde as etapas iniciais
• A abordagem de Crenshaw usa tradução dirigida pela sintaxe (syntax-directed translation), mas revela limitações na etapa de tratamento de tipos
• Esta reimplementação se destaca por restaurar o tutorial clássico em uma forma que desenvolvedores modernos podem executar e experimentar diretamente

---

Contexto do tutorial clássico

• ‘Let’s Build a Compiler’, de Jack Crenshaw, é um guia introdutório sobre construção de compiladores publicado entre 1988 e 1995, ainda frequentemente citado hoje
  • O texto original foi escrito em Pascal e emitia código assembly Motorola 68000
  • Mesmo 35 anos depois, em 2025, ele continua sendo lembrado com frequência em lugares como o Hacker News
• O autor do texto conheceu esse tutorial pela primeira vez em 2003 e ficou profundamente impressionado; em 2025, resolveu adaptá-lo novamente para Python e WebAssembly

Reimplementação em Python e WebAssembly

• Em vez de apenas reler o material, ele traduziu o compilador do tutorial para Python e o implementou para gerar WebAssembly (WASM)
• O resultado foi publicado no repositório GitHub (eliben/letsbuildacompiler)
  • O arquivo TUTORIAL.md explica como cada parte do original foi mapeada para código Python
  • Os leitores podem acompanhar o tutorial original e experimentar código realmente executável por conta própria

Exemplo da linguagem KISS e saída em WASM

• É apresentado o resultado de compilar, com a versão em Python do compilador, um programa de exemplo da linguagem KISS projetada por Crenshaw
  • O exemplo inclui procedure, laço while, passagem por valor e por referência
• O texto WASM gerado inclui a lógica de tratamento de parâmetros por referência (by-reference parameter), com quase nenhuma otimização aplicada
• A parte em que a variável global X é retornada implicitamente pela função main é um recurso para facilitar os testes
• O código WASM gerado é usado em testes que verificam os resultados esperados por meio de execução real

Pontos fortes do tutorial

• O tutorial de Crenshaw constrói passo a passo um parser recursivo descendente e prioriza geração de código funcional na prática em vez de teoria complexa
  • Na época, lex e yacc eram vistos como padrão, mas a simplicidade e clareza de um parser escrito manualmente causaram grande impacto
  • Depois disso, ao longo de 20 anos, o autor passou a preferir parsers recursivos descendentes manuais
• Além disso, numa época em que a maioria dos cursos se concentrava em análise sintática, Crenshaw já tratava de geração de código assembly desde as fases iniciais

Limitações e possibilidades de melhoria

• O tutorial usa a abordagem de tradução dirigida pela sintaxe (syntax-directed translation), gerando código diretamente durante o parsing
  • Essa abordagem é útil para aprendizado, mas tem a limitação de dificultar otimizações, já que as informações de tipo não são conhecidas antecipadamente
• Em especial, a partir da parte 14, quando tipos são introduzidos, fica claro que é necessário um método mais estruturado com representação intermediária (IR) ou AST
• Crenshaw não explicou explicitamente por que interrompeu o tutorial após a parte 14, mas é mencionado que isso pode estar relacionado a essa limitação
• O autor avalia que usar a parte 14 como ponto de virada para gerar uma AST e depois fazer verificação de tipos e geração de código seria uma abordagem mais adequada

Conclusão

• O tutorial original continua oferecendo excelente legibilidade e utilidade prática como introdução à construção de compiladores
• Esta versão em Python e WASM complementa o material para que desenvolvedores modernos possam aprender sem depender de tecnologias antiquadas
• Com o repositório no GitHub, qualquer pessoa pode experimentar, e o projeto é visto como uma releitura moderna que permite vivenciar diretamente a estrutura de um compilador

[GN⁺]

Comentários do Hacker News

• Gosto do fato de o tutorial não se perder nos detalhes do frontend e já começar gerando código assembly funcional desde o início
  A abordagem de Ghuloum, de construir tudo a partir de uma parte bem pequena da linguagem e ir expandindo gradualmente, é especialmente atraente
  Um bom livro que descobri recentemente é este aqui; embora C e x86 não sejam os melhores alvos para iniciantes, foi um ótimo material para fazer um primeiro compilador
  Para referência, o artigo de Ghuloum está aqui

  • Este é um caso raro, mas acho que é um exemplo em que a abordagem acadêmica na prática não combina com utilidade real
    No passado, parsing era a parte mais importante, então o currículo foi estruturado assim, mas hoje em dia o mais importante é como implementar os recursos da linguagem
    Mesmo que você vá criar um compilador por conta própria, agora vivemos numa época em que basta dizer “Claude, crie um parser recursivo descendente com esta gramática” e quase sempre sai algo utilizável de primeira
  • Senti claramente a diferença entre pesquisadores acadêmicos e desenvolvedores de mercado
    A academia tende a pensar em termos de camadas (layers), enquanto quem trabalha na prática tende a pensar em pipes
    A abordagem em camadas entrega código compilável, mas difícil de executar; a abordagem em pipe facilita executar, mas tem menos estrutura
    No fim, o essencial é desenvolver dividindo o problema em unidades mínimas executáveis

• Acho que esse texto acertou em cheio no ponto central
  Eu me interessava por compiladores desde antes de entrar na faculdade, e este foi o material introdutório mais acessível que encontrei
  Aos 17 anos, ao implementar eu mesmo um parser recursivo descendente, percebi que até problemas que pareciam complexos ficam simples quando você os divide nas primitivas corretas

  • “Dividir o problema nas primitivas corretas” é o verdadeiro cerne da programação
    Há muito material sobre algoritmos, mas pouco sobre como abordar problemas a partir de primitivas
  • Recursive descent não é só uma forma de criar parsers, mas também uma lição de projeto de software
    Antigamente, parsers baseados em tabelas como yacc eram o padrão, mas hoje recursive descent é mais prático e flexível
    Com geração de código por LLM, essa abordagem ficou ainda mais fácil
    Em compiladores didáticos, dá para pular AST, IR e otimizações e ir direto para geração de código sem perder valor educacional
    No passado, ao criar na empresa uma ferramenta de testes que suportava um subconjunto de C, fizemos o parser retornar uma estrutura de dados executável em vez de gerar código
    Por exemplo, uma classe ForLoopStatement continha testExpression e o método Execute() a chamava diretamente
  • O artigo de 1971 de Niklaus Wirth, Program Development by Stepwise Refinement, é um clássico que estabeleceu esse modo de pensar bem cedo
    Também é um artigo importante mencionado em The Mythical Man-Month, de Fred Brooks
  • Hoje em dia, sempre que preciso de parsing, acabo usando parser combinators
    Conceitualmente, é algo muito natural e elegante

• Achei interessante a explicação de que o tutorial do Jack Crenshaw usa a abordagem de syntax-directed translation
  Fiquei curioso se isso significa apenas um compilador single-pass ou se é um conceito mais específico
  Entendo que, em linguagens estaticamente tipadas, otimizações baseadas em tipos sejam difíceis, mas queria saber se isso também impõe limitações ao nível da verificação de tipos

  • Se a linguagem-alvo segue a regra de definição antes do uso e não tem inferência de tipos complexa, então dá para fazer coisas como otimizações baseadas em tipo ou constant folding
    Mas sem IR, otimizações avançadas como LICM, CSE e GVN são impossíveis
    Pessoalmente, prefiro uma compilação em 2 passes por função — no primeiro passo, gero o IR; depois gero o código imediatamente e descarto o estado, o que dá resultados rápidos e eficientes
  • syntax-directed translation é um conceito mais específico: significa gerar código imediatamente enquanto o código-fonte é lido
    Mesmo um compilador single-pass pode separar as etapas e só fazer a geração de código no final

• O tutorial do Crenshaw não chega a um nível prático, mas fica muito mais útil se for estendido com a técnica de precedence climbing
  Um bom texto sobre isso está neste link

• Dei mais uma olhada em threads sobre “Let’s Build a Compiler”
  Há vários registros de postagens no HN de 2007 até 2023 neste link
  Em especial, a entrevista com Jack Crenshaw não tem comentários, mas foi uma leitura muito interessante

  • O quarto link não é o texto do Crenshaw, e sim outro texto com o mesmo título
  • A entrevista com Crenshaw foi realmente muito boa

• Divulgação e apresentação de um projeto pessoal: cwerg.org
  Usa Python e parsing recursivo descendente, e separa frontend e backend com IR
  Gera binários ELF para x86 e ARM e tem como objetivo uso real
  Só que é complexo e não tem estilo de tutorial

• Tenho lembranças de ter aprendido com o tutorial do Jack Crenshaw no grupo da USENET comp.compilers
  Para referência, o grupo ainda está ativo

• Como abordagem moderna para compiladores, recomendo este post do blog de Cornell

  • Graças ao LLVM, fazer compiladores ficou surpreendentemente fácil
    Toda vez que uso, parece que estou só empilhando algumas pedras em cima de uma pirâmide
  • Mas o LLVM tem limitações por ser uma abordagem indireta
    Linguagens que usam LLVM como backend têm em comum compilação lenta
    O Zig reconheceu isso e está desenvolvendo seu próprio backend, enquanto Rust continua preso a compilações lentas
    O LLVM passa a impressão de que complexidade garante qualidade e, na minha opinião, é uma tecnologia que reduz a autonomia do desenvolvedor
    Isso se parece com outras tecnologias populares cujas iniciais são parecidas

• Eu também escrevi um tutorial chamado tiny-optimizing-compiler por motivos semelhantes
  É um exemplo conciso que trata apenas das etapas intermediárias e do backend de um compilador
  Link do GitHub

  • Implementar isso em Lean provavelmente seria divertido

• Quando era mais novo, eu imprimia esse tutorial e andava com ele para ler
  Ver um compilador ficar pronto em tão pouco tempo era realmente incrível
  Materiais desse tipo, como o Beej’s Guide, estão entre os documentos mais valiosos para o ensino de ciência da computação, mas não recebem o reconhecimento merecido