Pressione enter para ver os resultados ou esc para cancelar.

Desmistificando Interpretadores – Parte 3

No post anterior 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:

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:

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.

 

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:

E a regra de una

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.

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:

Novo num, agora prim:

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!


***
📣
Estamos contratando pessoas que desenvolvam software!
Mais informações sobre a vaga.
***