Lab Introduction to Scope Analysis
Véase el lab scope-intro
Introducción
El objetivo de esta práctica es de el ampliar la calculadora que hemos estado desarrollando hasta este momento. Así mismo en esta práctica hemos vuelto a visitar conceptos cómo son el manejo del AST, el como hacer grámaticas, testing, etc... Todo con el fin de poder añadir números complejos a nuestra calculadora
Compilación de la calculadora
De cara a gestionar la calculadora es necesario explicar una serie de ficheros, de los cuales me centraré en los más importantes, siendo estos:
lexer.l
%{ const reservedWords = ["print","i"]
const idOrReserved = text => { if (reservedWords.find(w => w == text)) return text; return 'ID'; } %} number [0-9]+(.[0-9]+)?([eE][+-]?[0-9]+)?"i"?|"i"
%% \s+ ; {number} return 'N'; [a-zA-Z_]\w* return idOrReserved(yytext); '' return ''; [-=+*/!(),@&] return yytext;
Comenzando estaría el fichero lexer.l, este se ha modificado con el objetivo de poder ampliar la antes mencionada calculadora. Para ello se ha cambiado la expresión regular que gestionaba los números para que esta ahora pudiese localizar número complejos tambíen.
Así mismo se ha empleado un array llamado 'reservedWords' el cual conserva los nombres de aquellas palabras que se consideran reservadas, tales cómo la 'i' (de los números complejos), cómo de la palabra print, con la que poder imprimir. Todo ello gestionado a través de la función idOrReserverd, la cual recibe cualquier texto que caze con su exprexión regular ([a-zA-Z_]\w*) y en caso de coincidir con la antes mencionada reservedWords es almacenado.
grammar.jison
%{
const {
buildRoot,
buildBinaryExpression,
buildLiteral,
buildCallExpression,
buildIdentifier,
buildAssignmentExpression,
buildSequenceExpression,
buildCallMemberExpression,
buildMax,
buildMin,
} = require('./ast-build');
const {$} = require('./utils.js')
%}
%left ','
%right '='
%left '@'
%left '&'
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
%right '**'
%left '!'
%%
es: e { return { ast: buildRoot($e) }; }
;
e:
e ',' e { $$ = buildSequenceExpression([$e1, $e2]) }
| ID '=' e { $$ = buildAssignmentExpression($($ID), '=', $e); }
| e '@' e { $$ = buildMax($e1, $e2, true); }
| e '&' e { $$ = buildMin($e1, $e2, true); }
| e '-' e { $$ = buildCallMemberExpression($e1, 'sub', [$e2]); }
| e '+' e { $$ = buildCallMemberExpression($e1, 'add', [$e2]); }
| e '*' e { $$ = buildCallMemberExpression($e1, 'mul', [$e2]); }
| e '/' e { $$ = buildCallMemberExpression($e1, 'div', [$e2]); }
| e '**' e { $$ = buildCallMemberExpression($e1, 'pow', [$e2]); }
| '(' e ')' { $$ = $2; }
| '-' e %prec UMINUS { $$ = buildCallMemberExpression($e, 'neg', []); }
| e '!' { $$ = buildCallExpression('factorial', [$e], true); }
| N { $$ = buildCallExpression('Complex',[buildLiteral($N)], true); }
| print '(' e ')' { $$ = buildCallExpression('print', [$e], true)}
| ID { $$ = buildIdentifier($($1));}
;
El fichero que se puede ver en este apartado es en el que queda reflejada la grámatica de la calculadora. Este es igual al de la práctica anterior, con la diferencia de que ahora se tiene en cuenta el ID del identificador que estamos recibiendo y se cuenta con una línea exclusiva para usar el método print:
| print '(' e ')' { $$ = buildCallExpression('print', [$e], true)}
| ID { $$ = buildIdentifier($($1));}
Por otro lado las funciones que se nos pedía desarrollar en este apartado eran principalmente las de buildRoot y de build literal, las cuales serán explicadas a continuación.
ast-build.js
De cara al siguiente fichero me gustaría destacar solo las funciones que se nos pidió realizar y que mencionamos anteriormente. Siendo estas las siguientes:
function buildRoot(child) {
return {
type: "Program",
body: [
{
type: "ExpressionStatement",
expression: child,
},
],
sourceType: "script",
};
}
function buildLiteral(value) {
return {
type: "Literal",
value: String(value),
raw: `"${value}"`,
};
}
Dichas funciones son efectivamente buildRoot y buildLiteral respectivamente. BuildRoot es la que gestiona de donde comienza la grámatica. Lo que hace es recibir el nodo de arranque y retornar que se trata de un programa el cual será también ExpressionStatement y que estará definida por el nodo pasado por parámetros.
Por otro lado estaría buildLiteral, la cual recibe un valor y devuelve su valor codificado asignadole el tipo de Literal y guardando su valor convertido a string.
transpile.js
#!/usr/bin/env node
const {deb} = require('./deb.js');
const { difference, notDeclared } = require('./utils.js');
const p = require('./calc').parser;
const fs = require('fs/promises');
const { initializedVariables, dependencies, usedVariables } = require('./scope.js');
const codeGen = require('./code-generation.js')
const writeCode = require('./write-code.js');
module.exports = async function transpile(inputFile, outputFile) {
let input = await fs.readFile(inputFile, 'utf-8')
let ast;
try {
ast = p.parse(input);
} catch (e) {
let m = e.message
console.error(m);
return m;
}
ast = dependencies(ast);
ast = initializedVariables(ast);
ast = usedVariables(ast);
let d = difference(ast.used, ast.symbolTable)
if (d.size > 0) {
let m = notDeclared(d).join('');
console.error(m);
return m;
}
let output = codeGen(ast);
debugger;
await writeCode(output, outputFile);
return output;
}
Una vez explicado y aplicado todo lo anterior podemos proceder a explicar lo el fichero reflejado en este apartado. Este es el que gestiona el cómo se debe traducir la información del fichero que se le introduzca, y debe encargarse de devolver un versión traducida del mismo.
Lo que se hace es leer un fichero el cual se pasa a formato 'utf-8' y se crea una variable ast. Acto seguido se pasa por un bloque try catch, el cual en caso de acertar pasará la información al parser, en caso contrario se retornará un mensaje de error.
Más adelante se hacen llamadas a las funciones de dependencies, initializedVariables y usedVariables, las cuales serán explicadas en el siguiente apartado. Estas lo que harán serán guardar en el ast la información relacionada acerca de las dependencias del árbol, así como de las variables usadas e inicializadas. Para luego calcular la diferencia entra lo usado y lo declarado en su tabla de símbolos y en caso de haber, se imprimirá un error.
Finalmente se creará una variable output la cual guardará el ast que se habrá generado apoyado en el uso codeGen, el cual llamará a distintas funciones con el fin de gestionar la creación del código junto con sus dependencias. Para luego finalmente imprimir el código en el fichero de salida.
scope.js
Para concluir en el siguiente fichero me gustaría centrarme en las 3 funciones principales del mismo, las cuales fueron anteriormente mencionadas. Siendo las siguientes:
function dependencies(dAst) {
dAst.dependencies = new Set([]);
astTypes.visit(dAst.ast, {
visitCallExpression(path) {
const node = path.node;
let name = node.callee.name;
if (patternIsSupport.test(name)) {
dAst.dependencies.add(name);
}
this.traverse(path);
}
});
return dAst;
}
const initializedVariables = (dAst) => {
let initialized = new Set();
let letDeclarations = [];
astTypes.visit(dAst.ast, {
visitAssignmentExpression(path) {
const node = path.node;
if (node.left.type === "Identifier") {
let name = node.left.name;
if (name !== "undefined" && !initialized.has(name)) {
if (!dAst.dependencies.has(name)) {
initialized.add(name);
letDeclarations.push(buildVariableDeclarator(buildIdentifier(name)));
}
}
}
this.traverse(path);
}
});
if (letDeclarations.length > 0) {
dAst.ast.body.unshift(buildVariableDeclaration(letDeclarations));
}
dAst.symbolTable = initialized;
return dAst;
};
const usedVariables = (dAst) => {
let usedVars = new Set();
astTypes.visit(dAst.ast, {
visitIdentifier(path) {
let name = path.node.name;
if (/^[$]/.test(name) && !dAst.dependencies.has(name)) {
usedVars.add(name);
}
this.traverse(path);
}
});
dAst.used = usedVars;
return dAst;
};
función dependencies
Esta función se encarga de gestionar las posibles dependencias que pueda tener nuestro árbol. Para ello lo que se se hace es crear un objeto Set, el cual almacenará dichas dependencias, y luego invocará al objeto astTypes para que active su función visit. Está recibe nuestro árbol y un objeto, siendo en este caso el formato por la función visitCallExpression.
Está función recibe un path y guarda su nombre así como también su atributo callee (debido al tipo de función con la que estamos tratando). Para luego invocar a la función patternIsSupport que se encarga de generar una expresión regular, que verificará si el callee de node es soportado por nuestro programa. Y en caso de serlo se añade a las dependencias del árbol.
Finalmente se llama a la función traverse, con la cual nos introducimos en el árbol para mirar todo esto de manera recursiva y por último retornar el objeto dAST invocante modificado.
función initializedVariables
Similar al caso anterior se comienza creando un Set llamada initialized, que guardará todas las variables inicializadas. Así cómo tambíen una variable letDeclarations que guardará un array con las declaraciones de las mismas.
Apartir de aquí el proceso es el mismo. Se invoca a astTypes con su función visit y lo que se va a mirar en esta ocasión son las expresiones de asignación. Se guarda el camino del nodo y cómo se trata de una variable de asignación, al lado izquierdo debería haber un Identifier. Si este mismo esta definido, no se encuentra en initialized y no está ya en las dependencias del dAst, se añade a initialized y se le construye una declaración, la cual se guardará en letDeclarations.
Finalmente se vuelve a llamar la función traverse para mirar todo de manera recursiva. Y acto seguido se comprueba que en caso de haber variables en letDeclarations, estas se incluyan en el body de dAst. Para luego actualizar la tabla de símbolos de initialized y retornar el árbol modificado.
función usedVariables
Para finalizar con este apartado toca mencionar la función usedVariables, esta sigue la misma lógica que las anteriores, con la diferencia de se buscan identificadores visitados. Para ello se guarda todo en usedVars, para luego volver a aplicar el mencionado método visit.
Acto seguido se usa la función visitIdentifiers para comprobar el path. Guardando el nombre del mismo y comprobando que el nombre coincida con lo esperado y no esté incluido ya en las dependencias. Si esto se cumple se añade a usedVars y usando traverse se mira todo de manera recursiva. Para luego finalmente actualizar el atributo used de nuestro dAst con el set de usedVars, y luego retornarlo.
Testing y uso de parámetros de versión y ayuda
De cara a este apartado solo resaltar que se puede hacer uso del parámetro -V y -h tal y cómo en las prácticas anteriores, y cómo se puede ver arriba. A continuación se mostrará un ejemplo de ejecución de los tests.
Documentación
A continuación adjunto una captura del coverage resultante en github pages: