Sé el compilador — haz un compilador con Javascript
Éste articulo es una traducción del original en inglés escrito por Mariko Kosaka.
https://medium.com/@kosamari/how-to-be-a-compiler-make-a-compiler-with-javascript-4a8a13d473b4
La licencia de ésta publicación es CC BY-NC-SA 4.0 license.
Un hermoso Domingo en Brooklyn, encontré un libro “Design by Numbers” escrito por John Maeda en una librería. El libro narra instrucciones paso por paso de un lenguaje de programación llamado DBN — un lenguaje hecho a finales de los noventas en MIT Media Lab, cuyo objetivo es introducir conceptos de programación de forma visual.
Inmediatamente pensé que hacer gráficas SVG a partir de DBN y poder verlas desde el navegador sería un proyecto muy interesante, en lugar de instalar el ambiente de Java para ejecutar el código original de DBN.
Entendí que necesitaría crear un compilador DBN a SVG, y así comienza mi búsqueda para crear un compilador. “Hacer un compilador” suena a algo de Ciencias de la Computación… pero nunca he podido transversar nodos en las entrevistas de código, podré hacer un compilador?
Comencemos por ser el compilador.
El compilador es un mecanismo que a partir de pedazos de código los convierte en algo útil para la máquina.Compilemos entonces algo simple en DBN en un dibujo físico.
Hay tres comandos disponibles en DBN, “Paper” nos define el color de el papel, “Pen” nos define el color de la pluma, y “Line” nos dibuja una línea.Cuando definimos como 100 el parámetro de color esto significa que es 100% negro o en rgb(0%,0%,0%) en CSS.La imágenes que produce código DBN son siempre en escala de grises.En DBN, un papel siempre es 100×100, el grosor de las líneas siempre son 1 y una línea se define por sus coordenadas “x, y” de inicio y coordenadas “x, y” donde termina; tomando en cuenta que se numera a partir de la esquina izquierda inferior.
Vamos a imaginar que somos un compilador.Te recomiendo que tomes papel y lápiz e intentes compilar el siguiente código como un dibujo.
Paper 0
Pen 100
Line 0 50 100 50Acaso, ¿dibujaste una línea negra, justo a la mitad de izquierda a derecha?¡Felicidades! Ya eres un compilador.
¿Cómo funciona un compilador?
Veamos qué pasó por nuestra mente mientras éramos un compilador.
1.Análisis léxico (tokenization)
Comenzamos separando cada una de las palabras clave o tokens.Al mismo tiempo asignamos tipos primitivos a cada token, como “palabra” o “número”.
2. Análisis Sintáctico (Parsing)
Una vez que separamos un pedazo de texto en tokens, vamos a encontrar alguna relación entre cada token.
En este caso, agrupamos dependiendo de cada comando.
Podemos apreciar que al agrupar damos una mejor estructura a el código.
3. Transformación
Una vez que analizamos la sintaxis mediante el “parsing”, transformamos la estructura en algo más entendible para el resultado final.Como el resultado final en éste caso es dibujar un dibujo, vamos a transformar en instrucciones paso a paso para humanos.
4. Generación de Código
Por último, vamos a compilar el resultado dibujando.Simplemente seguimos las instrucciones en “lenguaje humano” y hacemos el dibujo.
Y, ¡esto es lo que hace un compilador!
El dibujo sería equivalente a el resultado compilado (por ejemplo un archivo .exe cuando compilas código C en Windows).Podemos dar éste dibujo a cualesquiera que puedan “usarlo” (un escaner, una camara etc.) y todos “verán” que es una línea.
¡Manos a la obra!
Ahora que sabemos como funciona un compilador, hagamos uno en Javascript.Éste compilador convertirá código DBN en código SVG.
1. Función de análisis léxico.
Tal y como podemos separar una oración en Español “Tengo una pluma” a [Tengo, una, pluma],los analizadores léxicos separan una cadena de texto en pequeños trozos (tokens).
En DBN, cada token es delimitado por caracteres blancos (espacios, retorno de carro etc.), y a su vez son clasificados como “palabra” o“número”.
input: "Paper 100"
output:[
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]2. Función de análisis sintáctico
Los “parsers” toman cada token, encuentran información sintáctica, y construyen un objeto llamado “Árbol de Sintaxis Abstracta”. Imagina que un ASA es como un mapa 🗺 para nuestro código — una forma de entender cómo es la estructura de cada pedazo de código.
En nuestro código, hay dos tipos distintos “Literal Numérico” y “Expresión de Llamado de función”.El “Literal Numérico” es un número y es utilizado como argumentos para la “Expresión de Llamado de función”.
input: [
{ type: "word", value: "Paper" }, { type: "number", value: 100 }
]
output: {
"type": "Drawing",
"body": [{
"type": "CallExpression",
"name": "Paper",
"arguments": [{ "type": "NumberLiteral", "value": "100" }]
}]
}3. Función de transformación
El ASA que creamos en el paso anterior nos ayuda bastante describiendo qué pasa en el código, sin embargo no suficiente para generar un archivo SVG. Por ejemplo, “Paper” es un concepto que únicamente existe en DBN, en SVG utilizaríamos el elemento <rect> para representar un “papel o lienzo”.La función de transformación, convierte un ASA y a algo mas amigable para el formato 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. Función generadora
Como último paso para este compilador, la función generadora crea código SVG basado en el Árbol de Sintaxis Abstracta que se obtuvo en el paso 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. ¡A juntar todo para hacer el compilador!
Llamemos el compilador “el compilador sbn” (compilador SVG mediante números por sus siglas en inglés).Creamos un objeto sbn con el lexer, parser con los métodos de transformador y generador.Entonces agregamos el método “compile” que llama los 4 en cadena.
Podemos ahora pasarle código a el método “compile” y obtener SVG como salida.
Hice un demo interactivo que muestra el resultado de cada paso de este compilador.El código se encuentra en github. Estoy agregando más funcionalidades a el compilador.Si gustas puedes checar el compilador que hicimos en este articulo, revisa la rama simple.
¿Debe un compilador usar recursion y técnicas de transveral etc.?
Sí, la mayoría esas técnicas (recursión, transversal etc.) son muy útiles al momento de crear un compilador, sin embargo eso no significa que debas usarlas para tener un compilador funcional.
Comencé haciendo un compilador de un subconjunto de el lenguaje DBN, un conjunto muy pequeño y limitado. Desde entonces, he comenzado a añadir funcionalidades tales como variables, bloques de código, ciclos etc. al compilador. Es buena idea si piensas tener un lenguaje más robusto, sin embargo no son requerimientos para comenzar algo sencillo.
!Hacer un compilador es genial!
¿Qué puedo hacer con mi propio compilador? Quizá puedes hacer un nuevo lenguaje similar a Javascript en Español — español script?
// ES (español script)
función () {
si (verdadero) {
return «¡Hola!»
}
}Alguien hizo un lenguaje de programación con puros Emojis (Emojicode), las posibilidades son infinitas.
Lo que aprendí al hacer un compilador.
Hacer un compilador desde cero fue divertido, sin embargo lo más importante es que me enseñó mucho sobre el desarrollo de software.He aqui algunas cosas que aprendí al hacer mi mini compilador.
1. Esta bien tener cosas que desconoces.
Tal y como un analizador léxico, no necesitas saber todo de inicio.Si no entiendes un pedazo de código o alguna tecnología, está bien decir “Hay algo por ahi, pero no sé mucho al respecto” y seguir a el siguiente paso.No te preocupes mucho, eventualmente lo entenderás.
2. No uses mensajes de error poco descriptivos.
El rol de el “parser” es seguir la reglas y revisar que las cosas son tal y como se describen.Cuando ocurran errores trata de enviar mensajes que sean útiles y amigables.Es fácil decir “No, eso no funciona como crees” (Por ejemplo errores tales como “ILLEGAL Token” o “undefined is not a function” que son comunes en Javascript) en lugar de eso trata de indicar a el usuario qué debe de corregirse.
Eso también se puede aplicar al momento de comunicarte con tu equipo; cuando alguien te pregunta referente a un problema, quizá en lugar de decirle “eso no es así” puedes apuntar algo más útil como “Yo trataría de buscar la solución de tal o cual forma”, o “te recomiendo leer la documentación en tal o cual parte”.No necesitas hacer el trabajo por ellos, sin embargo puedes apuntar a recursos que son de ayuda.
Elm es un lenguaje de programación que utiliza mucho ésa estrategia.Ellos tratan de sugerirte soluciones en los mensajes de error.
3. Todo depende del contexto
Finalmente, tal como nuestra función de transformación convierte un tipo de Árbol de Sintaxis Abstracta en algo más util para la máquina, todo depende del contexto.
No hay forma de hacer que todo salga a la perfección, entonces no hagas cosas por ser populares o porque estas acostumbrado a hacerlas de ésa forma; piensa en el contexto.Algunas cosas funcionan para algunos y para otros necesitas ser de otra forma.
Igualmente, reconoce a las “funciones transformadoras”, quizá conozcas a personas en tu equipo que puedan traducir las cosas para facilitarles el trabajo a otros.Aquellos “catalizadores” quizá no contribuyan directamente al código, sin embargo son muy importantes al momento de producir código de calidad.
Espero que hayas disfrutado de ésta publicación, espero que te haya convencido lo maravilloso que es hacer y ser un compilador.
