Egg. A Programming Language

Introducción

Esta es la primera práctica de una serie de prácticas sobre las fases de análisis sintáctico, el análisis de ámbito y la interpretación del codigo. Se presenta un lenguaje llamado Egg (de tipo “Lisp”) y se describe como procesarlo e interpretarlo. Las siguientes prácticas irán ampliando el lenguaje con nuevas capacidades:

arrays multidimensionales,
hashes,
módulos (require),
objetos,
clases,
expresiones regulares,
asincronía,
…

y se construyen sobre esta.

Primero: Deberá leer el capítulo 12 A Programming Language de EJS:

Eloquent JS. Chapter 12. Project: A Programming Language

Lea cuidadosamente el capítulo intentando comprender como funcionan las dos fases: la primera con el análisis sintáctico que produce el AST y la segunda en la que se ejecuta el AST.

Es fundamental que llegue a dominar las bases que se asientan en esta capítulo. Son un montón de conceptos. No desespere si al principio todo es un poco confuso. Si tal cosa ocurre puede que le ayude dejar por un momento la lectura y pasar a leer primero las secciones

Escriba la gramática y
Introducción al Análisis Sintáctico Predictivo Recursivo

Después de estas dos lecturas vuelva otra vez a la lectura del capítulo Chapter 12. Project: A Programming Language. No haga todavía los ejercicios del libro.

Nota de Advertencia

En algunos de los ejemplos, vídeos, repos, etc. que acompañan esta práctica puede notar algunas inconsistencias en el lenguaje Egg debidas a que casi en cada curso hemos ido haciendo alias de algunos de los nombres de los constructos. Por ejemplo, a veces en un vídeo en vez de fun usamos -> y en algún ejemplo en los apuntes en vez de element se usa <-, etc. También en algún ejemplo aparecen llavitas { y } en vez de paréntesis (de nuevo una llave aquí es un alias del correspondiente paréntesis). Son cambios triviales que no deberían afectar a la comprensión del texto.

Metodología de Trabajo

Sugerencia de metodología:

Trabaje siempre en la misma working copy. Para cada práctica añada nuevos remotos git remote add practica-egg-XXX-super <url> etc.
Añade al board del super repo una columna Revisados por el profesor en la que se pondrán los objetivos alcanzados a los que el profesor le ha dado el visto bueno
Cuando el profesor da el visto bueno:
- los movemos a la columna Revisados del board de la práctica
- Cerramos la incidencia que habíamos creado para ese objetivo

Escriba la Gramática

Haga este ejercicio para determinar la gramática del lenguaje Egg:

Ejercicio

Escriba en su README.md las reglas de producción de la gramática que reconoce el traductor

Tiene una posible solución aquí

¿Es correcto este diseño de la gramática?

Gramática modificada

Análisis Sintáctico Predictivo Recursivo

Lea esta breve introducción a como se escribe un analizador Sintáctico Predictivo Recursivo como el que se construye en el capítulo 12 A Programming Language de EJS:

Análisis Sintáctico Predictivo Recursivo

Árboles de Análisis Abstracto

Fixing Scope

Resuelva ahora los dos ejercicios propuestos en el capítulo:

Comments y
Fixing Scope

Si no se le ocurre como resolver el segundo apartado, Fixing Scope, no desespere. Es un ejercicio muy difícil. Inténtelo mas de una vez.

Puede encontrar una solución al problema en la rama inicial de este repo ULL-ESIT-PL-1617/egg/. La rama inicial como su nombre indica contiene además del código descrito en el capítulo de EloquentJS las soluciones a los ejercicios propuestos en el capítulo del libro.

Si no se le ocurre una solución acuda a este enlace. Y si se le ocurrió también. Contraste las soluciones y quédese con la que le parezca mejor.

Analizador Léxico Separado

Intente ahora separar la fase de análisis sintáctico de la fase de análisis léxico en una función separada lex que cada vez que es llamada por las funciones parseExpression y parseApply retorna el siguiente token.

Esto es, a diferencia de en los ejemplos vistos en las clases anteriores, el analizador léxico no analiza todos los tokens en una pasada guardándolos en un array, sino que tan pronto como detecta el siguiente token lo devuelve a la rutina de análisis sintáctico que le ha llamado.

let lookahead;
let lineno = 1; // Save token line numbers
let offset = 0; // Save token offset
...
function lex() {
  let match;
  ... // Find the next token and save it in lookahead 
  return lookahead;
}

Se usará una variable compartida que se debe llamar lookahead para guardar el token actual. Esta variable lookahead sirve para la comunicación entre las funciones de análisis sintactico y el analizador léxico. El código de parseExpressiondebería quedar parecido a esto:

function parseExpression() {
  let expr;

  if (lookahead.type == "STRING") {
    expr = {type: "value", value: lookahead.value};
    lex();
    return expr;
  } else if (lookahead.type == "NUMBER") {
    expr = {type: "value", value: lookahead.value};
    lex();
    return expr;
  } else if (lookahead.type == "WORD") {
    expr = {type: "word", name: lookahead.value};
    lex();
    return parseApply(expr);
  } else {
    throw new SyntaxError(`Unexpected syntax line ${lineno}: ${program.slice(0,10)}`);
  }
}

Separe en Módulos el Programa

Separe el código en dos módulos Node.js:

lib
├── eggvm.js
└── parse.js

parse.js debe contener las funciones del análisis léxico y sintáctico y exportarlas

[~/.../crguezl-egg(master)]$ tail -n 9 lib/parse.js

module.exports = {
  ...
  parse,
  parseApply,
  parseExpression,
  parseFromFile,
};

eggvm.jsdebe contener todo el código relativo al entorno de ejecución. Este módulo debería exportar funciones para la ejecución del árbol generado en la primera fase como run, runFromFile, runFromEVM:
```
[~/.../crguezl-egg(master)]$ tail -n 1 lib/eggvm.js
```
```
module.exports = {
  run, 
  runFromFile, 
  runFromEVM, 
  topEnv, 
  specialForms, 
  parser, 
  evaluate
};
```

Añada también tres ejecutables que usan los módulos anteriores:

[~/.../crguezl-egg(master)]$ tree bin
bin
├── egg.js
├── eggc.js
└── evm.js

egg

El programa egg deberá ejecutar el programa .egg que se le pasa por línea de comandos:

$ cat examples/one.egg
do(
  define(x, 4),
  define(setx, fun(val, 
      set(x, val)
    )
  ),
  setx(50),
  print(x)
)
$ bin/egg.js examples/one.egg
50

eggc

Compiles the input program to produce a JSON containing the tree: eggc examples/two.egg produces the JSON file examples/two.egg.evm

Por ejemplo, si le damos como entrada este programa:

[~/.../crguezl-egg(master)]$ cat examples/two.egg

do(
  define(sum,  # function
    fun(nums, other,
      do(
         print(other),
         define(i, 0),
         define(sum, 0),
         while(<(i, length(nums)),
           do(define(sum, +(sum, element(nums, i))),
              define(i, +(i, 1))
           )
         ),
         sum
      )
   )
 ),
 print(sum(array(1, 2, 3), 4))
)

Si ejecutamos bin/eggc.js examples/two.egg produce como salida un fichero con el mismo nombre y extensión .evm (por Egg Virtual Machine) que no es otra cosa que el AST generado por el parser guardado como un objeto JSON.

[~/.../crguezl-egg(master)]$ bin/eggc.js examples/two.egg
[~/.../crguezl-egg(master)]$ ls -ltr examples/two.egg.evm
-rw-r--r--  1 casiano  staff  7466  2 abr 11:03 examples/two.egg.evm

Puede ver los contenidos del JSON generado en la ejecución de ejemplo en este enlace:

examples/two.egg.evm

evm

El intérprete evm ejecuta los ficheros en formato Egg Virtual Machine.

[~/.../crguezl-egg(master)]$ bin/evm.js examples/two.egg.evm
4
6

Examples folder

Añada una carpeta examples en la que guardará los ejemplos con los que va comprobando la funcionalidad de su compilador:

[~/.../crguezl-egg(master)]$ tree examples/ -I '*evm'
examples/
├── array.egg
├── greater-x-5.egg
├── if.egg
├── ...
└── two.egg

Cada vez que introduzca una nueva funcionalidad cree uno o varios ejemplos que sirvan para ilustrarla y comprobar el buen funcionamiento.

Por ejemplo, cuando trabajemos en la tarea Fixing Scope podemos añadir a nuestro directorio examples un par de ejemplos que ilustran como debería funcionar.

Uno que produzca una excepción:

[~/.../crguezl-egg(private2019)]$ cat examples/scope-err.egg
do(
  set(x,9),
  print(x) # ReferenceError: Tried setting an undefined variable: x
)

y al menos otro que muestre como unas variables ocultan a otras:

[~/.../crguezl-egg(private2019)]$ cat examples/scope.egg
do(
  def(x,9),
  /* def crea una nueva variable local */
  def(f, fun{
    do{
      def(x, 4),
      print(x) # 4
    }
  }),
  /* set no crea una nueva variable local */
  def(g, fun{set(x, 8)}),
  f(),
  print(x), # 9
  g(),
  print(x) # 8
)

Conforme programamos, vamos ejecutando nuestra solución contra estos programas. Cuando tengamos la solución correcta la salida debería ser algo así:

[~/.../crguezl-egg(private2019)]$ bin/egg.js examples/scope-err.egg
ReferenceError: Tried setting an undefined variable: x

[~/.../crguezl-egg(private2019)]$ bin/egg.js examples/scope.egg
4
9
8

Uno de nuestros objetivos es reciclar esos ejemplos en las pruebas y en la documentación.

Test Folder

Añadimos una carpeta test y en ella los programas de prueba test/test.js (Mocha o Jest, use lo que prefiera. Los ejemplos que siguen están en Mocha).

Creamos también un subdirectorio test/examples en el que copiamos nuestro ejemplo de prueba:

cp examples/scope.egg test/examples/

y junto a el escribimos un fichero con la salida esperada test/examples/scope.egg.expected.

Una estructura como esta:

test/
├── examples
│   ├── scope.egg
│   └── scope.egg.expected
└── test.js

Cada vez que logramos implementar una nueva funcionalidad o un nuevo objetivo añadimos en el directorio examples uno o varios programas examples/objetivo.egg cuya ejecución muestra el buen funcionamiento de nuestro código. También lo añadimos a test/examples/objetivo.egg así como la salida esperada test/examples/objetivo.egg.expected.

De esta forma la prueba se reduce a comprobar que la salida (stdout/stderr) de la ejecución del programa test/examples/objetivo.egg es igual a los contenidos de test/examples/objetivo.egg.expected.

Procura evitar que la salida sea dependiente de la versión de node.js o del Sistema Operativo.

Puede usar el módulo @ull-esit-pl/example2test para simplificar esta metodología

[~/.../test(private2019)]$ cat scopes.js

let fs = require('fs');
let should = require("should");
let e2t = require('@ull-esit-pl/example2test');
let eggvm = require('../lib/eggvm.js');

describe("Testing scopes", function() {
  let runTest = (programName, done) => {
    e2t({
      exampleInput: programName + '.egg',
      executable: 'node bin/egg.js',
      assertion: (result, expected) => result.replace(/\s+/g,'').should.eql(expected.replace(/\s+/g,'')),
      done: done,
    });
  };

  it("should  not allow the use of non declared variables", function() {
    let program = fs.readFileSync('examples/scope-err.egg', 'utf8');
    (() => { eggvm.run(program); }).should.throw(/setting.+undefined.+variable/i);
  });

  it("testing scope.egg", function(done) {
    runTest('scope', done);
  });
});

Como se puede apreciar, el objeto eggvm exportado por el módulo lib/eggvm.js dispone de un método run que ejecuta la cadena que se le pasa como entrada.

No olvides ejecutar todas las pruebas npm test cada vez que resuelves un nuevo objetivo

[~/.../crguezl-egg(private2019)]$ npx mocha test/scopes.js
  Testing scopes
    ✓ should  not allow the use of non declared variables
    ✓ testing scope.egg (138ms)
  2 passing (151ms)

Continuous Integration

Use GitHub Actions para añadir CI al proyecto

GitHub Registry

Publique el compilador como módulo en GH Registry en el ámbito @ULL-ESIT-PL-2021.

Puesto que este paquete contiene ejecutables es conveniente que lea la sección bin de la documentación de npm.js sobre package.json:

[~/.../crguezl-egg(master)]$ jq .bin package.json

{
  "egg": "./bin/egg.js",
  "eggc": "./bin/eggc.js",
  "evm": "./bin/evm.js"
}

Solución Parcial

Si logra resolver estos objetivos ¡Enhorabuena!.

Puede encontrar una solución a algunos de los problemas planteados en esta práctica en la rama master de este repo ULL-ESIT-PL-1617/egg.

Asegúrese que entiende como funciona.

También puede encontrarlo como módulo en npm @crguezl/eloquentjsegg

Mejoras en el Analizador Léxico

A continuación mejore el analizador léxico que encuentra en la rama master de ULL-ESIT-PL-1617/egg como sigue:

Guarde en el objeto token el offset de comienzo, la línea de comienzo, etc
Mejore los mensajes de error usando esta información
El analizador léxico actual destruye la cadena conteniendo el programa conforme la analiza. Es posible escribir una analizador léxico que recorra la cadena conteniendo el programa sin destruirla usando la opción sticky. Estudie esta mejora
Mejore las pruebas, especialmente con programas que contienen errores

Bucle REPLpara egg (Repeat Evaluate Print Loop)

Haga que el ejecutable egg funcione como un bucle REPL cuando no se le proporciona un fichero de entrada.

[~/ull-pl1718-campus-virtual/tema3-analisis-sintactico/src/egg/crguezl-egg(private)]$ bin/egg.js
> def(x, array(1,2,array(3,4))) # x = [1,2,[3,4]]
[ 1, 2, [ 3, 4 ] ]
> <-(x,2) # 3d element
[ 3, 4 ]
> <-(x,0) # 1st element
1
> +(2, # No completamos la expresión: espera
> ..*(3, # Sigue incompleta
> ....4)
> ..) # cerramos: evalúa
14
> # Pulsamos CTRL-D
> goodbye!

En este Vídeo Programando un bucle REPL para el lenguaje Egg explicamos como hacerlo

Recursos

Eloquent JS: Chapter 11. Project: A Programming Language
El lenguaje egg: repo en GitHub. Contiene una solución a los problemas de separar el analizador léxico del sintáctico así como al de separar los códigos y los tres ejecutables. También tiene ejemplos de pruebas en Mocha y Chai
NodeJS Readline gist: un sencillo gist que te enseña a usar readline para hacer un bucle interactivo. Quizá conviene que lo leas cuando llegues a la sección del problema del REPL
En el repo ULL-ESIT-PL-1617/interpreter-egg se muestra como hacer un bucle REPL
Vídeo Programando un bucle REPL para el lenguaje Egg
XRegExp
El módulo @ull-esit-pl/example2test
Tests. Mocking and Stubbing
- Sinon API
- Side effects of stubbing console in tests
- Unit Test like a Secret Agent with Sinon.js by Elijah Manor
VSCode Extension Egg Tools: Adds syntax highlighting and code snippets for the Egg language by EloquentJS

Rúbrica

Incidencias para el Project Board para la práctica Egg. A Programming Language

Documentación
1. Gramática documentada y se corresponde con el compilador
2. ASTs documentados y se corresponden
3. Documentación del módulo npm (API) y ejecutables como se usan
4. Opcional: Documentación de la API de los módulos (parser, eggvm), informe de cubrimiento, etc.
set (asignación y manejo de ámbitos)
Analizador Léxico
1. Sticky
2. Comentarios
3. Localización
Librerías separadas para el Parser y el Intérprete
Interfaz (exports) del Parser y del Intérprete
Ejecutables
1. Runner: egg.js. Funcionamiento, documentación de uso, ayuda, etc.
2. Compiler: eggc.js. Funcionamiento, documentación de uso, ayuda, etc.
3. Virtual Machine: eggvm.js. Funcionamiento, documentación de uso, ayuda, etc.
Pruebas
1. Se provee una carpeta examples con ejemplos de programas egg`
2. Se ha automatizado el proceso de pasar del “ejemplo que funciona” a “test unitario que prueba que funciona”
3. Se hace integración contínua
Se ha publicado en GitHub Registry
1. La publicación cumple los estándares de publicación de un módulo (CI, versionado, documentación, etc.)
El bucle REPL
1. Evalúa correctamente y no se despista
2. Detecta expresiones incompletas
3. Colores

Share on

Whatsapp Twitter Facebook LinkedIn

✏️