Expressões encadeadas e agrupamento
Tags: programminglanguage, javascript, languagedesign, compilers
Published: 2023-12-30 11:54:36

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:

```tokenizer.js
//...
  lparen: '(',
  rparen: ')',
//...
```

Agora podemos criar a regra `primary_expression` que representa o primeiro nível de expressões:
```lang0.ne
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:
```lang0.ne
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`:
```lang0.ne
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`:
```lang0.ne
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:
```ast.json
{
  "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:
```ast.json
{
  "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:
```lang0.ne
@{%
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:
```lang0.ne
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):
```tokenizer.js
//...
  gte: '>=',
  lte: '<=',
  neq: '!=',
  eqeq: '==',
  lor: '||',
  land: '&&',
//...
  or: '|',
  gt: '>',
  lt: '<',
  eq: '=',
  and: '&',
  caret: '^',
//...
```

Vamos agora adicionar nossas regras de operadores comparativos, lógicos e bitwise:
```lang0.ne
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 :
```lang0.ne
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:
```lang0.ne
# 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`:
```lang0.ne
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 é:
```ast.json
{
  "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!