Seja* um Compilador — Crie um compilador com JavaScript

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


Este artigo é uma tradução do texto original em inglês escrito por Mariko Kosaka.
https://medium.com/@kosamari/how-to-be-a-compiler-make-a-compiler-with-javascript-4a8a13d473b4

A licença de esta publicação é CC BY-NC-SA 4.0 license.


Em um ensolarado domingo em Bushwick, Brooklyn. Eu encontrei um livro chamado “Design by Numbers” escrito por John Maeda em uma livraria local. Era um passo-a-passo sobre DBN programming language — uma linguagem de programação criada no final dos anos 90 no MIT Media Lab, projetada para introduzir conceitos de programação computacional de uma forma visual.

Exemplo de implementação de DNB http://dbn.media.mit.edu/introduction.html

Eu imediatamente imaginei que fazer um SVG partindo de DBN e apresentar isso em um navegador seria um projeto muito mais interessante para 2016 do que instalar o ambiente do Java para rodar o código original de DBN.

Percebi então que precisaria escrever um compilador de DBN para SVG, logo minha jornada de criação de compiladores havia começado. “Criar compiladores” a primeiro momento parece algo com muita Ciência da Computação envolvida… Mas nunca me questionei, será que consigo fazer um compilador?

Como eu imagino o meu compilador, onde o código vai para ser punido. Se o código é ruim, é capturado em uma mensagem de erro para sempre.

Primeiro, vamos tentar ser um compilador

Compilador é um mecanismo que trata um trecho de código e o transforma em outra coisa. Vamos compilar um simples código DBN em um desenho.

Existem 3 comandos em um código DBN, “Paper” define a cor do papel que será utilizado, “Pen” diz a cor da caneta e “Line” desenha uma linha. Passado 100 como parâmetro de cor, significa o mesmo que dizer que estamos utilizando 100% de preto ou rgb(0, 0, 0) no CSS. A imagem produzida no DBN sempre é em escala de cinza. No DBN, um papel sempre terá o tamanho de 100×100, a espessura das linhas sempre serão de 1 e a linha é definida pelas coordenadas X e Y do ponto inicial, seguidas por X e Y do ponto final, partindo sempre do ponto mais baixo à esquerda.

Vamos tentar ser um compilador nós mesmos. Pare aqui, pegue um pedaço de papel, uma caneta e tente “compilar” o código a seguir num desenho.

Paper 0
Pen 100
Line 0 50 100 50

Você desenhou uma linha preta no meio do papel cruzando-o do lado esquerdo para o direito? Parabéns! Você acaba de se tornar um compilador.

Resultado esperado

Como um compilador funciona?

Vamos ver o que aconteceu em nossas cabeças como compiladores.

1. Análise Léxica (tokenização)

A primeira coisa que fizemos foi separar cada palavra-chave (token) por espaços. Enquanto nós separamos as palavras, nós atribuímos a cada uma um tipo primitivo, como “palavra” ou “número”.

Análise Léxica

2. Análise Sintática

Depois de um trecho de código ser separado em tokens, nós passamos por cada um para tentar encontrar uma relação entre eles. Neste caso, nós agrupamos números associados a cada palavra. Fazendo isso nós começamos a enxergar a estrutura do código.

Análise Sintática

3. Transformação

Assim que a análise sintática for efetuada, nós transformamos a estrutura com algo mais parecido com o resultado final. No nosso exemplo, nós vamos desenhar uma imagem, então precisamos transformar num passo a passo para um humano.

Transformação

4. Geração de código

Por último, nós criamos o resultado compilado, um desenho. Neste ponto, nós apenas seguimos as instruções que fizemos nós passos anteriores.

E isso que um compilador faz!

O desenho que fizemos é o resultado compilado ( como um arquivo .exe quando você compila um código C). Nós podemos passar o desenho para qualquer um e qualquer dispositivo ( scanner, câmera etc) para “rodar” e todos conseguiram ver uma linha preta no meio da folha.


Vamos fazer um compilador

Agora que sabemos como um compilador funciona, vamos criar um em JavaScript. Esse compilador receberá códigos DBN e transformará-los em códigos SVG.

1. Função de análise léxica

Assim como no Português nós podemos dividir uma frase como “Eu tenho uma caneta” em [Eu, tenho, uma, caneta], nossa função de análise léxica dividirá uma string em pedaços menores ( tokens ). In DBN, cada token é delimitado por espaços, e classificado como “word” (palavra) ou “number” (número).

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

2. Função de análise sintática

Nossa função passa por cada token, encontra informação sintática e constrói um objeto chamado de AST (Abstract Syntax Tree). Você pode assemelhar o AST como um mapa 🗺 para nosso código — uma maneira de entender como cada peça do código é estruturada.

No nosso código, existem 2 tipos de sintaxe “NumberLiteral” e “CallExpression”. NumberLiteral significa que o valor é um número. E é usado como argumentos para CallExpression.

https://gist.github.com/kosamari/041282ca510f9d5e699dc4c419688422/raw/7c4826664c099872e6388f21104ae64bedefdd7d/parser.js

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 de transformação

O AST que criamos no passo anterior descreve bem o que acontece no código, mas não é útil para criar um arquivo SVG. Por exemplo. “Paper” é um conceito que existe apenas no paradigma DBN. In SVG, nós devemos usar o elemento <rect> para representar um papel. A nossa função de transformação converte AST para outro AST no fomato SVG.

https://gist.githubusercontent.com/kosamari/0dd2a76984e3375c11462276cdf014e1/raw/c448f122121d3af85f983794920164adb4ea2d59/transformer.js

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 geradora

Como passo final desse compilador, nosso gerador cria SVG baseado em um novo AST que fizemos no passo 3.

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. Colocando tudo junto como um compilador

Vamos chamar esse compilador de “sbn compiler” (SVG by numbers compiler). Nós criamos um objeto sbn com um Analisador Léxico, Sintático, um transformador e o gerador. Então adicionamos um método “compile” para chamar os outros 4 em cadeia.

Nós agora podemos passar uma string de códigos para ser compilada e retornar um SVG.

https://gist.github.com/kosamari/6c610165c0f48c699679bc5a8bab6327/raw/a2709b29fe44e66453d5872ab0a9698c15553aac/compiler.js

Eu criei uma demonstração que mostra o resultado de cada passo do nosso compilador. O código do sbn compiler está no github. E estou adicionando algumas melhorias no momento. Se você quiser ver o código básico usado nesse artigo, por favor veja o simple branch.

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

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

Sim, essas são técnicas maravilhosas de construir um compilador, mas não significa que você precisa usa-las de saída.

Eu comecei criando um compilador para um pequeno trecho da linguagem DBN, com bastante limitações. Desde então, eu expandi o escopo e agora estou planejando adicionar melhorias como variáveis, blocos de código e loops para este compilador. Seria uma ideia interessante usar essas técnicas neste momento, mas esse não era um requisito para iniciar o projeto.

Escrever um compilador é maravilhoso

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

// PT(portuguese script)
funcao () {
sim (verdadeiro) {
return «Olá!»
}
}

Existem pessoas que criaram algumas linguagens tais como o Emoji (Emojicode) e o colored image (Piet programming language). As possibilidades são infinitas!


Ensinamentos sobre construir um compilador

Construir um compilador foi divertido, mas mais importante, me ensinou muito sobre desenvolvimento de softwares. Aqui estão algumas coisas que aprendi.

Como imagino um compilador depois de ter feito um

1. É normal encontrar coisas que não parecem familiares.

Assim como nosso analisador léxico, você não precisa saber tudo do começo. Se você não entende muito bem um trecho de código ou alguma tecnologia, é normal apenas dizer “Aqui está algo, e eu sei apenas isso” e passar o resto adiante para o próximo passo. Não se estresse com isso, você chegará lá eventualmente.

2. Não seja um idiota com péssimas mensagens de erro.

O papel do analisador sintático é seguir regras e verificar se tudo está escrito de acordo com essas regras. Então, muitas das vezes, erros acontecem. E quando acontecer, tente enviar uma mensagem convidativa e que realmente leve um significado. É muito fácil dizer “Isso não funciona” (como os erros de JavaScript “ILLEGAL Token” ou “undefined is not a function”) porém, tente dizer ao usuário o que aconteceu e o que ele pode fazer para resolver o problema.

Isso também se aplica a comunicação do time. Quando alguém está preso com alguma questão, ao invés de dizer “Sim, realmente não funciona” talvez você possa começar a dizer “Eu buscaria as palavras como ___ e ___.” ou “Eu recomendo ler essa documentação.” Você não precisa fazer o trabalho deles, mas você com certeza pode ajudar eles a fazer um trabalho mais rápido e melhor sendo um pouco prestativo.

Elm é uma linguagem de programação que abraça esse método. Eles sempre colocam alternativas como “Talvez você possa tentar isso?” em suas mensagens de erro.

3. Contexto é tudo

Finalmente, como nosso transformador gerou um tipo de AST para outro que se encaixava melhor no resultado final, tudo é contexto especifico.

Não existe uma maneira perfeita de fazer as coisas. Então não deixe de fazer coisas porque é popular ou você já fez isso antes, pense no contexto primeiro. Coisas que funcionam para alguns podem ser um desastre para outros.

Também aproveite o trabalho que estes tranformadores fazem. Você pode conhecer um no seu time — alguém que seja muito bom em encurtar caminhos. O trabalho feito por transformadores pode não criar trechos de código diretamente, mas claramente faz um trabalho muito importante na produção de um produto de qualidade.


Espero que gostem do artigo e espero ter convencido como é incrível escrever & ser um compilador!

Este é um resumo da palestra que eu ministrei na JSConf Colombia 2016 em Medellin, Colombia. Se quiser saber mais da palestra, dê uma olhada aqui.