3º. 2º cuatrimestre. Itinerario de Computación. Grado en Ingeniería Informática. ULL
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: expresiones regulares, hashes, arrays multidimensionales, módulos, objetos, clases, … y se construyen sobre esta.
Primero: Deberá leer el capítulo 12 A Programming Language de EJS:
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
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.
En algunos de los ejemplos, vídeos, 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.
Haga este ejercicio para determinar la gramática del lenguaje Egg:
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?
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
Resuelva ahora los dos ejercicios propuestos en el capítulo:
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/. 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.
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 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
El programa egg deberá ejecutar el programa .egg que se le pasa por línea de comandos:
$ cat one.egg
do(
define(x, 4),
define(setx, fun(val,
set(x, val)
)
),
setx(50),
print(x)
)
$ egg one.egg
50
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:
El intérprete evm ejecuta los ficheros en formato Egg Virtual Machine.
[~/.../crguezl-egg(master)]$ bin/evm.js examples/two.egg.evm
4
6
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.
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 tabié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 de la ejecución del programa test/examples/objetivo.egg es igual a los contenidos de test/examples/objetivo.egg.expected.
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)
Use GitHub Actions para añadir CI al proyecto
Publique el compilador como módulo en GH Registry en el ámbito @ULL-ESIT-PL-1920.
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"
}
Si logra resolver estos objetivos ¡Enhorabuena!.
Puede encontrar una solución a algunos de los problemas planteados en este repo ULL-ESIT-PL-1617/egg.
Asegúrese que entiende como funciona.
También puede encontrarlo como módulo en npm @crguezl/eloquentjsegg
A continuación mejore el analizador léxico que encuentra en este repo como sigue:
offset de comienzo, la línea de comienzo, etcsticky. Estudie esta mejoraHaga 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
> # Pulsamos CTRL-D
> goodbye!
En este Vídeo Programando un bucle REPL para el lenguaje Egg explicamos como hacerlo
readline para hacer un bucle interactivo. Quizá conviene que lo leas cuando llegues a la sección del problema del REPL