Verificando e Gerando Expressões

Type Checker

Continuando nosso capítulo de expressões na nossa linguagem, neste post vamos focar na parte de verificação das expressões, alterando nosso type checker e também ajustando nosso generator para criar transformar as ASTs em javascript válido.

Atualmente nossa função check_binary_expression avalia as partes left e right do node são numéricas, porém agora nossas expressões podem conter outras expressões inteiras uma dentro da outra de forma arbitrária.
Nossa função check_program já muda a verificação dependendo do tipo do node, portanto podemos simplesmente usar recursividade e essa nossa função para resolver esse problema.
Nossa função check_binary_expression ficará assim agora:

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

Perceba que essa mudança é bem significativa pois antes estávamos usando a função check_numeric para verificar os componentes left e right do node, assim tínhamos certeza que os operadores aritméticos estavam sendo usado apenas com números, porém isso não faz mais sentido, primeiro porque temos mais tipos diferentes de expressões binárias e não só aritméticas e segundo que um operador é tecnicamente uma função e ainda não temos um mecanismo definido para verificar "assinaturas" de funções comparado com os argumentos da função, só conseguiremos fazer uma verificação mais profunda quando tivermos esse mecanismo criado.
Por enquanto vamos fazer verificação estrutural apenas, seguindo a lógica vamos alterar nossa função check_unary_expression também:

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

IMPORTANTE: Ao fazer um teste com a função check_program atual achei um erro que tinha passado despercebido, no meio da função temos a verificação if (type === 'literal') { porém não existem nodes do tipo literal, na verdade literal representa todos os tipos de node de valores como int, float, string, etc. Por isso vamos alterar nossa função para corrigir esse erro:

function check_program(ast) {
  const { type } = ast
  if (check_literal(ast)) {
    return true
  } 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
  }
}

Nesta nova versão utilizamos a função já previamente definida check_literal para "pular" o caso do node to "tipo" literal.

Agora com os novos ajustes vamos altera nosso arquivo exemplo para 2 * 3 + 4 || 3 - (3 * 1 + 3) == 1 rodar o comando node parser ex.ln0 e depois o comando node typecheck ast.json
Na tela é printado true indicando que a AST está "correta", isso ainda não significa muita coisa, mas em breve vamos trabalhar mais nisso e implementar o sistema de validação de "assinatura" de funções, por enquanto isso já está bom o suficiente.

Generator

Vamos focar agora no generator e transformar nossa AST em javascript válido contendo as várias expressões que já conseguimos parsear.

No nosso generator temos os mesmos problemas para resolver, precisamos usar recursão e arrumar nossa função principal que também contêm a verificação do tipo literal que não faz sentido.

Primeiro vamos alterar nossas funções geradoras gen_binary_expression e gen_unary_expression usando recursão para gerar os parâmetros:

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

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

E depois alteramos nossa função principal, pra isso vamos "emprestar" nossa função check_literal do módulo typecheck:

module.exports.check_literal = check_literal

const { check_literal } = require('./typecheck')
//...
function gen_program(ast) {
  const { type } = ast
  if (check_literal(ast)) {
    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 ''
  }
}

Agora com todas essas modificações, basta rodarmos o comando node generator ast.json o nosso arquivo output.js fica dessa forma: 2 * 3 + 4 || 3 - 3 * 1 + 3 == 1. Está quase correto, o único problema é a falta dos parênteses que estavam no arquivo original, eles sumiram porque atualmente nossa definição gramática ignora os parênteses, para arrumarmos isso precisamos alterar nossa gramática primeiro:

primary_expression
  -> literal {% id %}
  | %lparen term_expression %rparen {% data => ({
    type: 'parenthesized_expression',
    expression: data[1],
  }) %}

Agora introduzimos um novo type de node, o parenthesized_expression, com essa diferenciação conseguimos preservar a estrutura original, mas antes de continuar vamos buidlar nossa gramática rodando o comando pnpm nc.

Agora precisamos adicionar os handlers do tipo parenthesized_expression no typecheck.js e no generator.js, começando com o typecheck.js:

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

Por ser algo bem simples de se fazer vou deixar no meio da função mesmo, vamos fazer agora o do generator.js:

function gen_program(ast) {
  const { type } = ast
  if (check_literal(ast)) {
    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 if (type === 'parenthesized_expression') {
    return gen_parenthesized_expression(ast)
  } else {
    console.log(`Invalid AST has type = ${type}`)
    return ''
  }
}

Neste caso vamos criar uma função separada mesmo, a função gen_parenthesized_expression:

function gen_parenthesized_expression(node) {
  const { expression } = node
  return `(${gen_program(expression)})`
}

Agora, ao rodar o comando node typecheck ast.json temos o resultado true, indicando que tudo está funcionando bem e ao rodar o comando node generator ast.json o resultado é: 2 * 3 + 4 || 3 - (3 * 1 + 3) == 1 agora com os parêntesis.

Finalização

Nossa linguagem agora consegue "enxergar" vários tipos de expressões com vários níveis de profundidade e depois consegue transformar tudo em javascript. Por enquanto não há nenhuma diferença pois estamos tratando apenas de expressões básicas e ainda não implementamos nosso sistema de tipagem nem de funções, nem de verificação de "assinatura" de funções e é isso que vamos focar no próximo post. Até mais!