PL 21/22

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

# Descripción de la Tarea

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

Escriba un traductor de estas expresiones aritméticas 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 debería ser traducida al siguiente código JS:

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

Para ello

  1. Escriba un programa Jison que produzca un AST compatible Espree conteniendo el correspondiente código JS. A continuación
  2. Utilice escodegen.generate(ast) (opens new window) para generar el código JS

# Paréntesis

Añada paréntesis al lenguaje para que se pueda alterar la prioridad por defecto. Por ejemplo

debería traducirse por:

console.log(Math.min(3, Math.max(22, 4)));
1

# Challenge: Floats

Extend the regular expression in the lexical analyzer to cover floating point numbers like 2.53e-3 or 3e2.

# Dealing with Ambiguity

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

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

# Ejemplo de Stubbing en la práctica "Hello Compilers"

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#

#Labs

  1. Task GitHub-AluXXXX Form
  2. Lab GitHub Campus Expert
  3. Lab GitHub Project Board
  4. Lab GitPod and Visual Studio Code
  5. Lab IAAS
  6. Lab Espree Logging
  7. Lab Hello Compilers
  8. Lab Constant Folding
  9. Lab ast-types
  10. Lab egg-parser
  11. Lab Lexer Generator
  12. Lab The Egg Interpreter
  13. Lab Adding OOP to the Egg Parser
  14. Lab Extending the Egg Interpreter
  15. Lab TFA: Final Project PL
  16. Task Training Exam for PL

Comments#

Last Updated: 10 months ago

← Constant Folding →