Desmistificando Interpretadores – Parte 1
Introdução
Antes de começar a escrever este artigo, meu conhecimento sobre linguagens se resumia em: “não faço a mínima ideia de como esse treco funciona”. E sempre que eu pesquisava para ter uma noção básica sentia que estava lendo grego, achava tudo mágico, místico. Então se você também não entende nada do assunto, sei exatamente como se sente.
Por isso mesmo, para tentar desmistificar o tema, iremos abordar tudo na prática. Vamos começar do ponto zero e, ao final deste artigo, teremos um interpretador funcional, rodando expressões matemáticas em javascript.
Não pretendo me aprofundar muito, até porque este é um conceito que existe há vários anos (literalmente desde o começo da programação), e existem centenas de milhares de termos técnicos, variações, algoritmos e abordagens. No entanto, o objetivo é que você passe do “não faço ideia de como isso funciona” para o “aaah, então é assim que funciona”, e não que você vire o ninja dos compiladores.
Interpretador vs. Compilador
Você deve ter notado que misturei os termos compilador e interpretador, o que pode ter dado um nó na cabeça. E sim, geralmente acontece essa confusão. Na verdade, eles são extremamente parecidos, o que difere é o resultado final. Ambos compartilham dos mesmos conceitos de construção de análises léxica, sintática, semântica, etc. A diferença é que no Interpretador, como o nome sugere, a linguagem vai ser interpretada no final. Ou seja, no nosso caso, o javascript vai decompor nosso input, traduzir de acordo com as regras gramaticais que fizermos, e ele mesmo executar os cálculos e retornar o resultado, tudo dentro do js. Será uma linguagem rodando dentro do javascript, assim como o javascript roda dentro do C. Os compiladores, por outro lado, têm um processo de gerar código, e é mais comum nas linguagens de baixo nível, como C, que compila para Assembly.
Análise Léxica
Essa é a primeira etapa do nosso interpretador, que também é conhecido como “tokenizer”, “scanner” ou apenas “lexer”. O objetivo desta etapa é extrair os tokens da nossa entrada. Esse é um processo importante para a “desambiguidade” das sintaxes das linguagens. É nessa etapa que se diferenciam que `==` é um token só (igualdade) e não dois tokens `=` (atribuição), por exemplo. No nosso caso, não teremos nenhum destes tokens citados pois iremos trabalhar apenas com expressões matemáticas (+, -, *, /, parênteses e números).
Token
Pense em um token como um pedaço “útil” da nossa entrada. Pode ser um número, um parênteses, um operador. Em linguagens mais complexas pode ser uma keyword, uma variável, entre outros. No começo temos apenas uma sequência de caracteres, que aparentemente não significam nada, mas no final aquele pedaço da string que tinha 1 e depois 0 era na verdade um token número de valor 10. No nosso interpretador iremos descartar todos os espaços vazios. Todos os outros caracteres farão parte do token, como no exemplo abaixo:
O trabalho do lexer é apenas a separação dos tokens, ele não se importa se a sintaxe estiver quebrada (por exemplo, se tem um parênteses sem fechar, ele não vai se importar). Os erros léxicos são, geralmente, um caractere desconhecido. Se eu rodar 1 % 1, ele não vai ter nenhum conhecimento do que é esse tal %, e aí sim, disparar um erro.Iremos representar um token como um objeto que possui as propriedades type e value (para os literals), dessa forma teremos uma lista de tokens parecida com isso:
[
{ type: 'Number', value: 2 },
{ type: 'Star' },
{ type: 'LeftParen' },
{ type: 'Number', value: 10 },
{ type: 'Plus' },
{ type: 'Number', value: 5 },
{ type: 'RightParen' },
{ type: 'End' },
]
O lexer
O algoritmo começa com o lexer percorrendo toda a string de entrada, char por char, e entender qual o momento para salvar o token ou continuar a análise.
const lexer = (input /*: string */) => {
let tokens = [] // onde serão guardados nossos tokens
let current = 0 // seta o ponteiro na index 0, ou seja, no início
while (current < input.length) { // continua a execução até que o ponteiro esteja no final do input
let char = input[current] // pega o char correspondente à posição do ponteiro
/**
* executa a lógica baseada no char encontrado
*/
current++ // avança o ponteiro para continuar a execução do while
}
}
Para entender melhor o ponteiro, explico: a string tem um comportamento bem parecido à um array no que se refere à indexes e iteração. Conseguimos acessar um caractere da string passando a posição dela. Dessa forma, a cada vez que o ponteiro é incrementado, conseguimos ler o próximo caracter da string e aplicar a lógica que desejamos.
const input = "2 * (10 + 5)" let current = 0; input[current] // input[0] -> '2' current++; input[current] // input[1] -> ' ' current++; input[current] // input[2] -> '*'
Ignorando espaços vazios
Os whitespaces são essenciais para escrevermos códigos legíveis, e em muitas vezes eles também tem seu papel sintático. No nosso caso, eles vão ser apenas ignorados. Então quando o nosso lexer encontrar um whitespace, ele vai apenas prosseguir:
if (char === " ") {
current++; // incrementa o current para que na próxima execução do while ele pegue o próximo char
continue; // para a execução atual do while e recomeça se necessário
}
Lidando com tokens de caracteres únicos
A maioria dos tokens que utilizaremos são de apenas um caractére (*, +, (, …), então eles são os mais simples de se parsear, pois não é necessário olhar os chars da frente, apenas o atual dentro da iteração:
if (char === "+") {
tokens.push({ type: "Plus" }); // adiciona o token "Plus" à nossa lista de tokens
current++; // incremente o current para que na próxima execução do while ele pegue o próximo char
continue; // para a execução atual do while e recomeça se necessário
}
Depois de repetir o processo com todos os outros tokens, teremos algo como:
if (char === " ") {
current++;
continue;
}
if (char === "+") {
tokens.push({ type: "Plus" });
current++;
continue;
}
if (char === "-") {
tokens.push({ type: "Minus" });
current++;
continue;
}
if (char === "*") {
tokens.push({ type: "Star" });
current++;
continue;
}
if (char === "/") {
tokens.push({ type: "Slash" });
current++;
continue;
}
if (char === "(") {
tokens.push({ type: "LeftParen" });
current++;
continue;
}
if (char === ")") {
tokens.push({ type: "RightParen" });
current++;
continue;
}
Lidando com tokens de múltiplos caracteres
Existem tokens formados por mais de um caractere. Na maioria das linguagens esse grupo forma maior parte dos tokens, porém, no nosso caso será apenas o token Number
10 + 1000 ⟶ [10] [+] [1000]
Para cobrir este cenário, a partir do momento que encontrarmos o primeiro caractere de número, iremos observar seus próximos caracteres e ir agrupando enquanto continuarem sendo números, e quando encontrarmos um caracter qualquer que não seja o que procuramos, cancelamos o processo e salvamos o token com o agrupamento final.
// vamos usar um regex simples para testar se o char é um dígito
if (/[0-9]/.test(char)) {
let value = '';
// enquanto o char for um número, adicionar no value e avança o ponteiro
while (/[0-9]/.test(char)) {
value += char;
current++;
char = input[current];
}
// quando quebrar o while, adicionamos o resultado final aos tokens
tokens.push({ type: "Number", value: parseInt(value) });
// dessa vez não vamos incrementar o ponteiro antes do continue pois ele
// já está em um ponto após o fim número por ter quebrado o while de agrupamento
continue;
}
Agora que cobrimos os cenários de todos os nossos tokens, qualquer outro caractere que apareça vai ser um que não está sendo tratado. Por isso, disparamos um erro.
while (current < input.length) {
// ...
throw new Error(`Unexpected char ${char}`)
}
No final de tudo, adicionamos um token para indicar o fim da nossa expressão e retornamos todos os tokens.
Temos o nosso lexer:
const lexer = input => {
let tokens = []
let current = 0
while (current < input.length) {
let char = input[current]
if (char === " ") {
current++
continue
}
if (char === "+") {
tokens.push({ type: "Plus" })
current++
continue
}
if (char === "-") {
tokens.push({ type: "Minus" })
current++
continue
}
if (char === "*") {
tokens.push({ type: "Star" })
current++
continue
}
if (char === "/") {
tokens.push({ type: "Slash" })
current++
continue
}
if (char === "(") {
tokens.push({ type: "LeftParen" })
current++
continue
}
if (char === ")") {
tokens.push({ type: "RightParen" })
current++
continue
}
if (/[0-9]/.test(char)) {
let value = ''
while (/[0-9]/.test(char)) {
value += char
current++
char = input[current]
}
tokens.push({ type: "Number", value: parseInt(value, 10) })
continue
}
throw new Error(`Unexpected char ${char}`)
}
tokens.push({ type: "End" })
return tokens
}
Agora o próximo passo é usar os tokens para construir nosso parser na etapa de análise sintática, onde aprenderemos sobre árvores, recursive descent parser, grammar e muitas outras coisas. Não perca a continuação da série!
