Desmistificando Interpretadores – Parte 2
Antes começar a ler a parte 2 da série “Desmistificando Interpretadores” recomendamos ler o artigo: Desmistificando Interpretadores – Parte 1! Mas se você já leu esse conteúdo incrível, bora!
Análise Sintática
Essa etapa também é conhecida como parsing, e é a segunda fase do nosso interpretador. É aqui que vamos analisar os tokens produzidos no lexer, que vimos na primeira parte desta série, para construir uma árvore sintática abstrata (ou como é mais conhecido, AST, do inglês Abstract Syntax Tree). Cada interpretador tem seus objetivos nessa fase, vai depender de cada propósito, mas no geral, a maioria dos interpretadores usa essa fase para gerar árvores hierárquicas que facilitam uma análise posterior tanto humana quanto por uma máquina. Isso acontece por meio de patterns como o Visitor Pattern, tópico que iremos abordar mais pra frente.
Uma particularidade das expressões que o torna mais complexo de se resolver, é a precedência dos operadores. Para nós já é algo intuitivo, que aprendemos ainda na escola. Observe a expressão abaixo:
4 + 3 * 2
Seu cérebro já sabe que você precisa resolver primeiro a multiplicação, para depois resolver a soma. E você obtém o resultado com facilidade. Nosso parser também vai precisar saber disso, e a melhor forma de se representar precedência para ele é usando árvores:
Ao desmontar nossa expressão e montar nossa árvore, começamos pelos operadores de menor precedência (no caso, o +), para que os operadores de maior precedência (*) fiquem pro final. Pois é de baixo para cima que iremos resolver nossa árvore:
Recursive Descent Parser
Certo, parece simples, né? Isso pois o exemplo é simples, mas e se misturarmos operadores unários? Parênteses (subexpressões)? Como transformar tokens em uma árvore considerando ordens de precedência diferentes? Dentre diversas técnicas e algoritmos para lidar com este problema de parsing, existe o recursive descent, que é um dos mais conhecidos por ser ao mesmo tempo simples e eficiente. E é ele que vou usar para construir nosso parser.
É chamado recursive descent pois consiste em várias funções recursivas que vão em uma ordem descendente. Essas funções representam regras de uma gramática (aqui vamos chamar de grammar, em inglês mesmo), então para cada regra da nossa grammar existe uma função dedicada à resolvê-lo dentro do nosso parser.
Grammar
O conceito de grammars é um dos pilares desta etapa (e bastante poderoso). Isto porque os grammars conseguem definir operações a partir dos tokens, ao mesmo tempo em que definem uma ordem de prioridade (junto à recursividade), resolvendo nosso problema de precedência.
Para entender melhor, imagine que um grammar é um conjunto de regras dentro da nossa expressão. Por exemplo, a multiplicação é um regra dentro da nossa grammar representada pelos tokens de “Number”, “Star” e “Number”, nessa sequência. Sem isso, não existe uma multiplicação pois eu não consigo multiplicar nada sem ter dois produtos (Number), e no caso o “Star” para me indicar que eu preciso fazer a multiplicação.
Seguindo a mesma lógica, nossa regra de adição seria a junção dos tokens “Number”, “Star” e “Number”, certo? Bom, a ideia é por aí, mas não é bem assim. Dentro do recursive parser nós definimos o grammar pela ordem inversa de precedência – adição vem antes da multiplicação aqui, pelo mesmo motivo que começamos a quebrar a árvore pelo operador + no começo desse tópico –, só que ao definirmos uma regra de baixa precedência, usamos a próxima regra (de maior precedência) como valor da definição, como no exemplo abaixo:
adição = multiplicação “Plus” multiplicação
multiplicação = número “Star” número
número = “Number”
Porém, nossa expressão pode não ter uma multiplicação, então como ele vai resolver a adição? Bom, para isso, vamos adaptar nossa regra de multiplicação para retornar um “ou”.
multiplicação = (número “Star” número) OU número
Dessa forma, se não existir uma sequência de número, “Star” e número, ele vai retornar apenas o número, pois não temos uma multiplicação. O mesmo faremos na adição, porque podemos não ter uma adição na nossa expressão. Lembre-se, um simples número (5) já é uma expressão válida.
adição = (multiplicação “Plus” multiplicação) OU multiplicação
multiplicação = (número “Star” número) OU número
número = “Number”
Essa definição faz com que quando formos criar o algoritmo, ao procurar por uma adição, ele vai procurar pelas multiplicações dentro da recursividade. Lembre-se que cada uma dessas regras se tornarão funções no nosso parser. Então conforme o exemplo acima teríamos algo como add() e mul(). A adição procuraria por multiplicações para serem resolvidas antes (pois dentro de uma função recursiva, as primeiras execuções usam o valor das últimas execuções, fazendo com que a multiplicação fosse resolvida antes da adição).
Um pouco confuso, né? Mas vamos chegar lá. Existe uma notação para definir as grammars e ela vai ajudar a facilitar o entendimento. Elas lembram um pouco as expressões regulares – mas não são tão complexas quanto elas.
Aqui vai o mesmo exemplo usado acima, em grammar notation:
expr → add
add → mul (PLUS mul)*
mul → num (STAR num)*
num → NUMBER
As regras quando usadas nas definições são chamadas de nonterminals, pois elas não são terminais, elas tem que ser executadas dentro da recursividade até virarem os terminals que são valores finais (nossos tokens são terminals). Em mul (PLUS mul)*, os mul são os nonterminals, enquanto o PLUS é um terminal.
Os nonterminals são representados em minúsculo (expr, add, mul, num), enquanto os terminals, em maiúsculo (PLUS, STAR, NUMBER).
Assim como nas expressões regulares, os parênteses servem para agrupamento, enquanto o asterisco serve para dizer que aquele valor (ou agrupamento, no nosso caso) poderá se repetir 0 ou mais vezes. Ou seja, na regra add → mul (PLUS mul)* eu estou dizendo que o add vai ter um produto que tem mul e pode ser que tenha uma repetição infinita de PLUS mul.
O parser
Eu sei muito bem que só pela teoria, as coisas ficam difíceis de se entender. Então, para simplificar, vamos começar a codar nosso parser partindo do pressuposto que só temos adição e multiplicação e depois vamos adicionando os outros operadores.
const parser = tokens => {
let current = 0
// ...
}
Começamos com a mesma premissa do lexer. Vamos usar um ponteiro para percorrer os tokens, mas ao contrário do lexer, vamos criar algumas funções de suporte para que nosso parser não fique tão confuso:
const peek = () => tokens[current]
const prev = () => tokens[current - 1]
const match = (type) => {
if (peek().type === type) {
current++;
return true;
}
return false;
}
Por partes: o peek e o prev são simples, eles nos trazem o token atual e o token anterior, respectivamente. Já o matché mais vai nos ajudar a identificar os terminals por tipos a partir do nosso ponteiro. Então se precisar saber se o ponteiro está num token de tipo Number é só usar match(‘Number’), se a resposta for sim, ele vai retornar true e já avançar o ponteiro, se não, vai retornar false.
A partir daqui já podemos construir nossas funções recursivas a partir das regras do nosso grammar. Por enquanto não vamos montar um AST, mas apenas resolver a expressão e obter o resultado final.
Nossa regra de expr é realmente tão simples como a notação demonstra: ela retorna a execução de add!
// expr → add
const expr = () => {
return add()
}
A regra de add vai retornar um resultado que começa por mul, e enquanto ele encontrar o token PLUS, vai somar ao próximo mul. O while aqui representa muito bem o asterisco da notação.
// add → mul (PLUS mul)*
const add = () => {
// mul
let result = mul()
// (PLUS mul)*
while(match('Plus')) {
result = result + mul() // se ele encontrar o token "Plus" então vai somar ao `mul()` seguinte
}
return result
}
A regra de mul é idêntica ao add, mas agora ele vai usar o num com o operador STAR.
// mul → num (STAR num)*
const mul = () => {
// num
let result = num()
// (STAR num)*
while(match('Star')) {
result = result * num()
}
return result
}
.
Finalmente a nossa última regra. Como NUMBER é um terminal, não podemos fazer o que fizemos na primeira regra com add, que é um nonterminal e representa apenas uma execução. Aqui temos que garantir que ele seja o token “Number”, e retornar seu value, terminal de fato. E como é a última regra do nosso parser, se ele chegou aqui e não é um “Number”, então temos um erro de sintaxe pois não foi capturada por nenhuma das nossas regras gramaticais (por exemplo 5 + * 3). Para isso vamos lançar um SyntaxError.
// num → NUMBER
const num = () => {
// NUMBER
if(match('Number')) {
return prev().value
}
throw SyntaxError(`Unexpected ${peek().type} token`)
}
No final, o parser retorna a execução da primeira regra, e a recursividade faz todo o resto:
const parser = tokens => {
let current = 0
const peek = () => tokens[current]
const prev = () => tokens[current - 1]
const match = type => {
if (peek().type === type) {
current++
return true
}
return false
}
const expr = () => {
return add()
}
const add = () => {
let result = mul()
while (match('Plus')) {
result = result + mul()
}
return result
}
const mul = () => {
let result = num()
while (match('Star')) {
result = result * num()
}
return result
}
const num = () => {
if (match('Number')) {
return prev().value
}
throw new SyntaxError(`Unexpected ${peek().type} token`)
}
return expr()
}
Neste ponto você já tem um parser funcionando com precedência entre + e *!
Você pode ver o resultado parcial neste link: https://repl.it/@renatorib/parser-v1
***
No próximo post da série vamos continuar abordando o parser e usar a mesma ideia que aprendemos hoje para implementar outros tipos de operadores binários, como subtração e divisão, operadores unários como positivo e negativo, e subexpressões (os parênteses)!
