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)