No post anterior de “Desmistificando Interpretadores” aprendemos o que são os grammars e como funciona um recursive decent parser usando apenas as operações de adição e multiplicação. Agora que temos uma boa base, podemos continuar a implementar os próximos operadores.
Desmistificando Interpretadores – Parte 1
Desmistificando Interpretadores – Parte 2
Subtração e Divisão
Como disse antes, usamos apenas adição e multiplicação para simplificar, mas chegou a hora de adicionar novos operadores. Aqui vamos entrar em uma regra de precedência nova para nós. Diferentemente da adição e multiplicação que possuem precedências entre si, a adição e subtração não possuem. Elas são executadas na ordem em que vêm. Assim como a multiplicação e divisão. Por isso, não podemos separar ambas em regras diferentes, pois regras diferentes representam precedências diferentes.
Para isso, vamos usar um simples “ou” dentro do nosso token, para que ele dê match com qualquer um dois dois:
expr → add - add → mul (PLUS mul)* + add → mul ((PLUS | MINUS) mul)* - mul → num (STAR num)* + mul → num ((STAR | SLASH) num)* num → NUMBER
Certo, agora que adicionados ao nosso grammar, vamos atualizar nosso parser. Como mexemos apenas nas regras de add e mul, é apenas nessas funções que iremos mexer:
// add → mul ((PLUS | MINUS) mul)*
const add = () => {
// mul
let result = mul()
// ((PLUS | MINUS) mul)*
while(match('Plus') || match('Minus')) {
// precisamos verificar se o token que deu match é Plus ou Minus para fazer a operção correta
// usamoos o `prev` pois o ponteiro já avançou pelo `match`
if (prev().type === 'Plus') result = result + mul()
if (prev().type === 'Minus') result = result - mul()
}
return result
}
// mul → num ((STAR | SLASH) num)*
const mul = () => {
// num
let result = num()
// ((STAR | SLASH) num)*
while(match('Star') || match('Slash')) {
if (prev().type === 'Star') result = result * num()
if (prev().type === 'Slash') result = result / num()
}
return result
}
Você pode ver o resultado parcial neste link: https://repl.it/@renatorib/parser-v2
Operadores Unários
Até agora lidamos apenas com operadores binárias, isto é, quando o operador precisa de dois valores para gerar um resultado. Porém existem os operadores que são unários, como o caso do número negativo (-5) e do número positivo (+5). Apesar dos tokens serem os mesmos, eles não podem ser confundidos com a subtração e a adição. As operações unárias possuem uma precedência maior que as binárias.
Sabendo disso, vamos adicionar a regra dos unários (PLUS | MINUS) number ao nosso grammar.
expr → add add → mul ((PLUS | MINUS) mul)* - mul → num ((STAR | SLASH) num)* + mul → una ((STAR | SLASH) una)* + una → ((PLUS | MINUS) una) | num num → NUMBER
Primeiro precisamos mexer na regra de mul, pois a próxima regra não é mais num, mas sim a nossa nova regra una. Existe uma particularidade nessa nova regra que é o fato de que o operador unário pode operar sobre outros operadores unários. Observe: – -5, essa é uma expressão válida. Consiste em dois números negativos aninhados, que resulta em um número 5 positivo (menos com menos dá mais). Assim como a expressão – – + -5 também é válida. Por esse motivo, na regra una usamos ele mesmo como nontermial após o operador.
Então bora implementar:
Na regra mul vamos substituir apenas os num por una:
// mul → una ((STAR | SLASH) una)*
const mul = () => {
// una
let result = una()
// ((STAR | SLASH) una)*
while(match('Star') || match('Slash')) {
if (prev().type === 'Star') result = result * una()
if (prev().type === 'Slash') result = result / una()
}
return result
}
E a regra de una
// una → ((PLUS | MINUS) una) | num
const una = () => {
// ((PLUS | MINUS) una)
if (match('Plus') || match('Minus')) {
if (prev().type === 'Plus') return + una()
if (prev().type === 'Minus') return - una()
}
// | num
return num()
}
Você pode ver o resultado parcial neste link: https://repl.it/@renatorib/parser-v3
Subexpressões
As subexpressões – os famosos parênteses – nos permitem, mais do que agrupar, furar a fila da precedência das expressões. Elas possuem a maior precedência dentro das expressões, isto é, são calculadas antes de qualquer outro. Então, se por um lado na expressão 4 + 3 * 2 a multiplicação é calculada primeiro, nessa outra (4 + 3) * 2 a subexpressão 4 + 3 é calculada primeiro, e por consequência, a adição também.
Trazendo dois resultados diferentes. Porém, dentro da subexpressão, a ordem das precedências ainda são respeitadas, por exemplo em (4 + 3 * 2) * 2, apesar de o parênteses ser calculado primeiro, começará pelo 3 * 2. Sabendo disso, observe que as subexpressões, como o nome sugere, nada mais são do que expressões inteiras que serão executadas antes. A gente já tem a regra que lida com as expressões expr, só precisamos identificar as subexpressões pelos tokens de parênteses e usar a regra.
expr → add add → mul ((PLUS | MINUS) mul)* mul → una ((STAR | SLASH) una)* - una → ((PLUS | MINUS) una) | num + una → ((PLUS | MINUS) una) | prim - num → NUMBER + prim → NUMBER | LEFTPAREN expr RIGHTPAREN
A única coisa que fizemos foi adicionar | LEFTPAREN expr RIGHTPAREN na regra de num. Porém também tivemos que trocar o nome pois num não fazia mais sentido aqui. Usamos prim de primary. O nome aqui é bem arbitrário, poderia ser qualquer coisa. Para trocar o nome de num também tivemos que mexer na regra de una.
Ajuste em una:
- // | num - return num() + // | prim + return prim()
Novo num, agora prim:
// prim → NUMBER | LEFTPAREN expr RIGHTPAREN
const prim = () => {
// NUMBER
if (match('Number')) {
return prev().value
}
// | LEFTPAREN expr RIGHTPAREN
if (match('LeftParen')) {
const result = expr()
if (match('RightParen')) {
return result
}
throw SyntaxError(`Unexpected ${peek().type}, expecting closing paren`)
}
throw SyntaxError(`Unexpected ${peek().type} token`)
}
A ideia é simples, ao encontrar um LEFTPAREN, salvamos um result com o resultado da expr() e só retornamos caso ache um RIGHTPAREN que feche a subexpressão, caso contrário temos um erro de sintaxe.
Você pode ver o resultado parcial neste link: https://repl.it/@renatorib/parser-v4
***
Na continuação da série aprenderemos mais sobre a árvore sintática abstrata, ou abstract syntax tree (a famosa AST). Não perde!