Expressões encadeadas e agrupamento

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!