Operadores numéricos são mais complexos do que parece

O que faremos

No último post, expandimos nossa linguagem para "enxergar" uma única instância de qualquer um dos valores literais que definimos: int, float, bool, string e char. Nesse post nosso foco será integrar operadores aritméticos na nossa gramática. Spoiler Alert: é mais difícil do que parece.

Isso porque precisamos criar nossa AST corretamente, seguindo a ordem de precedência dos operadores, ou seja, os sinais + e - têm mais "importância" do que os de * e /. Isso parece ser contraditório, mas faz total sentido, pra entender melhor vamos precisar criar algumas árvores.

Vamos transformar essa expressão aritmética 2 * 3 + 4 em uma AST:

     +
    / \
   2   *
      /  \
     3    4

perceba que a raiz da AST é a operação +, isso porque esta operação tem menor precedência, ou seja, ela se "encaixa" na árvore depois, uma outra maneira de entender isso é imaginando que cada operador tem uma distância limite onde procuram os operandos, quanto maior essa distância menor a precedência do operador.

Na prática, precisamos criar regras gramaticais diferentes para cada nível de precedência para que o compilador crie a AST de forma correta.

Alterando o tokenizer

Como estamos introduzindo novos elementos na linguagem precisamos adicionar novas regras no nosso tokenizer, e neste caso isso é bem fácil, basta definir nomes para caracteres específicos:

//...
  bool: /true|false/,
  plus: '+',
  dash: '-',
  star: '*',
  slash: '/',
  NL: { match: '\n', lineBreaks: true },
})

Isso já é o suficiente para adicionar os operadores primários na nossa linguagem, agora o próximo passo é alterar nossa gramática para gerarmos ASTs corretas.

Atualizando gramática

Um ponto importante que não podemos ignorar é que agora temos que lidar com espaços em branco, ao escrever uma expressão matemática geralmente escrevemos com espaços em branco ao redor dos operadores, portanto o primeiro passo é definir regras para espaço em branco na nossa gramática.

A princípio teremos dois tipos de espaço em branco, espaço obrigatório e espaço opcional, isso é uma prática comum de gramática nearley então vamos manter, vamos ignorar a existência de quebras de linha por enquanto.

Por questões de simplicidade vamos usar um único underscore _ para a regra de espaço opcional e underscore duplo __ para a regra de espaço obrigatório dessa forma:

#...

_ -> %WS:* {% id %}
__ -> %WS:+ {% id %}

Vamos agora criar a regra para os operadores de menor precedência (+, -), pois temos que seguir a hierarquia de precedência inversa (de menor precedência para maior precedência) para formarmos ASTs corretas.
Primeiro definimos a regra de operadores e depois de expressões., a regra de expressão a princípio aceitará uma única instância de expressão, depois vamos expandir para aceitar expressões encadeadas.
A regra para expressões também terá espaçamento obrigatório entre os termos.

#...
term_operator
  -> %plus {% id %}
  | %dash {% id %}

term_expression
  -> literal __ term_operator __ literal {% data => ({
    type: 'binary_expression',
    operator: data[2],
    left: data[0],
    right: data[4],
  }) %}
#...

Vamos alterar nossa regra program para aceitar agora um único valor literal (como já era antes) ou uma única expressão simples.

#...
program
  -> literal {% id %}
  | term_expression {% id %}
#...

Agora vamos compilar nossa gramática mais uma vez rodando o comando nearleyc lang0.ne -o lang0.js

Nota: Nesse momento percebo que estamos rodando esse comando toda vez, portanto decidi criar um script no meu arquivo package.js para rodar esse comando automaticamente.

"scripts": {
  "nc": "nearleyc lang0.ne -o lang0.js"
},

Portanto a partir de agora vou usar o comando pnpm nc para compilar minha gramática.

Voltando ao que estávamos fazendo antes, precisamos testar agora essa nova regra, pra isso vou alterar nosso arquivo de teste para conter apenas um número:

1

Rodar o comando: node parser ex.ln0
E o resultado está correto:

{
  "type": "int",
  "value": "1",
  "text": "1",
  "offset": 0,
  "lineBreaks": 0,
  "line": 1,
  "col": 1
}

Se alterarmos o arquivo exemplo para conter uma expressão de soma agora:

1 + 2

E rodarmos o comando novamente: node parser ex.ln0
O resultado é esse:

{
  "type": "binary_expression",
  "operator": {
    "type": "plus",
    "value": "+",
    "text": "+",
    "offset": 2,
    "lineBreaks": 0,
    "line": 1,
    "col": 3
  },
  "left": {
    "type": "int",
    "value": "1",
    "text": "1",
    "offset": 0,
    "lineBreaks": 0,
    "line": 1,
    "col": 1
  },
  "right": {
    "type": "int",
    "value": "2",
    "text": "2",
    "offset": 4,
    "lineBreaks": 0,
    "line": 1,
    "col": 5
  }
}

Está correto.

Vamos testar com o operador de menos: 1 - 2
Resultado (omiti algumas informações pra ficar mais conciso):

{
  "type": "binary_expression",
  "operator": {
    "type": "dash",
    "value": "-",
    //...
  },
  "left": {
    "type": "int",
    "value": "1",
    //...
  },
  "right": {
    "type": "int",
    "value": "2",
    //...
  }
}

Alterando o type checker

Agora temos um novo node possível, o binary_expression node, por isso precisamos criar uma nova função específica para checkar esse node.
Neste começo vamos fazer com que os operadores aritméticos só funcionem com valores numéricos, por tanto, primeiro precisamos criar a função check_number que retornará true caso o node seja um valor numérico e false caso contrário.

function check_number(node) {
  const { type } = node
  return check_int(node) || check_float(node)
}

Agora podemos criar a função check_binary_expression:

function check_binary_expression(node) {
  const { left, right } = node
  return check_number(left) && check_number(right)
}

Com essa nova função em mãos precisamos apenas fazer uma função mais high level que será responsável por checkar o programa inteiro, visto que, como foi definido anteriormente, um programa nessa linguagem agora pode ser apenas um valor literal ou apenas uma expressão simples.

function check_program(ast) {
  const { type } = ast
  if (type === 'literal') {
    return check_literal(ast)
  } else if (type === 'binary_expression') {
    return check_binary_expression(ast)
  } else {
    console.log(`Invalid AST has type = ${type}`)
    return false
  }
}

Basta alterarmos a chamada principal do programa agora:

//...
  const ast = JSON.parse(content);
  console.log(check_program(ast));
} catch(e) {
//...

Vamos testar agora rodando o comando: node typecheck ast.json e o resultado é true como esperado.

Vamos alterar nosso arquivo exemplo para "somar" duas strings:

"2" + "a"

Vamos compilar: node parser ex.ln0
E verificar: node typecheck ast.json
O resultado é false, como esperado, pois definimos que os operandos dos operadores devem ser numéricos.

Atualizando o gerador de código

Agora só precisamos criar a função geradora para transformarmos nossa AST de expressão binária em javascript válido.

Pra isso precisamos criar a função gen_binary_expression, responsável por transformar um node do tipo binary_expression em string:

function gen_binary_expression(node) {
  const { operator, left, right } = node
  return `${left.value} ${operator.value} ${right.value}`
}

E a função gen_program, que será nossa função high level para decidir qual função ustilizar:

function gen_program(ast) {
  const { type } = ast
  if (type === 'literal') {
    return gen_literal(ast)
  } else if (type === 'binary_expression') {
    return gen_binary_expression(ast)
  } else {
    console.log(`Invalid AST has type = ${type}`)
    return ''
  }
}

Agora é só alterar nossa chamada principal para executar a função gen_program:

//...
  const ast = JSON.parse(contents);
  const output = gen_program(ast);
  fs.writeFileSync('output.js', output);
} catch(e) {
//...

Antes de testar vamos voltar nosso arquivo exemplo para algo mais coerente com nossa linguagem e passar por todas as etapas:

1. Alterar o arquivo ex.ln0 para conter a expressão 42 + 1
2. Compilar a AST do nosso programa rodando node parser ex.ln0
3. Fazer verificação de tipos rodando node typecheck ast.json
4. Como o resultado foi positivo vamos gerar o javascript final rodando node generator ast.json

Se verificarmos nosso arquivo output.js agora teremos:

42 + 1

E assim concluímos a primeira etapa do conceito de expressões.

Próximos passos

Ainda precisamos dos outros operadores aritméticos * e / (que são de outro nível de precedência) para completarmos nossas expressões aritméticas simples, depois ainda temos os operadores unários, operadores de comparação, de lógica, de operações de bit, em fim, muitas coisas ainda pra termos um bom set de operadores.
Porém tudo ficará mais fácil agora e será mais ou menos só uma questão de copiar, colar e ajustar.
Até a próxima!