Práctica: Traducción de expresiones aritméticas a JavaScript

Introducción

Enunciado de la práctica arith2js

En la presente práctica se pretende implementar un traductor de expresiones aritméticas a JavaScript. Para ello se utilizará la herramienta Jison que es un generador de analizadores sintácticos (parsers) a partir de una gramática y un analizador léxico.

Primeros pasos

Instalar Dependencias

npm install

Código

Crear el fichero de gramática

%{
const { 
 L,
 buildLiteral, 
 buildBinaryExpression, 
 buildRoot,
 buildUnaryExpression,
 buildCallExpression
} = require('./ast-build.js');
%}
%token 
%left '+' '-'
%left '*' '/'
%right '**'
%left '!'
%nonassoc UMINUS
%%
es: e EOF { return buildRoot($1, L(@1, yy)); }
;

e:
   e '-' e     { $$ = buildBinaryExpression($1, $2, $3, L(@2, yy)); }
 | e '+' e     { $$ = buildBinaryExpression($1, $2, $3, L(@2, yy)); }
 | e '*' e     { $$ = buildBinaryExpression($1, $2, $3, L(@2, yy)); }
 | e '/' e     { $$ = buildBinaryExpression($1, $2, $3, L(@2, yy)); }
 | '(' e ')'   { $$ = $2; }
 | e '**' e    { $$ = buildCallExpression('power', [$1, $3], L(@2, yy)); }
 | e '!'       { $$ = buildCallExpression('factorial', [$1], L(@2, yy)); }
 | '-' e %prec UMINUS { $$ = buildUnaryExpression($1, $2, L(@1, yy)); }
 | N           { $$ = buildLiteral($1, L(@1, yy)); }
;

Crear el fichero de construcción del AST en el que se encuentran las funciones que construyen los nodos del árbol sintáctico abstracto

function buildRoot(child, loc) {
  return {
    "type": "Program",
    "start": [loc.start.line - 1] + loc.start.column,
    "end": [loc.end.line - 1] + loc.end.column,
    "loc": loc,
    "range": [
      [loc.start.line - 1] + loc.start.column,
      [loc.end.line - 1] + loc.end.column
    ],
    "body": [
      {
        "type": "ExpressionStatement",
        "start": [loc.start.line - 1] + loc.start.column,
        "end": [loc.end.line - 1] + loc.end.column,
        "loc": loc,
        "range": [
          [loc.start.line - 1] + loc.start.column,
          [loc.end.line - 1] + loc.end.column
        ],
        "expression": child
      }
    ],
    "sourceType": "script"
  };
}

function L(jloc, { input, offsets }) {
  return {
    "start": {
      "line": jloc.first_line,
      "column": jloc.first_column
    },
    "end": {
      "line": jloc.last_line,
      "column": jloc.last_column
    }
  };
}

function computeLineOffets(input) {
  let offsets = [];
  let lines = input.split("\n");
  let offset = 0;
  for (let i = 0; i < lines.length; i++) {
    offsets.push(offset);
    offset += lines[i].length + 1;
  }
  return offsets;
}

function buildLiteral(raw, loc) {
  return {
    "type": "Literal",
    "start": [loc.start.line - 1] + loc.start.column,
    "end":  [loc.end.line - 1] + loc.end.column,
    "loc": loc,
    "range": [
      [loc.start.line - 1] + loc.start.column,
      [loc.end.line - 1] + loc.end.column
    ],
    "value": Number(raw),
    "raw": raw
  };
}

function buildBinaryExpression(left, op, right, loc) {
  return {
    "type": "BinaryExpression",
    "start": [loc.start.line - 1] + loc.start.column,
    "end": [loc.end.line - 1] + loc.end.column,
    "loc": loc,
    "range": [
      [loc.start.line - 1] + loc.start.column,
      [loc.end.line - 1] + loc.end.column
    ],
    "operator": op,
    "left": left,
    "right": right
  };
}

function buildUnaryExpression(op, argument, loc) {
  return {
    "type": "UnaryExpression",
    "start": [loc.start.line - 1] + loc.start.column,
    "end": [loc.end.line - 1] + loc.end.column,
    "loc": loc,
    "range": [
      [loc.start.line - 1] + loc.start.column,
      [loc.end.line - 1] + loc.end.column
    ],
    "operator": op,
    "prefix": true,
    "argument": argument
  };
}

function buildCallExpression(callee, args, loc) {
  return {
    "type": "CallExpression",
    "start": [loc.start.line - 1] + loc.start.column,
    "end": [loc.end.line - 1] + loc.end.column,
    "loc": loc,
    "range": [
      [loc.start.line - 1] + loc.start.column,
      [loc.end.line - 1] + loc.end.column
    ],
    "callee": {
      "type": "Identifier",
      "start": [loc.start.line - 1] + loc.start.column,
      "end": [loc.end.line - 1] + loc.end.column,
      "loc": loc,
      "range": [
        [loc.start.line - 1] + loc.start.column,
        [loc.end.line - 1] + loc.end.column
      ],
      "name": callee
    },
    "arguments": args
  };
}

module.exports = {
    buildRoot,
    buildBinaryExpression,
    buildUnaryExpression,
    buildLiteral,
    computeLineOffets,
    L,
    buildCallExpression
};

Crear el fichero con la función transpile que se encargará de generar el código JavaScript a partir del AST

#!/usr/bin/env node
const fs = require('fs/promises');

const p = require("./calc").parser;

const estraverse = require("estraverse"); 
const exportedSupportIdentifiers = Object.keys(require("./support-lib.js")); // [ power, factorial ]

const escodegen = require('escodegen');
const { renderFile } = require('template-file'); // handlebars.js mustache.js ...

const computeLineOffets = require('./ast-build').computeLineOffets;

async function generateCode(dependencies, ast) {
  let code = escodegen.generate(ast);
  code = `console.log(${code.slice(0, -1)});`;
  if (dependencies.length === 0) {
    return code;
  }
  let root = __dirname.replace(/\/src$/, '');
  return renderFile(`${root}/src/template.js`, { root, code, dependencies });
}

const findUsedFunctions = function (ast) {
  const usedSupportFunctions = new Set();
  estraverse.traverse(ast, {
    enter: function (node, _ ) {
      if (node.type === "CallExpression" && node.callee.type === "Identifier" && exportedSupportIdentifiers.includes(node.callee.name)) {
        usedSupportFunctions.add(node.callee.name);
      }
    },
  });
  return Array.from(usedSupportFunctions);
}

async function writeOutput(outputFile, output, options) {
  let finalOutput = output;
  if (options?.verbose) {
    console.log(finalOutput);
  }
  if (!outputFile) {
    return finalOutput;
  }
  await fs.writeFile(outputFile, finalOutput);
  return finalOutput;
}

module.exports = async function transpile(inputFile, options) {
  let outputFile = options?.output || "./out/output.js";
  try {
    let input = await fs.readFile(inputFile, 'utf-8')
    let offsets = computeLineOffets(input);           

    p.yy = { input, offsets };      
    const ast = p.parse(input);

    let dependencies = findUsedFunctions(ast);        

    const output = await generateCode(dependencies, ast);
    
    return await writeOutput(outputFile, output, options);
  } catch (e) {
    console.error(e.message);
  }
};

Crear el fichero de ejecución bin/calc2js.mjs

#!/usr/bin/env node

import { program } from "commander";
import { createRequire } from "module";
const require = createRequire(import.meta.url);
const { version } = require("../package.json");
import transpile from "../src/transpile.js";
import run  from "../src/run.js";


program
  .version(version)
  .showSuggestionAfterError(true);

program
  .command("transpile")
  .argument("<filename>", "calc file to transpile")
  .option("-o, --output <filename>", "output file")
  .option("-v, --verbose", "show generated code")
  .description("Transpile a calc file to JavaScript")
  .action((filename, options) => {
    transpile(filename, options); // Options es: { output: "archivosalida", verbose: true/false }
  });
  
program.parse(process.argv);

Ejecutar el programa

Para ejecutar el programa se debe ejecutar el siguiente comando que transpilará el archivo test/test1.calc a JavaScript

node bin/calc2js.mjs transpile test/test1.calc -o out.js

Si queremos que se ejecute el código generado, podemos usar la opción -v para que se muestre el código y pasarlo por pipeline a node

node bin/calc2js.mjs transpile test/test1.calc -o out.js -v | node

Adiciones

Con lo anterior tendríamos suficiente para ejecutar algunos archivos con operaciones básicas, pero necesitamos importar algunas funciones que no están definidas en el código que hemos escrito. Para ello, se ha creado un fichero support-lib.js que contiene las funciones power y factorial.

Crear el fichero support-lib.js

let gamma = require('math-gamma');
const power = (base, exponent) => Math.pow(base, exponent);
const factorial = (number) => gamma(number + 1);

module.exports = { 
  power, 
  factorial 
};

Crear el fichero template.js

Se usará template-file para añadir las dependencias solo cuando se necesiten

const { {{ dependencies }} } = require('{{root}}/src/support-lib.js');
{{code}}

Función run

Es incómodo tener que ejecutar el código generado con node, por lo que se ha creado una función run que se encarga de ejecutar el código generado

const transpile = require("./transpile.js");

module.exports = async function run(inputFile, options) {
  const code = await transpile(inputFile, options);
  eval(code);
};

Ahora se puede ejecutar con el siguiente comando

node bin/calc2js.mjs run test/test1.calc

Añadiendo la opción -v se mostrará el código generado

node bin/calc2js.mjs run test/test1.calc -v

Testing con Mocha

Se ha creado un fichero test.js en el que se automatiza la ejecución de los tests

const transpile = require("../src/transpile.js");
const assert = require('assert');
const fs = require("fs/promises");

require('dotenv').config();
const JSComparison = process.env.JSComparison === 'true';
const REMOVE_OUTPUTS = process.env.REMOVE_OUTPUTS === 'true';

const Tst = require('./test-description.js');

const Test = Tst.map(t => ({
  input: __dirname + '/data/' + t.input,
  output: __dirname + '/data/' + t.output,
  expected: __dirname + '/data/' + t.expected,
  correctOut: __dirname + '/data/' + t.correctOut,
})
)

const removeRequires = /require\(["'][\S]+["']\)/g;

function removeSpaces(s) {
  return String(s).replace(/\s/g, '').replace(removeRequires, 'require("support-lib")');
}

async function outputProgramIsAsExpected(t, outputjs) {
  let expectedjs = await fs.readFileSync(t.expectedjs, 'utf-8')
  
  assert.equal(removeSpaces(outputjs), removeSpaces(expectedjs));
  if (REMOVE_OUTPUTS) fs.unlinkSync(t.output);
  return outputjs;
}

async function outputRunExpected(outputjs, expectedout) {
  expectedout = await fs.readFile(expectedout, 'utf8');
  oldLog = console.log;
  let result = '';
  console.log = (...s) => result += s.join(' ');
  eval(outputjs);
  assert.equal(removeSpaces(result), removeSpaces(expectedout));
  console.log = oldLog;
  return result;
}

async function main() {
  for (let i = 0; i < Test.length; i++) {
    let [t, ft] = [Test[i], Test[i].input];
    it(`Test ${i + 1}: ${ft}`, async () => {
      let outputjs = await transpile(ft, t.output);
      if (JSComparison) await outputProgramIsAsExpected(t, outputjs);
      await outputRunExpected(outputjs, t.correctOut);
    });
  }
}

main();

Para ejecutar los tests se debe ejecutar el siguiente script

npm run test

npm test

Se pueden añadir más tests en el fichero test-description.js y creando su entrada su código js esperado y su salida esperada en archivos dentro del directorio test/data/ del repo

Conclusiones

Con la implementación de la práctica se ha conseguido traducir expresiones aritméticas a JavaScript. Se ha utilizado Jison para generar el parser y se ha creado un AST con las funciones necesarias para construirlo. Se ha añadido soporte para funciones power y factorial que no están definidas en el código. Se ha creado un fichero template.js para añadir las dependencias solo cuando se necesiten. Se ha creado una función run que se encarga de ejecutar el código generado. Se ha automatizado la ejecución de los tests con Mocha.

Referencias

• Repo ULL-ESIT-GRADOII-PL/esprima-pegjs-jsconfeu-talk
• crguezl/hello-jison
• Espree
  • Options for parse and tokenize methods
• astexplorer.net demo
• idgrep.js
• Introducción a los Compiladores con Jison y Espree