Translating Arithmetic Expressions to JavaScript

Objetivos

Usando Jison generalice el ejemplo en la carpeta ast del Repo hello-jison (opens in a new tab) constituido por los ficheros:

para escribir un programa que, recibiendo como entrada una cadena que contiene una secuencia de expresiones aritméticas de flotantes, produzca un AST compatible con el del parser espree (opens in a new tab). Use escodegen (opens in a new tab) para generar el código JavaScript correspondiente (vea ast2js.js (opens in a new tab)). Sigue un ejemplo de una posible ejecución.

Given an input file like this:

✗ cat test/data/test1.calc 
4 - 2 - 1

when we run the transpiler calc2js we get the following JavaScript code:

✗ bin/calc2js.mjs test/data/test1.calc 
console.log(4 - 2 - 1);

using a pipe we can execute the code:

✗ bin/calc2js.js test/data/test1.calc | node -
1

Las expresiones aritméticas deben soportar además de

suma,
resta,
multiplicación y
división,
el menos unario (ej.: -(2+3)*2)
un operador de factorial ! (factorial only supports an integer value as argument),
un operador de potencia ** (ej.: 2!**3!**2!) y
paréntesis.

El siguiente ejemplo muestra la traducción de una expresión aritmética que incluye los operadores de potencia y factorial:

➜  arith2js-solution git:(main) cat test/data/test-exp-fact.calc 
2**3!

La idea es construir una librería de soporte que incluya las funciones necesarias para que el código JavaScript generado pueda ser ejecutado:

➜  arith2js-solution git:(main) bin/calc2js.mjs test/data/test-exp-fact.calc 
const {factorial, power } = require("/Users/casianorodriguezleon/campus-virtual/2223/pl2223/practicas/arith2js/arith2js-solution/src/support-lib.js");
console.log(power(2, factorial(3)));

Nótese que el código generado importa las funciones factorial y power desde un fichero support-lib.js que se encuentra en la carpeta src en la que el compilador esté instalado.

➜  arith2js-solution git:(main) bin/calc2js.mjs test/data/test-exp-fact.calc | node -
64

Opciones en línea de comandos

Use commander (opens in a new tab) para procesar la línea de argumentos:

$ bin/calc2js.mjs --help
Usage: calc2js [options] <filename>
 
Arguments:
  filename                 file with the original code
 
Options:
  -V, --version            output the version number
  -o, --output <filename>  file in which to write the output
  -h, --help               display help for command

Dealing with Ambiguity

Para tratar con los temas de ambigüedad en la gramática, puede consultar

Conflict Solving in Yacc
la sección Precedencia y Asociatividad (opens in a new tab) de los viejos apuntes de PL
See the examples in the Repo crguezl/jison-prec (opens in a new tab).

Unary minus and exponentiation in escodegen

NOTE: The latest versions of escodegen support the exponentiation operator:

➜  arith2js-parallel-computing-group-parallel git:(essay-2023-02-15-miercoles) npm ls escodegen
hello-jison@1.0.0 /Users/casianorodriguezleon/campus-virtual/2223/pl2223/practicas/arith2js/arith2js-parallel-computing-group-parallel
└─┬ jison@0.4.18
  └── escodegen@1.3.3

➜  arith2js-parallel-computing-group-parallel git:(essay-2023-02-15-miercoles) npm i escodegen@latest
➜  arith2js-parallel-computing-group-parallel git:(essay-2023-02-15-miercoles) ✗ npm ls escodegen      
hello-jison@1.0.0 /Users/casianorodriguezleon/campus-virtual/2223/pl2223/practicas/arith2js/arith2js-parallel-computing-group-parallel
├── escodegen@2.1.0
└─┬ jison@0.4.18
  └── escodegen@1.3.3

➜  arith2js-parallel-computing-group-parallel git:(essay-2023-02-15-miercoles) ✗ node
Welcome to Node.js v21.2.0.
Type ".help" for more information.
> let  espree = require('espree')
> let ast3 = espree.parse('(-2)**2', { ecmaVersion: 7})
> let escodegen = require('escodegen')
> let gc = escodegen.generate(ast3) 
> gc
'(-2) ** 2;'

⚠️

Danger: Exponentiation is ECMAScript 2016

New Features in ECMAScript 2016: JavaScript Exponentiation (**) See for instance: https://www.w3schools.com/js/js_2016.asp (opens in a new tab) and https://262.ecma-international.org/7.0/ (opens in a new tab)

... This specification also includes support for a new exponentiation operator and adds a new method to Array.prototype called includes

Since the old version of escodegen do not support this Feature the combination of unary minus and exponentiation for those you an have:

➜  arith2js-parallel-computing-group-parallel git:(essay-2023-02-15-miercoles) ✗ node
Welcome to Node.js v18.8.0.
Type ".help" for more information.
> let  espree = require('espree')
> let ast = espree.parse('(-2)**2') // gives an error since the default compiler is ecma 5
Uncaught [SyntaxError: Unexpected token *
> let ast3 = espree.parse('(-2)**2', { ecmaVersion: 7}) // no errors. Right AST
> let escodegen = require('escodegen')
> let gc = escodegen.generate(ast3) // escodegen does not support this feature. The code generated is wrong
> gc
'-2 ** 2;'
> eval(gc) // the evaluation of the code produces errors
Uncaught:
SyntaxError: Unary operator used immediately before exponentiation expression. Parenthesis must be used to disambiguate operator precedence
> -2 ** 2 # JS does not accept this expression
-2 ** 2
^^^^^
Uncaught:
SyntaxError: Unary operator used immediately before exponentiation expression. Parenthesis must be used to disambiguate operator precedence
> (-2) ** 2  # ... But this code works 
4

Therefore, the following continuation of the former node session suggest the correct translation:

💡

> let ast5 = espree.parse('Math.pow(-2,2)')
undefined
> gc = escodegen.generate(ast5)
'Math.pow(-2, 2);'
> eval(gc)
4

Run time support

The run time support library is in the file src/support-lib.js: It is a library that exports those functions that are needed to run the generated code and are not part of the target language.

/practicas/arith2js/arith2js-solution/src/support-lib.js

const power = (n,m) => Math.pow(n, m) 
const factorial = n => (n === 0) ? 1 : n * factorial(n - 1)
 
module.exports = {
  power,
  factorial,
};

The generated code, if needed imports from the library the required functions. For instance, for the input:

➜  arith2js-solution git:(main) cat test/data/test-fact-fact.calc 
2!*3!

we get the following output code:

➜  arith2js-solution git:(main) bin/calc2js.mjs test/data/test-fact-fact.calc 
const { factorial } = require("/Users/casianorodriguezleon/campus-virtual/2223/pl2223/practicas/arith2js/arith2js-solution/src/support-lib.js");
console.log(factorial(2) * factorial(3));

and for the input:

➜  arith2js-solution git:(main) cat test/data/test2.calc            
9 - 6 - 3

we get the following output code:

➜  arith2js-solution git:(main) bin/calc2js.mjs test/data/test2.calc
console.log(9 - 6 - 3);

Notice how the require is not inserted in the output code, since it is not needed.

To achieve this goal we add a template file src/template.js:

/practicas/arith2js/arith2js-solution/src/template.js

➜  arith2js-solution git:(main) cat src/template.js 
const { {{ dependencies }} } = require("{{root}}/src/support-lib.js");
{{code}}

the variables {{ dependencies }} and {{ code }} are replaced with the required function names and the code generated from the AST. The variable {{ root }} is replaced with the path to the place where the arith2js compiler will be installed.

You can implement your own JS templates or use one of the many available:

Computing the dependencies

We can find the dependencies of the generated code by traversing the AST and collecting the names of the functions that are not part of the target language. We can use espree.estraverse for that:

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

Where exportedSupportIdentifiers is an array with the names of the functions exported by the support library:

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

Tests

Add tests to this project using mocha

The test folder contains the data folder with the input and expected output files, the test-description.mjs and the test.mjs files.

✗ tree test 
test
├── data
│   ├── correct-out1.txt
│   ├── correct-out2.txt
│   ├── correct1.js
│   ├── correct2.js
│   ├── test1.calc
│   └── test2.calc
├── test-description.mjs
└── test.mjs

The workflow is that for each feature we add an input file test/data/test2.calc:

➜  arith2js-solution git:(dependencies) ✗ cat test/data/test2.calc 
9 - 6 - 3

then we run the transpiler calc2js and check the output:

➜  arith2js-solution git:(dependencies) ✗ bin/calc2js.mjs test/data/test2.calc    
#!/usr/bin/env node
console.log(9 - 6 - 3);

Since it looks good we save it as a correctXX.js file:

➜  arith2js-solution git:(dependencies) ✗ bin/calc2js.mjs test/data/test2.calc -o test/data/correct2.js

We then run the output program and check the logged output is what expected:

➜  arith2js-solution git:(dependencies) ✗ node test/data/correct2.js 
0

Since it looks good we save the output as a correct-outXX file:

➜  arith2js-solution git:(dependencies) ✗ node test/data/correct2.js > test/data/correct-out2.txt

We add the new test to the test-description.mjs file and then run the new test:

➜  arith2js-solution git:(dependencies) ✗ npx mocha --grep 'test2' 


  ✔ transpile(test2.calc, out2.js)

  1 passing (14ms)

The tests are in the test folder. The file test.mjs starts importing the necessary modules and the test-description.mjs file:

/practicas/arith2js/arith2js-solution/test/test.mjs

import transpile from "../transpile.js";
import assert from 'assert';
import * as fs from "fs/promises";
import { dirname } from 'path';
import { fileURLToPath } from 'url';
 
const __dirname = dirname(fileURLToPath(import.meta.url));
import Tst from './test-description.mjs';

We import in Tst the module test-description.mjs that contains the list of objects describing the tests: input file, expected javascript output, etc.:

/practicas/arith2js/arith2js-solution/test/test-description.mjs

export default [
  {
    "input": "test1.calc",
    "output": "out1.js",
    "expected": "correct1.js",
    "correctOut": "correct-out1.txt"
  },
  ...
  {
    "input": "test-power-power.calc",
    "output": "out-power-power.js",
    "expected": "correct-power-power.js",
    "correctOut": "correct-out-power-power.txt"
  }
];

The test file test.mjs contains the code to run the tests: traspiles each input file, checks the JS output is the expected and runs the JS output program and checks the logged output is what expected:

/practicas/arith2js/arith2js-solution/test/test.mjs

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,
})
)
 
function removeSpaces(s) {
  return s.replace(/\s/g, '');
}
 
for (let i = 0; i < Test.length; i++) {
  it(`transpile(${Tst[i].input}, ${Tst[i].output})`, async () => {
 
    // Compile the input and check the output program is what expected
    await transpile(Test[i].input, Test[i].output);
    let output = await fs.readFile(Test[i].output, 'utf-8')
    let expected = await fs.readFile(Test[i].expected, 'utf-8')
    assert.equal(removeSpaces(output), removeSpaces(expected));
    await fs.unlink(Test[i].output);
 
    // Run the output program and check the logged output is what expected
    let correctOut = await fs.readFile(Test[i].correctOut, 'utf-8')
    let oldLog = console.log; // mocking console.log
    let result = "";
    console.log = function (...s) { result += s.join('') }
      eval(output);
      assert.equal(removeSpaces(result), removeSpaces(correctOut))
    console.log = oldLog;
  });
}

Testing erroneous input files

In an analogous way, you can add testing for erroneous input files.

➜  arith2js-solution git:(main) ls test/*error*
test/test-error-description.js test/test-error.js

For instance, the file test/data/test-err.calc contains an erroneous input:

➜  arith2js-solution git:(main) cat test/data/test-err.calc 
2*(-3!!
➜  arith2js-solution git:(main) bin/calc2js.mjs test/data/test-err.calc 
Parse error on line 1:
2*(-3!!
-------^
Expecting '-', '+', '*', '/', ')', '**', '!', got '1'

Which is tested by the file test/test-error.js:

➜  arith2js-solution git:(main) npx mocha --grep err test/test-error.js 
  ✔ transpile(test-err.calc, outerr.txt)
  1 passing (8ms)

Mocking

Mocking means creating a fake version of an external or internal service that can stand in for the real one, helping your tests run more quickly and more reliably. When your implementation interacts with an object’s properties, rather than its function or behavior, a mock can be used.

Stubbing

Stubbing, like mocking, means creating a stand-in, but a stub only mocks the behavior, but not the entire object. This is used when your implementation only interacts with a certain behavior of the object.

To give an example: You can stub a database by implementing a simple in-memory structure for storing records. The object under test can then read and write records to the database stub to allow it to execute the test. This could test some behaviour of the object not related to the database and the database stub would be included just to let the test run.

If you instead want to verify that the object under test writes some specific data to the database you will have to mock the database. Your test would then incorporate assertions about what was written to the database mock.

Examples of Mocking and Stubbing

See the code at ast/test/test.mjs (opens in a new tab) in the repo hello-jison for an example of stubbing the console.log.

Cuando vaya a escribir las pruebas de la práctica podemos intentar una aproximación como esta: ➜ arith2js-solution git:(dependencies) ✗ cat test/data/test1.calc

Tomamos un objeto como c = { text: "3! - 1", result: 5 } con el atributo text conteniendo la expresión de prueba y el atributo result el resultado esperado después de la traducción y evaluación del código
Construimos primero el árbol con t = p.parse(c.text)
Generamos el JavaScript con js = escodegen.generate(t)
Evaluamos el JavaScript con result = eval(js)
Si nuestro traductor es correcto result debería ser igual c.result

Suena bien ¿Verdad?

Pero en tal aproximación ¡tenemos un problema! y es que el código JavaScript generado para "3! - 1" nos han pedido que sea:

➜  arith2js-solution git:(dependencies) ✗ cat test/data/test1.calc 
3! - 1                                                                                                        
➜  arith2js-solution git:(dependencies) ✗ bin/calc2js.mjs test/data/test1.calc 
#!/usr/bin/env node
const factorial = n => (n === 0) ? 1 : n * factorial(n - 1);
console.log(factorial(3) - 1);

y si evaluamos el código resultante:

➜  arith2js-solution git:(dependencies) ✗ node                                
Welcome to Node.js v16.0.0.
Type ".help" for more information.
> result = eval(`const factorial = n => (n === 0) ? 1 : n * factorial(n - 1);
... console.log(factorial(3) - 1);`)
5
undefined
> result
undefined

¡La variable result está undefined!

Esto es así porque la llamada a console.log() siempre retorna undefined (no se confunda por el 5 que aparece en stdout producido por el console.log. El valor retornado es undefined)

Así pues una aproximación como esta no funcionaría:

const p = require("../src/transpile.js").parser;
const escodegen = require("escodegen");
require("chai").should();
 
const Checks = [
  { text: "2+3*2", result: 8 },
  { text: "4-2-1", result: 1 },
];
 
describe("Testing translator", () => {
  for (let c of Checks) {
    it(`Test ${c.text} = ${c.result}`, () => {
      const t = p.parse(c.text);
      const js = escodegen.generate(t);
      const result = eval(js);
 
      result.should.equal(c.result);
      
      console.log = oldLog;
    });
  }
});

No funcionaría porque lo que queda en result es undefined y no el resultado de 2+3*2. ¿Cómo arreglarlo?

¡El patrón de Stubbing al rescate!

Sustituyamos el método log del objeto console con nuestra propia función adaptada a nuestras necesidades de testing console.log = x => x; que retorna el valor del argumento pasado a console.log. De esta forma podemos acceder al valor de la evaluación de la expresión:

it(`Test ${c.text} = ${c.result}`, () => {
      let oldLog = console.log;
      console.log = x => x;
 
      const t = p.parse(c.text);
      const js = escodegen.generate(t);
      const result = eval(js);
 
      result.should.equal(c.result);
      
      console.log = oldLog;
    });
  }
});

Ahora result contiene la evaluación de la expresión y las pruebas funcionan.

Covering

You can use nyc (opens in a new tab) to do the covering of your mocha tests. See the notes in covering.

Activate the GitHub pages (opens in a new tab) of your repo (use the default branch and the docs folder) and be sure to include your covering report (use --reporter=html --report-dir=docs options) in the docs folder.

✗ npm run cov

> hello-jison@1.0.0 cov
> nyc npm test


> hello-jison@1.0.0 test
> npm run compile; mocha test/test.mjs


> hello-jison@1.0.0 compile
> jison src/grammar.jison src/lexer.l -o src/calc.js



  ✔ transpile(test1.calc, out1.js)
  ✔ transpile(test2.calc, out2.js)
  ✔ transpile(test3.calc, out3.js)

  3 passing (20ms)

--------------|---------|----------|---------|---------|-----------------------------------------
File          | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s                       
--------------|---------|----------|---------|---------|-----------------------------------------
All files     |   58.92 |    45.83 |   47.22 |   56.63 |                                         
 ast-build.js |     100 |      100 |     100 |     100 |                                         
 calc.js      |   57.44 |    45.78 |   40.62 |   54.92 | ...,530-539,548-569,578,580,602-607,610 
 transpile.js |   81.81 |       50 |     100 |   81.81 | 11-12                                   
--------------|---------|----------|---------|---------|-----------------------------------------

Read the chapter Creating and Publishing an npm Module and namely the sections

Videos

Este vídeo del 14 de Febrero de 2024 explica como hacer parte de la práctica arith2js:

También puede ver los vídeos del 14, 15 y 22 de febrero de 2023, que contienen explicaciones para la práctica arith2js:

Rubric

arith2js Repos

References

Essentials for this lab

See the examples in the repo crguezl/hello-jison (opens in a new tab)
https://astexplorer.net (opens in a new tab)
Tipos de Nodos del AST y nombres de las propiedades de los hijos
Escodegen repo en GitHub (opens in a new tab)
- Escodegen API Doc (opens in a new tab)
Jison Documentation (opens in a new tab)

Jison and Syntax Analysis

Have a look

Testing

Hello Compiler IAAS