Como ser* um compilador—construa um compilador com JavaScript

*Sim! Você deveria ser um compilador. É incrível.


Este post é uma tradução e adaptação do original em inglês escrito por Mariko Kosaka. Este post é publicado sob a licença CC BY-NC-SA 4.0.


Em um delicioso domingo in Bushwick, Brooklyn, eu encontrei um livro chamado “Design by Numbers” by John Maeda na livraria do bairro. Nesse livro tinha um passo-a-passo sobre a linguagem de programação DBN—uma linguagem criada no final dos anos 90 no MIT Media Lab, projetada pra apresentar conceitos de programação de uma maneira visual.

Exemplo de um código em DBN. Fonte: http://dbn.media.mit.edu/introduction.html

Imediatamente pensei que criar SVG a partir de DBN rodando no browser poderia ser um projeto mais interessante pra fazer em 2016 do que instalar um ambiente Java pra executar o código-fonte original em DBN.

Eu percebi que eu precisaria escrever um compilador de DBN para SVG, e foi aí que a saga de escrever um compilador começou. “Criar um compilador” parece algo de Ciências da Computação… mas eu, que nunca nem percorri nodes em um teste prático numa entrevista, conseguiria criar um compilador?

Meu compilador imaginário, onde os códigos vão para serem punidos. Se o código é ruim, ele é aprisionado numa mensagem de erro para sempre.

Primeiro vamos tentar ser um compilador

Compilador é um mecanismo que pega um pedaço de um código e transforma ele em alguma outra coisa. Vamos compilar um simples código DBN em um desenho de verdade.

Existem três comandos nesse código DBN: “Paper” define a cor do papel; “Pen” define a cor da caneta; e, “Line” desenha uma linha. 100 no parâmetro de cor significa 100% preto ou rgb(0%, 0%, 0%) em CSS. A imagem criada com DBN é sempre em em tons de cinza. No DBN, o papel é sempre 100×100, a espessura da linha é sempre 1, e a linha é definida pela coordenadas x e y do ponto inicial e do ponto final em relação ao canto superior esquerdo do papel.

Vamos tentar ser um compilador. Agora pare, pegue um papel e uma caneta e tente gerar uma imagem compilando o seguinte código.

Paper 0
Pen 100
Line 0 50 100 50

Você desenhou uma linha preta bem no meio atravessando o papel de lado a lado? Parabéns! Você acaba de se tornar um compilador.

Resultado compilado.

Como funciona um compilador?

Vamos dar uma olhada no que acabou de acontecer na nossa cabeça ao funcionar como um compilador.

1. Análise Léxica (gerando tokens)

Primeira coisa que nós fizemos foi separar cada palavra (o que chamamos de tokens) baseados nos espaços entre elas. Enquanto estávamos separando as palavras, nós também classificamos cada token em tipos primitivos como “palavra” (word) e “número” (number).

Análise Léxica

2. Parsing (Análise Sintática)

Uma vez que um bloco de texto é dividido em tokens, nós passamos por cada um deles e tentamos encontrar uma relação entre eles.
Nesse caso, nós agrupamos números associados com palavras de comando.
Fazendo isso, nós começamos a estruturar o código.

Parseando

3. Transformação

Uma vez que analisamos a sintaxe, nós transformamos a estrutura em algo mais apropriado pra atingir o resultado final. Nesse caso, nós vamos desenhar uma imagem, então transformamos o código em um passo-a-passo para humanos.

Transformação

4. Geração de Código

Por último, nós compilamos o resultado em um desenho. Nessa etapa nós apenas seguimos as instruções que criamos no passo anterior.

Geração de código

E é isso que um compilador faz!

O desenho que fizemos é o resultado da compilação (como um arquivo .exe quando você compilado código C). Nós podemos passar esse desenho para qualquer pessoa ou device (scanner, câmera, etc) para “rodar” e qualquer pessoa (ou device) vai ver uma linha preta no meio do papel.


Vamos fazer um compilador

Agora que você já sabe como um compilador funciona, vamos criar um em JavaScript.

1. Função ‘Lexer’

Assim como a gente pode dividir a frase em português “Eu tenho uma caneta” em [Eu, tenho, uma, caneta], o analisador léxico divide o código em pedaços menores que tenham significado (tokens). No DBN, cada token é delimitado por espaços e classificados como “word” ou “number”.

input: "Paper 100"
output:[
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]

2. Função ‘Parser’

A função parser vai passar por cada token, encontrar informação sintática e vai gerar um objeto chamado AST (Abstract Syntax Tree). Você pode pensar no AST como sendo um mapa🗺 para nosso código—uma maneira de entender como um pedaço de código é estruturado.

No nosso código existem dois tipos de sintaxes: “NumberLiteral” e “Call Expression”. NumberLiteral significa que o valor é um número. Ele é utilizado como parâmetro de uma CallExpression.

input: [
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]
output: {
"type": "Drawing",
"body": [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{ "type": "NumberLiteral", "value": "100" }]
}]
}

3. Função ‘Transformer’

A AST que nós criamos no passo anterior descreve muito bem o que está acontecendo no código, mas não é útil para criar um SVG.
Por exemplo: “Paper” é um conceito que só existe no padrão DBN. No SVG, nós temos que usar o elemento <rect> para representar um “Paper”. A função ‘transformer’ converte AST pra outro AST que tem mais a ver com o SVG.

input: {
"type": "Drawing",
"body": [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{ "type": "NumberLiteral", "value": "100" }]
}]
}
output: {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}

4. Função “Generator”

Sendo a última etapa desse compilador, a função ‘generator’ gera um código SVG baseada no novo AST que criamos no passo anterior.

input: {
"tag": "svg",
"attr": {
"width": 100,
"height": 100,
"viewBox": "0 0 100 100",
"xmlns": "http://www.w3.org/2000/svg",
"version": "1.1"
},
"body": [{
"tag": "rect",
"attr": {
"x": 0,
"y": 0,
"width": 100,
"height": 100,
"fill": "rgb(0%, 0%, 0%)"
}
}]
}
output:
<svg width="100" height="100" viewBox="0 0 100 100" version="1.1" xmlns="http://www.w3.org/2000/svg">
<rect x="0" y="0" width="100" height="100" fill="rgb(0%, 0%, 0%)">
</rect>
</svg>

5. Juntando tudo pra criar o compilador

Vamos chamá-lo de “compilador SBN” (compilador SVG by numbers). Nós vamos criar um objeto sbn através dos métodos ‘lexer’, ‘parser’, ‘transformer’ e ‘generator’. E então, adicionar um método ‘compile’ que chama todos os outros quatro métodos em cadeia.

Nós podemos agora passar uma string com o código para o método ‘compile’ e receber o SVG como retorno.

Eu fiz um demo interativo que mostra o resultado de cada etapa do compilador. O código pro compilador SBN está postado no github. Eu estou adicionando algumas features nele. Se você quiser conferir o compilador básico que a gente fez nesse post, por favor veja o ‘simple branch’ no github.

https://kosamari.github.io/sbn/

Um compilador não deveria usar recursão, varredura, etc?

Sim, essas são técnicas excelentes para construir um compilador. Mas isso não significa que você tenha que optar por esse caminho logo no começo.

Eu comecei a fazer um compilador para uma pequena parte da linguagem de programação DBN, uma parte bem limitada. Desde então, eu aumentei o escopo e estou planejando adicionar outros recursos como variáveis, blocos e loops ao compilador. Seria muito bom utilizar as técnicas mencionadas acima nessa etapa, mas você não precisa disso pra começar.

Escrever um compilador é sensacional

O que você pode fazer escrevendo seu próprio compilador? Talvez você queira criar uma nova linguagem parecida com JavaScript em Português… o que você acha de um PortuguêsScript?

// PTS (PortuguêsScript)
função () {
se(verdadeiro) {
retorne «Olá!»
}
}

Tem uma galera que fez uma linguagem de programação com Emojis (Emojicode) e com imagens coloridas (Piet programming language). As possibilidades são infinitas!

Aprendizados ao criar um compilador

Criar um compilador foi divertido mas, o mais importante, isso me ensinou muito sobre desenvolvimento de software. Aqui estão algumas coisas que eu aprendi fazendo meu compilador:

Como eu imagino um compilador depois de ter feio um

1. Tá tudo certo em não saber algumas coisas

Assim como nosso analisador léxico, você não precisa saber tudo desde o começo. Se você realmente não entende alguma coisa do código ou de uma tecnologia, é tranquilo simplesmente dizer “Tem esse negócio e eu entendo só isso” e seguir em frente pra próxima etapa. Não se estresse com isso, uma hora ou outra você vai acabar aprendendo.

2. Não seja um babaca nas mensagens de erro

O trabalho do ‘Parser’ é seguir regras e conferir se as coisas estão escritas de acordo com aquelas regras. Sendo assim, muitas vezes, erros vão aparecer. E quando eles aparecem, tente retornar mensagens úteis e amigáveis. É muito fácil dizer “Isso não funciona assim” (como no JavaScript: “ILLEGAl Token” ou “undefined is not a function”) mas, ao invés disso, tente ao máximo dizer o que deveria ser feito.

Isso também se aplica a comunicação da equipe. Quando alguém está enroscado em um problema, ao invés de dizer “é mesmo, isso aí não funciona” você poderia falar algo como “eu procuraria no Google por ____ e ____.” ou “eu recomendo ler essa página da documentação.” Você não precisa fazer o trabalho pelos outros, mas você pode, certamente, ajudar eles a fazer um trabalho melhor e mais rápido contribuindo com uma ajudinha.

Elm é uma linguagem de programação que abraçou esse método. Eles usam “Maybe you want to try this?” (Talvez você queira tentar isso?) nas mensagens de erro.

3. Contexto é tudo

Finalmente, assim como nossa função ‘transformer’ transformou um tipo de AST em outro mais adequado, tudo está relacionado ao contexto.

Não existe uma maneira perfeita de fazer as coisas. Então não fique fazendo coisas só porque todo mundo faz ou porque foi assim que você fez da outra vez. Pense sobre o contexto, primeiro. Algumas coisas que funcionam para uma pessoa podem ser um desastre para outra.

Mais uma coisa, reconheça o trabalho desses ‘transformers’. Talvez você tenha bons ‘transformers’ no seu time—pessoas que são muito boas em preencher lacunas. Talvez o trabalho feito por esses ‘transformers’ não gere um código diretamente, mas é um trabalho importantíssimo para se produzir produtos de qualidade.


Espero que você tenha gostado desse post e que eu tenha te convencido que construir e ser um compilador é algo sensacional!

Esse artigo é um trecho retirado de uma palestra que eu dei na JSConf Colombia 2016 em Medelín, Colômbia. Se você quer saber mais sobre a palestra, confira os slides aqui.


Nota do tradutor: sugestões e críticas são bem vindas nos comentários!