Operadores numéricos são mais complexos do que parece
Tags: programming, language, languagedesign, tutorial
Published: 2023-12-20 20:53:36

### O que faremos
[No último post](https://dev.to/lucas_ac_am/alem-dos-numeros-expandindo-a-linguagem-2b0j), 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:
```tokenizer.js
//...
  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:
```lang0.ne
#...

_ -> %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.
```lang0.ne
#...
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.
```lang0.ne
#...
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.
```package.json
"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:
```ex.ln0
1
```

Rodar o comando: `node parser ex.ln0`
E o resultado está correto: 
```ast.json
{
  "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:
```ex.ln0
1 + 2
```

E rodarmos o comando novamente: `node parser ex.ln0`
O resultado é esse:
```ast.json
{
  "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): 
```ast.json
{
  "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.
```typecheck.js
function check_number(node) {
  const { type } = node
  return check_int(node) || check_float(node)
}
```

Agora podemos criar a função `check_binary_expression`:
```typecheck.js
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.
```typecheck.js
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:
```typecheck.js
//...
  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_:
```ex.ln0
"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:
```generator.js
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:
```generator.js
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`:
```generator.js
//...
  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:
```output.js
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!