Pressione enter para ver os resultados ou esc para cancelar.

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:

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.

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.

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:

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:

Depois de repetir o processo com todos os outros tokens, teremos algo como:

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.

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.

No final de tudo, adicionamos um token para indicar o fim da nossa expressão e retornamos todos os tokens.

Temos o nosso lexer:

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!