Desmistificando Interpretadores – Parte 4

Antes de mais nada, esta é a continuação da série Desmistificando Interpretadores. Para não se perder, leia os primeiros posts, onde abordo sobre Análise Léxica e Análise Sintática:

1ª Parte – Desmistificando Interpretadores

2ª Parte – Desmistificando Interpretadores

3ª Parte – Desmistificando Interpretadores

 

Abstract Syntax Tree (AST)

Se você lembra, no começo deste tópico de Análise Sintática, eu disse que iríamos construir nosso AST. Mas cadê? Bom, eu pulei essa parte. Ao invés disso, usamos o parser para interpretar o código diretamente, por exemplo:

Fiz isso para poder explicar melhor como o recursive descent parser funciona, sem precisar entrar nos detalhes da AST. Mas o ideal é que a gente chegue nisso:

Mas aí você me pergunta: se a gente já chegou no resultado final, que era o resultado, por que precisamos passar ainda pelo AST? Bom, de fato, se nosso objetivo fosse só esse, poderíamos simplificar as coisas e terminar por aqui. Mas o AST tem um papel fundamental na terceira etapa, a etapa da análise semântica. E com o AST, nós não apenas conseguimos calcular o resultado final da expressão, mas fazer muitas outras coisas.

Mas afinal, o que é AST?

Tá, eu sei que é uma árvore de sintaxe abstrata, mas, o que isso quer dizer? Sabemos que árvore é uma estrutura de dados, geralmente encadeado e representado por vários nós (ou nodes).

À grosso modo, a gente vai pegar uma expressão e transformá-la e em um objeto que represente esta expressão, como por exemplo:

De:

1 + 2 * 3

Para:

{

  "type": "BinaryOpNode",

  "token": {

    "type": "Plus"

  },

  "left": {

    "type": "LiteralNode",

    "token": {

      "type": "Number",

      "value": 1

    }

  },

  "right": {

    "type": "BinaryOpNode",

    "token": {

      "type": "Star"

    },

    "left": {

      "type": "LiteralNode",

      "token": {

        "type": "Number",

        "value": 2

      }

    },

    "right": {

      "type": "LiteralNode",

      "token": {

        "type": "Number",

        "value": 3

      }

    }

  }

}

Nodes

Dentro do AST, cada node representa uma construção sintática dentro do programa. Pode representar um valor literal, bruto, como: number, float, string, boolean, etc. Pode representar uma expressão (com seus fatores e operador), uma declaração de variável (com o identificador e sua atribuição), entre outros. No nosso interpretador, teremos apenas três nodes, e são eles:

Em primeiro lugar, o LiteralNode que vai representar os nodes literais, no nosso caso o number.

interface LiteralNode {

  type: 'LiteralNode',

  token: Token

}

Em segundo lugar, o BinaryOpNode representando os operadores binários, isto é, operadores que possuem dois fatores (soma, subtração, multiplicação e divisão).

interface BinaryOpNode {

  type: "BinaryOpNode",

  left: Node,

  right: Node,

  token: Token

}

O último node, UnaryOpNode, representando nossos operadores unários, no nosso caso o valor negativo.

interface UnaryOpNode {

  type: "UnaryOpNode",

  expr: Node,

  token: Token

}

Por fim, iremos criar três funções que criam nossos três nodes. São funções simples que recebem os dados e retornam o objeto que representa o node.

const nodes = {

  LiteralNode: ({ token }) => 

    ({ type: "LiteralNode", token }),




  BinaryOpNode: ({ left, right, token }) => 

    ({ type: "BinaryOpNode", left, right, token }),




  UnaryOpNode: ({ expr, token }) => 

    ({ type: "UnaryOpNode", expr, token })

}

De volta ao Parser

Agora que temos nossos nodes definidos, precisamos reescrever nosso parser para que ele gere o AST ao invés de interpretar o resultado final.

const add = () => {

  let node = mul()




  while (match('Plus') || match('Minus')) {

    node = nodes.BinaryOpNode({ token: prev(), left: node, right: mul() })

  }




  return node

}

const mul = () => {

  let node = una()




  while (match('Star') || match('Slash')) {

    node = nodes.BinaryOpNode({ token: prev(), left: node, right: una() })

  }    




  return node

}

const una = () => {

  if (match('Minus') || match('Plus')) {

    return nodes.UnaryOpNode({ token: prev(), expr: una() })

  }




  return prim()

}

const prim = () => {

  if (match('Number')) {

    return nodes.LiteralNode({ token: prev() })

  }




  if (match('LeftParen')) {

    const result = expr()




    if (match('RightParen')) {

      return result

    }




    throw SyntaxError(`Unexpected ${peek().type}, expecting closing paren`)

  }




  throw new Error(`Unexpected ${peek().type} token`)

}

Interpretando o AST

Existem várias maneiras que uma linguagem pode fazer para se obter o resultado final de um código fonte. Em geral, costuma ser uma parte complexa por ter que lidar com contextos, escopos, globais, expressões, entre outros. Nosso interpretador só lida com expressões, ou seja, para executar nosso programa vamos apenas calcular nossa expressão, e produzir um valor final.

Anteriormente, nós já havíamos chegado ao valor final de nossa expressão calculando diretamente no parser. Demos um passo atrás para reescrevê-lo e produzir um AST. Da mesma forma como quando fizemos dentro do parser, onde percorremos por todos os lexemes, identificamos nodes e calculamos seu valor baseado em cada tipo. Portanto, iremos ter que percorrer agora o AST e realizar a mesma lógica necessária para cada node.

Iremos construir uma função que irá visitar cada node, muito parecido com o que um visitor pattern faz, mas muito mais simplista e menos flexível, por ora.

const interpreter = (ast) => {

  // define os visitors de cada node

  const visitors = {

    LiteralNode() { ... },

    BinaryOpNode() { ... },

    UnaryOpNode() { ... },

  }




  // executa o visitor correspondente ao node

  const visit = (node) {

    if (visitors[node.type]) {

      return visitors[node.type](node, visit)

    }

  }




  // executa o visitor do primeiro node do ast

  return visit(ast)

}

Quando chamarmos nossa função interpreter(), ela irá percorrer todos os nodes chamando o visitor responsável por calcular seu próprio resultado. Por exemplo, o visitor do BinaryOpNode será responsável por somar o left e o right caso seu operator seja do token Plus. Ou multiplicar o left e right caso seu operator seja do token Star. Da mesma forma para os outros operadores.

Cada visitor recebe o node como primeiro argumento, e a função visit como segundo argumento, para que ele possa visitar e obter o resultado dos seus nodes filhos.

Começamos pelo LiteralNode, que é o mais simples dos nodes, já que ele representa um node terminal. Ele não possui outros nodes dentro dele, ou seja, para calcular seu valor nós apenas retornamos o valor do seu token.

LiteralNode

const visitors = {

  LiteralNode(node) {

    return node.token.value

  }

}

Agora criamos o visitor para o BinaryOpNode. Apesar de parecer complexo, a ideia também é simples. Iremos aplicar a lógica para o left e right baseado no operador. Ou seja, para o operador de soma, iremos somar o left e o right. Porém, lembre-se que o right e o left também são nodes, então precisamos interpretar eles primeiro, como:

BinaryOpNode

const visitors = {

  // ...

  BinaryOpNode(node, visit) {

    const leftVal = visit(node.left)

    const rightVal = visit(node.right)




    if (node.token.type === 'Plus') {

      return leftVal + rightVal

    }




    if (node.token.type === 'Minus') {

      return leftVal - rightVal

    }




    if (node.token.type === 'Star') {

      return leftVal * rightVal

    }




    if (node.token.type === 'Slash') {

      return leftVal / rightVal

    }

  }

}

Para o nosso último node, o UnaryOpNode, a ideia não é muito diferente.

UnaryOpNode

const visitors = {

  // ...

  UnaryOpNode(node, visit) {

    const exprVal = visit(node.expr)




    if (node.token.type === 'Plus') {

      return + exprVal        

    }




    if (node.token.type === 'Minus') {

      return - exprVal

    }

  } 

}

Pronto! Em conclusão temos um interpretador que usa o AST como base!

Se a gente chamar interpreter(parser(lexer(“5 – 2 * 3”))) obtemos o valor 1 como resultado.

Você pode ver o resultado parcial neste link: https://repl.it/@renatorib/parser-v5