PL 22/23

# Hello Compilers

Antes de emprender esta práctica, asegúrese de entender los dos ejemplos de parser generator en el repo crguezl/hello-jison (opens new window). Los ejemplos incluyen

  1. Un evaluador de expresiones aritméticas de restas (ficheros minus-ast.jison, minus.l y use-ast.js) y
  2. Un traductor a JS de expresiones aritméticas de restas (ficheros minus-ast.jison, ast-build.js, minus.l y use-ast.js)

# Two new operators & and @

Let us consider a notation of arithmetic in which the @ and & symbols on numbers are defined as the max and min operations. Thus, with this notation

and

Extienda el traductor de la calculadora para que admita estas expresiones aritméticas y las traduzca a un programa JavaScript que las compute y las imprima.

Supondremos que el mínimo & tiene mas prioridad que el máximo @. Por ejemplo, la entrada podría ser traducida al siguiente código JS:

console.log(max(234, min(325,57)))
1

Compared to the other tokens, give a low priority to the @ and & operators so that an expression 4!@3**2 should be interpreted as (4!)@(3**2) and produces a JS code as max(factorial("4"), pow("3", "2"))).

Como en la práctica anterior extienda el programa Jison hecho en la práctica anterior con estas dos operaciones para que produzca un AST compatible Espree conteniendo el correspondiente código JS. A continuación utilice escodegen.generate(ast) (opens new window) para generar el código JS

# Dealing with Ambiguity

For the & and @ operators you can extend the initial incomplete grammar in the assignment repo this way:

%{
const { buildLiteral, buildRoot, buildMin } = require('./ast-build');
%}

%%
es: e 
;

e: 
    e '@' e  
  | e '&' e  
  | N        
  | '(' e ')'
;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

The problem with this grammar is that it is ambiguous. Expressions like 2&3@4 have more than one concrete syntax tree.

On one side:

that will lead to the interpretation 2&(3@4); but we have also this other syntax tree:

that leads to the interpretation (2&3)@4.

Read the teacher notes on precedence and associativity (opens new window) and see the examples in the Repo crguezl/jison-prec (opens new window).

To break the ambiguity you have to set that the precedence of the token & is higher that the one of the token @.

You have also to fix the ambiguity for phrases like 2&3&4 and 3@4@5 favouring a left associativity interpretation, i.e. preferring (2&3)&4 to 2&(3&4) and (3@4)@5 to 3@(4@5).

# Breaking Ambiguity in Jison/Eyapp/Yacc/Bison et al. using token precedence

These is a simplified version of the rules to resolve conflicts and ambiguities in a Yacc-like parser generator:

Precedence Rules

  1. La precedencia de los tokens se hace en la cabecera del programa Jison; esto es: antes del primer %% usando la sintáxis %left token ... , %right token ... o %nonassoc token ...
  2. La precedencia de una regla de producción es la precedencia del último token que aparece en la parte derecha de la regla
    • Por ejemplo la precedencia de será la precedencia que le demos al token
  3. Cuando el parser detecta un conflicto y ve que hay dos posibles vias de continuar la construcción del árbol: Una que indica que quizá se aplicó la regla y otra que indica que quizá se pueda seguir leyendo el token a la entrada,
    1. El parser compara las precedencias del token y de la regla y se queda con el de mas prioridad.
    2. Si es el token quien tiene mayor prioridad avanzará en la lectura desplazando el token y buscando nuevos símbolos (se dice que hace un shift; en este caso probablemente el AST se "hundirá" a derechas) y
    3. Si es la regla completará el subárbol parcial y continuará en su construcción del árbol (se dice que hace un reduce y en este caso el árbol construido estará más hundido a izquierdas)
  4. Los tokens declarados en la misma línea mediante una declaración %left o %right tienen igual precedencia e igual asociatividad.
  5. La precedencia es mayor cuanto mas abajo su posición en el texto

Así, en nuestro ejemplo deberíamos poner:

... 

%left @
%left &
%%
es: e 
;

...
1
2
3
4
5
6
7
8
9

# Challenge: Complex Numbers

Extend the regular expressions in the lexical analyzer to cover both floating point real numbers like 2.53e-2 and floating point imaginary numbers like 2.9e-5i or -i.

The complex.js (opens new window) library provides a constructor Complex and methods mul, add, sub, div, etc. that can be used this way:

  let Complex = require('complex.js'); 
  let c = Complex({ re: 1.0e1, im: 8}); // Same: let c = Complex("1.0e1 + 8i");
  console.log(c); // { re: 10, im: 8 }
  console.log(c.mul({re: 2, im: 2}).div(2).sub(3, 2)); // { re: -1, im: 16 }
  console.log(c.add({re: 3, im: 9})); // { re: 13, im: 17 }
1
2
3
4
5

Write the code inserting the support functions and the require to complex.js (opens new window) lib in the preamble that is concatenated to the generated code.

# Redefining the minimum and maximum operators for complex numbers

When comparing Complex Number expressions, compare their modules. For example, the expression 2+3i<4+5i can be interpreted as

Complex("2").add("3i").abs() < Complex("4").add("5i").abs()
1

For real floating point numbers, this leads to the comparison of absolute values. For instance 2.3<-4.5 should be

Complex("2.3").abs() < Complex("4.5").neg().abs()
1

which is true.

Since & and @ have a lower priority than + and -, an expression like 4+5i&3-2i should be interpreted as (4+5i)&(3-2i).

# Redefining the factorial function

To keep compatibility with the calculator in the previous lab, you can extend the complex class with a factorial method like this:

#!/usr/bin/env node
const Complex = require("complex.js");

Complex.prototype.factorial = function() {
  if (this.im !== 0) throw new Error(`Imaginary part must be zero. Instead is ${this.im}`);
  let n = this.re;
  if (!Number.isInteger(n)) throw new Error(`Not an Integer number ${n}`);
  if ( n < 0) throw new Error(`Factorial of negative number ${n}`);
  let result = Complex(1);
  if (n === 0) return result;
  for (let i = 1; i <= n; i++) {
    result = result.mul(i);
  }
  return Complex({re: result.re, im: this.im});
};

console.log(Complex(process.argv[2]).factorial());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Here are several executions of the former example:

➜  complex-lib ./factorial.js "3"
{ re: 6, im: 0 }
➜  complex-lib ./factorial.js "3+2i"
Error: Imaginary part must be zero. Instead is 2
➜  complex-lib ./factorial.js "-3+0i"
Error: Factorial of negative number -3
➜  complex-lib ./factorial.js "-3.2+0i"
Error: Not an Integer number -3.2
1
2
3
4
5
6
7
8

The new version of the factorial function has to be added in the preamble of the generated code.

# The translation scheme

Thus your calc translator must be able to generate code for expressions like

2!+3**2i-4i
1

that using the complex library augmented with our factorial can be ultimately evaluated as:

Complex(2).factorial().add(Complex(3).pow("2i")).sub(Complex("4i"))
1

Using auxiliary proxy functions like sub, add, pow, etc. 2!+3**2i-4i can be translated as:

sub(add(factorial("2"), pow("3", "2i")), "4i")
1

which simplifies the AST and thus the translation.

An expression 4+5i&3-2i should be interpreted as (4+5i)&(3-2i) and can produce a JS code as min(add("4", "5i"), (sub("3", "2i"))).

# Pruebas

Añada pruebas usando Mocha y Chai o Jest

# 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.

# Ejemplos

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

Cuando vaya a escribir las pruebas de la práctica Hello Compilers podemos intentar una aproximación como esta:

  1. Tomamos un objeto como c = { text: "2@1&3", result: 2 } 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
  2. Construimos primero el árbol con t = p.parse(c.text)
  3. Generamos el JavaScript con js = escodegen.generate(t)
  4. Evaluamos el JavaScript con result = eval(js)
  5. 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 "2@1&3" nos han pedido que sea:

➜  hello-compilers-solution git:(master) ✗ ./bin/mmt.js '2@1&3'
console.log(Math.max(2, Math.min(1, 3)));
1
2

y si evaluamos el código resultante:

➜  hello-compilers-solution git:(master) ✗ node
Welcome to Node.js v16.0.0.
> result = eval("console.log(Math.max(2, Math.min(1, 3)));")
2
undefined
> result
undefined
1
2
3
4
5
6
7

¡La variable result está undefined!

Esto es así porque la llamada a console.log() siempre retorna undefined (no se confunda por el 2 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/maxmin.js").parser;
const escodegen = require("escodegen");
require("chai").should();

const Checks = [
  { text: "2@1&3", result: 2 },
  { text: "2@1@3", result: 3 },
  { text: "2&1&3", result: 1 },
  { text: "2&1@3", result: 3 },
  { text: "2&(1@3)", result: 2 },
];

describe("Testing hello maxmin 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;
    });
  }
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

No funcionaría porque lo que queda en result es undefined y no el resultado de Math.max(2, Math.min(1, 3)). En efecto, al ejecutar las pruebas obtenemos:

1) Testing hello maxmin translator
       Test 2@1&3 = 2:
     TypeError: Cannot read property 'should' of undefined
1
2
3

¿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;
    });
  }
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

➜  hello-compilers-solution git:(master) ✗ npm test

> hello-compilers@1.0.1 test
> npm run build; mocha


> hello-compilers@1.0.1 build
> jison src/maxmin-ast.jison src/maxmin.l -o src/maxmin.js



  Testing hello maxmin translator
    ✔ Test 2@1&3 = 2
    ✔ Test 2@1@3 = 3
    ✔ Test 2&1&3 = 1
    ✔ Test 2&1@3 = 3
    ✔ Test 2&(1@3) = 2


  5 passing (9ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Covering

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

Activate the GitHub pages of your repo (use the default branch and the docs folder) and be sure to include your covering report in the docs folder.

# Continuous Integration

Añada Integración contínua usando GitHub actions. Lea la sección GitHub Actions de los apuntes.

# References

# Essentials for this lab

# Jison and Syntax Analysis

# Have a look

Grading Rubric#

Comments#

Last Updated: 4 months ago