Já temos um bom arsenal de expressões singulares preparado, nossa linguagem já "entende" expressões aritméticas binárias e unárias e agora precisamos fazer com que ela "entenda" expressões encadeadas.
Pra isso vamos definir todos os tipos de expressões e usaremos a sequência de precedência para fazer as alterações necessárias.
No nível mais baixo temos os valores literais e os agrupamentos, que são expressões entre parênteses, para trabalharmos com agrupamentos primeiro precisamos alterar nosso tokenizer:
//... lparen: '(', rparen: ')', //... Agora podemos criar a regra primary_expression que representa o primeiro nível de expressões:
primary_expression -> literal {% id %} | %lparen term_expression %rparen {% data => data[1] %} Essa regra interpreta literais ou expressões entre parênteses.
A próxima na lista é a unary_expression que já temos, porém precisaremos fazer alguma alterações:
unary_expression -> primary_expression {% id %} | unary_operator primary_expression {% data => ({ type: 'unary_expression', operator: data[0], argument: data[1], }) %} Perceba a alteração de literal para primary_expression, e a adição da variante anterior primary_expression como opção de resolução, essas alterações fazem uma regra depender da outra ao mesmo tempo que evita ambiguidade, vamos continuar com essa lógica subindo a hierarquia.
A próxima da lista é a factor_expression:
factor_expression -> unary_expression {% id %} | factor_expression __ factor_operator __ factor_expression {% data => ({ type: 'binary_expression', operator: data[2], left: data[0], right: data[4], }) %} E por último a term_expression:
term_expression -> factor_expression {% id %} | term_expression __ term_operator __ term_expression {% data => ({ type: 'binary_expression', operator: data[2], left: data[0], right: data[4], }) %} Testando
Basta compilar a gramática com o comando pnpm nc
Vamos também alterar nosso arquivo ex.ln0 escrevendo a expressão 2 + 3 * 4
Ao rodar o comando node parser ex.ln0, temos a seguinte AST:
{ "type": "binary_expression", "operator": { "type": "plus", "value": "+", //... }, "left": { "type": "int", "value": "2", //... }, "right": { "type": "binary_expression", "operator": { "type": "star", "value": "*", //... }, "left": { "type": "int", "value": "3", //... }, "right": { "type": "int", "value": "4", //... } } } O resultado é o esperado, o primeiro operador colapsado é o +, e a propriedade right é uma expressão binária inteira com o operador * portanto a regra de precedência se faz correta visto que o símbolo de * será avaliado primeiro por estar mais longe da raiz da AST.
Vamos alterar nosso exemplo dessa forma 2 + -(3 * 4 + 1) / 2, assim podemos ver na prática todas as variações de expressões.
Depois de rodar o comando node parser ex.ln0, temos o resultado:
{ "type": "binary_expression", "operator": { "type": "plus", "value": "+", //... }, "left": { "type": "int", "value": "2", //... }, "right": { "type": "binary_expression", "operator": { "type": "slash", "value": "/", //... }, "left": { "type": "unary_expression", "operator": { "type": "dash", "value": "-", //... }, "argument": { "type": "binary_expression", "operator": { "type": "plus", "value": "+", //... }, "left": { "type": "binary_expression", "operator": { "type": "star", "value": "*", //... }, "left": { "type": "int", "value": "3", //... }, "right": { "type": "int", "value": "4", //... } }, "right": { "type": "int", "value": "1", //... } } }, "right": { "type": "int", "value": "2", //... } } } Por enquanto tudo parece estar dentro dos conformes.
Expansão rápida
Já possuímos um "framework" de expressões binárias e unárias agora podemos expandir para não só expressões aritméticas mas também comparativas, lógicas e bitwise. Vamos aproveitar o fato de que é só copiar e colar para melhorar um pouco a nossa organização de código e fazer algumas refatorações.
Primeiramente vamos criar uma função especial para compilar nossos nodes do tipo binary_expression no nosso arquivo de gramática:
@{% const tokenizer = require('./tokenizer') function binary_expression(data) { return { type: 'binary_expression', operator: data[2], left: data[0], right: data[4] } } %} Dessa forma podemos para de copiar e colar esse pedaço de código nas expressões binárias, a refatoração fica dessa forma:
factor_expression -> unary_expression {% id %} | factor_expression __ factor_operator __ factor_expression {% binary_expression %} term_expression -> factor_expression {% id %} | term_expression __ term_operator __ term_expression {% binary_expression %} Antes de continuar precisamos aumentar nosso vocabulário de tokens adicionando os items >=, <=, !=, ==, >, <, =, |, & e ^ (lembrando de definir os tokens duplos antes dos simples para evitar errors):
//... gte: '>=', lte: '<=', neq: '!=', eqeq: '==', lor: '||', land: '&&', //... or: '|', gt: '>', lt: '<', eq: '=', and: '&', caret: '^', //... Vamos agora adicionar nossas regras de operadores comparativos, lógicos e bitwise:
comparison_operator -> %gt {% id %} | %gte {% id %} | %lt {% id %} | %lte {% id %} equality_operator -> %eqeq {% id %} | %neq {% id %} Note que não precisamos definir regras para operadores lógicos e bitwise pois cada um deles possuiu um nível de precedência diferente e fazer isso seria redundante.
O próximo passo é definir as regras de expressões de comparação e de igualdade :
comparison_expression -> term_expression {% id %} | comparison_expression __ comparison_operator __ comparison_expression {% binary_expression %} equality_expression -> comparison_expression {% id %} | equality_expression __ equality_operator __ equality_expression {% binary_expression %} E depois as regras individuais de expressões bitwise e de lógica:
# bitwise start bitwise_and_expression -> equality_expression {% id %} | bitwise_and_expression __ %and __ equality_expression {% binary_expression %} bitwise_xor_expression -> bitwise_and_expression {% id %} | bitwise_xor_expression __ %caret __ bitwise_and_expression {% binary_expression %} bitwise_or_expression -> bitwise_xor_expression {% id %} | bitwise_or_expression __ %or __ bitwise_xor_expression {% binary_expression %} # bitwise end # logical start logical_and_expression -> bitwise_or_expression {% id %} | logical_and_expression __ %lor __ bitwise_or_expression {% binary_expression %} logical_or_expression -> logical_and_expression {% id %} | logical_or_expression __ %land __ logical_and_expression {% binary_expression %} # logical end por último basta trocar nossa definição de program para usar a última expressão da lista a logcal_or_expression:
program -> logical_or_expression {% id %} Depois de compilar a gramática com pnpm nc e alterar nosso programa exemplo para 1 + 2 > 3 * 4 == 3 < 1 | 3 - 1
Vamos rodar o comando node parser ex.ln0 e o resultado é:
{ "type": "binary_expression", "operator": { "type": "or", //... }, "left": { "type": "binary_expression", "operator": { "type": "eqeq", //... }, "left": { "type": "binary_expression", "operator": { "type": "gt", //... }, "left": { "type": "binary_expression", "operator": { "type": "plus", //... }, "left": { "type": "int", "value": "1", //... }, "right": { "type": "int", "value": "2", //... } }, "right": { "type": "binary_expression", "operator": { "type": "star", //... }, "left": { "type": "int", "value": "3", //... }, "right": { "type": "int", "value": "4", //... } } }, "right": { "type": "binary_expression", "operator": { "type": "lt", //... }, "left": { "type": "int", "value": "3", //... }, "right": { "type": "int", "value": "1", //... } } }, "right": { "type": "binary_expression", "operator": { "type": "dash", //... }, "left": { "type": "int", "value": "3", //... }, "right": { "type": "int", "value": "1", //... } } } O que é bem impressionante!
Próximos Passos
Até agora fizemos a parte da expansão gramatical, porém ainda precisamos adequar nosso type checker e nosso generator para que eles funcionem corretamente. Faremos isso no próximo post, até mais!
Top comments (0)