Mais níveis de precedência e mais operadores

No último post adicionamos os operadores binários + e - em nossa linguagem, nesse post vamos adicionar os operadores binários * e / além dos unários ! e -, repare que o sinal de menos poder tanto um operador binário onde realmente seria uma operação de subtração ou pode ser um operador unário indicando que o número é negativo.

Olhando nas nossas definições de tokens iniciais, podemos já identificar um problema, os token incluem sinalização, teremos que alterar isso para não causar confusão no parser:
Atualmente temos essas duas definições:

//...
  float: /[-+]?(?:\d+\.\d*|\.\d+)(?:[eE][-+]?\d+)?/,
  int: /0|[-+]?[1-9][0-9]*/,
//...

Vamos altera-las para:

//...
  float: /(?:\d+\.\d*|\.\d+)(?:[eE][-+]?\d+)?/,
  int: /0|[1-9][0-9]*/,
//...

Dessa forma temos controle total da nossa gramática e o tokenizer não vai nos atrapalhar.

Com isso resolvido vamos continuar com nossa modificação, primeiramente implementando os operadores * e /

Adicionando os operadores * e /

Vamos adicionar os operadores à gramática:

factor_operator
  -> %star {% id %}
  | %slash {% id %}

E a regra de expressão única do tipo factor:

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

vamos também adicionar a regra factor_expression como opção para definição de um program válido:

program
  -> literal {% id %}
  | term_expression {% id %}
  | factor_expression {% id %}

Lembrando mais uma vez que por enquanto a linguagem suporta apenas uma expressão por vez. Uma multi-expressão como essa 2 + 3 * 4 ainda não é suportada pela nossa linguagem, trabalharemos nisso mais pra frente.

Para prosseguirmos vamos compilar nossa gramática com o comando pnpm nc.
Também vou alterar nosso programa exemplo dessa forma:

2 * 2

E compilar o programa: node parser ex.ln0
O resultado final é correto e fica dessa forma (omiti algumas informações por efeitos de concisão):

{
  "type": "binary_expression",
  "operator": {
    "type": "star",
    "value": "*",
    //...
  },
  "left": {
    "type": "int",
    "value": "2",
    //...
  },
  "right": {
    "type": "int",
    "value": "2",
    //...
  }
}

Como os novos operadores geram nodes do tipo binary_expression não precisamos alterar nosso arquivo typecheck.js. Da mesma forma nossa função gen_binary_expression do nosso arquivo generator.js já funcionará corretamente.

Para verificar vou continuar com o processo rodando o comando node typecheck ast.json, o resultado é true.
E rodando o comando node generator ast.json, o resultado é o arquivo output.js contendo o texto 2 * 2, ou seja, tudo funcionando perfeitamente.

Adicionando operadores unários

Operadores unário são operadores que recebem apenas um operando, os principais são o operador de negação lógica ! e o operador de negação aritmética - repare que o o símbolo - pode ser tanto o operador binário de subtração aritmética quanto a outra versão, o operador unários.

Para evitar confusão vamos definir uma regra geral para a linguagem onde os operadores unário dever estar localizados imediatamente ao lado do operando, por exemplo, esse seria um código inválido - 2, por causa do espaço, o correto seria -2 sem espaço.

Para isso precisamos alterar nossa gramática e nosso tokenizer mais uma vez.

Começando com alterações dos tokens, vamos adicionar o símbolo de negação lógica !:

//...
  bang: '!',
//...

Na nossa gramática vamos criar as regras para operadores e expressões unárias:

unary_operator
  -> %bang {% id %}
  | %dash {% id %}

#...

unary_expression
  -> unary_operator literal {% data => ({
    type: 'unary_expression',
    operator: data[0],
    argument: data[1],
  }) %}

Perceba que na definição de unary_expression não há nenhuma regra de espaçamento (_ ou __) para indicarmos que espaço entre o operador e o operando é proibido.

Precisamos incluir a nova regra na definição de program:

program
  -> literal {% id %}
  | term_expression {% id %}
  | factor_expression {% id %}
  | unary_expression {% id %}

Agora podemos compilar o arquivo de gramática usando pnpm nc

Vamos alterar nosso exemplo agora para fazer o teste de compilação:

-3

rodando o comando node parser ex.ln0 temos como resultado a seguinte AST:

{
  "type": "unary_expression",
  "operator": {
    "type": "dash",
    "value": "-",
    "text": "-",
    "offset": 0,
    "lineBreaks": 0,
    "line": 1,
    "col": 1
  },
  "argument": {
    "type": "int",
    "value": "3",
    "text": "3",
    "offset": 1,
    "lineBreaks": 0,
    "line": 1,
    "col": 2
  }
}

O que indica que tudo está funcionando corretamente.

Para finalizar basta adicionar novas funções para expressões unárias nos arquivos typecheck.js e generator.js

Começando com o typecheck.js precisamos criar uma função check_unary_expression e alterar nossa lógica principal.
Primeiro criamos a função:

function check_unary_expression(node) {
  const { argument } = node
  return check_number(argument)
}

E agora alteramos a lógica principal adicionando a branch de unary_expression:

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 if (type === 'unary_expression') {
    return check_unary_expression(ast)
  } else {
    console.log(`Invalid AST has type = ${type}`)
    return false
  }
}

Rodando o comando node typecheck ast.json o resultado no console é true indicando sucesso.

Por último vamos criar a função no arquivo generator.js:

function gen_unary_expression(node) {
  const { operator, argument } = node
  return `${operator.value}${argument.value}`
}

E agora basta alterar a lógica principal também:

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 if (type === 'unary_expression') {
    return gen_unary_expression(ast)
  } else {
    console.log(`Invalid AST has type = ${type}`)
    return ''
  }
}

Rodando o comando node generator ast.json o arquivo output.js possuiu o texto -3 indicando que tudo está funcionando corretamente

Próximos passos

Por enquanto nossa expressões são "únicas", ou seja, expressões encadeadas como essa 2 + 3 * 4 simplesmente não são suportadas pela nossa linguagem ainda e é nisso que vamos trabalhar no próximo capítulo.