@sofidfr/while NPM

Lab Add Loops and Strings

Author: Sofía De Fuentes Rosella
Email: alu0101480619@ull.edu.es

Introduction

Using the grammar built from the previous labs, we are now expanding the functionality of our program by adding functions and the boolean type.

Opciones en línea de comandos

program
  .version(version)
  .argument("<filename>", 'file with the original code')
  .option("-o, --output <filename>", "file in which to write the output")
  .option("-V, --version", "output the version number")
  .action((filename, options) => {
    transpile(filename, options.output);
  });

Se utiliza el paquete 'commander' para crear una interfaz por línea de comandos en una aplicación Node.js.

-V: La versión se establece en el package.json
-o: Se indica el fichero en el que se imprime la salida

Análisis del programa

Lexer

%{
const reservedWords = ["fun", "true", "false", "i", "while", "for"]  
const predefinedIds = ["print", "write" ]

function removeQuotes(s) {
  return s.substring(1, s.length - 1);
}

const idOrReserved = text => {
  if (reservedWords.find(w => w == text)) return text.toUpperCase();
  if (predefinedIds.find(w => w == text)) return 'PID';
  return 'ID';
}

%}
number [0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)?"i"?|"i"
string  \"(?:[^"\\]|\\.)*\"

%%
\s+            /* skip whites */;
"#".*          /* skip comments */;
\/\*(.|\n)*?\*\/ /* skip comments */;
{number}       return 'N';
{string}       { yytext = removeQuotes(yytext); return 'STRING'; }
[a-zA-Z_]\w*   return idOrReserved(yytext); // must be after number
'**'           return '**';
'=='           return '==';
'&&'           return '&&';
'||'           return '||';
[-=+*/!(),<>@&{}\[\];]  return yytext;

Este analizador léxico simplemente aplica reglas de reconocimiento de tokens para saber qué carácteres son aceptados por la gramática. Las reglas vienen definidas como expresiones regulares.

reservedWords Contiene la lista de palabras reservadas del lenguaje. Contienen identificadores especiales y no pueden usarse como identificadores comunes
predefinedIds Contiene la lista de identificadores predefinidos que representan functiones o variables especiales ya existentes en el entorno
removeQuotes Elimina las doble comillas que redean las strings
idOrReserved Función que verifica si un texto es una palabra reservada, un identificador predefinido o un identificador común, y devuelve una clasificación adecuada

Gramática

Permite realizar diversas operaciones matemáticas sobre números enteros, flotantes u complejos. Además permite la asignación, el uso de la coma y PID para imprimir.

%left ','
%right '='
%nonassoc '<' '>'
%left '&&' '||'
%nonassoc '==' 
%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            { $$ = buildCallMemberExpression($e1, 'equals', [$e2]); }   
  | e '<' e             { $$ = buildCallMemberExpression($e1, 'lessThan', [$e2]); } 
  | e '>' e             { $$ = buildCallMemberExpression($e1, 'greaterThan', [$e2]); }   
  | e '&&' e            { $$ = buildLogicalExpression($e1, '&&', $e2); }   
  | e '||' e            { $$ = buildLogicalExpression($e1, '||', $e2); } 
  | '!' e               { $$ = buildUnaryExpression('!', $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 ')'  apply    { $$ = buildParOrCallExpression($e, $apply); }
  | '-' e %prec UMINUS  { $$ = buildCallMemberExpression($e, 'neg', []); }
  | e '!'               { $$ = buildCallExpression('factorial', [$e], true); }
  | N                   { $$ = buildCallExpression('Complex',[buildLiteral($N)], true); }
  | TRUE                { $$ = buildLiteral(true); }
  | FALSE               { $$ = buildLiteral(false); }
  | STRING              { $$ = buildLiteral($STRING); }
  | WHILE  e '{' e '}'  { $$ = buildWhileExpression($e1, $e2); }
  | FOR    '(' e ';' e ';' e ')' '{' e '}' { $$ = buildForExpression($e1, $e2, $e3, $e4); }
  | PID '(' eList ')'   { $$ = buildCallExpression($PID, $eList, true); }
  | ID  apply           { $$ = buildParOrCallExpression(buildIdentifier($($ID)), $apply); }
  | FUN '(' idOrEmpty ')' '{' e '}'   
                        { $$ = buildFunctionExpression($idOrEmpty, $e); } 
;

Operaciones soportadas

Operaciones Binarias: +, -, *, /, @ (max), & (min), ** (potencia)
Operaciones Unarias: - (negativo), ! (factorial)
Números Complejos: Representados por N y tratados con Complex (más info en apartado de Complejos)
Asignación: Permite asignar el resultado de una expresión a un identificador (variable) usando =
Operadores lógicos: && (and), || (or)
Operaciones de comparación: ==, <
Uso de la coma: , se usa para separar expresiones, permitiendo evaluar múltiples expresiones en secuencia
PID: permite imprimir el id usando la función print o write

Precedencia de Operadores

Coma: ','
- Asociatividad: %left (Izquierda)
- Descripción: Utilizada para evaluar múltiples expresiones en secuencia, devolviendo el resultado de la última. Suele tener una precedencia baja, facilitando la ejecución de múltiples acciones en una sola expresión
Asignación: '='
- Asociatividad: %right (Derecha)
- Descripción: Generalmente tiene una de las precedencias más bajas, permitiendo cadenas de asignaciones
Operaciones lógicas y comparación: '==' '<' '&&' '||'
- Asociatividad: %left (Izquierda)
- Descripción: Permiten evaluar igualdades, comparaciones y operaciones lógicas entre expresiones. Se evalúan después de las operaciones aritméticas, pero antes de la igualdad y la coma
Máximo y mínimo: '@' '&'
- Asociatividad: %left (Izquierda)
- Descripción: Se evalúan después de todas las operaciones de mayor precedencia, agrupándose de izquierda a derecha en expresiones sucesivas sin paréntesis
Suma y resta: '+' '-'
- Asociatividad: %left (Izquierda)
- Descripción: Tienen mayor precedencia que el máximo y mínimo, pero menor que la multiplicación y división, evaluándose de izquierda a derecha
Multiplicación y división: '*' '/'
- Asociatividad: %left (Izquierda)
- Descripción: Una de las precedencias más altas, con evaluación de derecha a izquierda en expresiones con múltiples operadores de potencia
Potencia: '**'
- Asociatividad: %right (Derecha)
- Descripción: Una de las precedencias más altas, con evaluación de derecha a izquierda en expresiones con múltiples operadores de potencia
Factorial y negativo unario: '!' 'UMINUS'
- Asociatividad: %nonassoc (No asociativa)
- Descripción: La mayor precedencia, evaluándose antes de cualquier otro operador. La no asociatividad previene ambigüedades en expresiones directamente consecutivas sin paréntesis claros

apply:
    /* empty */      { $$ = []; }
  | '('  ')' apply   { $$ = [ null ].concat($apply); }
  | '(' e ')' apply  { $$ = [$e].concat($apply); }
;

empty: Retorna un arreglo vacío. No hay argumentos de función o aplicación
'(' ')': Maneja llamadas a funciones sin argumentos. Agrega null a un array que se concatena con más contenidos de apply.
'(' e ')': Para llamadas a funciones con argumentos

idOrEmpty:
   /* empty */    { $$ = []; } 
  | ID            { $$ = [ buildIdentifier($($ID)) ]; }   
;

empty: Representa la ausencia de un id. Retorna un array vacío
ID: Cuando se encuentra un id, construye un nodo AST para ese id y lo mete en un array

eList:            { $$ = []; }
  | eList ';' e   { $$ = $eList.concat([$e]); }
  | e             { $$ = [$e]; }
;

empty: Indica una lista de expresiones vacías. Retorna un array vacío
eList ';' e: Permite construir listas de expresiones separadas por ;. Agrega la expresión a eList. Esto es recursivo y permite listas de cualquier longitud
e: Inicia una lista de expresiones con un único elemento.

Funciones

buildRoot: Construye el nodo raíz del AST.
buildBinaryExpression: Construye nodos para expresiones binarias (e.g., suma, resta).
buildLiteral: Construye nodos para literales numéricos.
buildCallExpression: Construye nodos para llamadas a funciones, utilizado aquí para operaciones de factorial y potencia.
buildUnaryExpression: Construye nodos para expresiones unarias, como el negativo.
buildIdentifier: Crea nodos para identificadores, que representan nombres de variables o funciones en el código
buildAssignmentExpression: Construye nodos para expresiones de asignación, donde se asigna el resultado de una expresión a un identificador
buildSequenceExpression: Genera nodos para secuencias de expresiones, permitiendo representar múltiples expresiones evaluadas en secuencia
buildCallMemberExpression: Construye nodos para llamadas a métodos sobre objetos, útil para operaciones con números complejos donde se invoca un método de un objeto
buildMemberExpression: Crea nodos para expresiones de miembro, usadas para acceder a propiedades o métodos de objetos
buildVariableDeclaration: Genera nodos para declaraciones de variables, introduciendo nuevas variables
buildVariableDeclarator: Crea nodos para especificar variables individuales dentro de una declaración
buildMax: Construye un nodo del AST para representar la llamada a la función Math.max que devuelve el mayor entre dos números
buildMin: Construye un nodo del AST para representar la llamada a la función Math.min que devuelve el menor entre dos números
buildMethodExpression: Construye nodos para llamadas a métodos sobre objetos, específicamente para operaciones con números
buildFunctionExpression: Crea un nodo del AST con parámetros y cuerpo de función que contiene una instrucción de retorno
buildIdCalls: Construye un nodo del AST, aplicando una serie de llamadas sucesivas a un id inicial, cada una con sus propios argumentos
buildWhileExpression: Construye un nodo para la expresión de bucle while dentro de una función
buildForExpression: Construye un nodo para la expresión de bucle for dentro de una función
buildArrowFunctionExpression: Construye un nodo para una expresión de función de flecha.
buildParOrCallExpression: Construye un nodo para expresiones que pueden ser simples o secuencias de llamadas a funciones

Traducción de expresiones

Cuando se invoca calc2js.mjs, se llama a la función transpile con el nombre del archivo de entrada que contendrá algo así:

a = 0,
b = while a < 10 {
  print(a),
  a = a +1
},
print(b) # 10

La función transpile se encarga de:

Leer el contenido del archivo de entrada
Parsear el código fuente para construir un AST
Generar el código JS transpilado a partir del AST modificado, incluyéndo un preámbulo que importa las dependencias necesarias desde una biblioteca de soporte support-lib.js
Escribe el código JS generado en el archivo de salida o por pantalla

La función que se encarga de traducir el código a JavaScript es codeGen(ast)

module.exports = function codeGen(ast) {
  let fullPath = path.join(__dirname, 'support-lib.js');
  let dependencies = Array.from(ast.dependencies).join(", ");
  let preamble = template(dependencies, fullPath);
  let output = preamble + recast.print(ast.ast).code;
  return output;  
}

Primero utiliza el módulo path para obtener la ruta completa al archivo support-lib.js que contiene las implementaciones de las dependencias
La variable dependencies recoge todas las dependencias identificadas durante el análisis del AST. Estas se pasan a template para generar el preámbulo del archivo de salida
Se utiliza recast.print(ast.ast) para convertir el AST modificado en código JS. recast permite la lectura y la generación de código, manteniendo tanto como pueda el estilo original
El preámbulo se concatena con el código JS, formando la salida (output) y es retornado

while

Para la traducción de expresiones while, en la gramática se llama a buildWhileExpression, árbol que se encuentra en ast-build.js

function buildWhileExpression(test, body) {
  return {
    type: "CallExpression",
    callee: {
      type: "ArrowFunctionExpression",
      id: null,
      params: [],
      body: {
        type: "BlockStatement",
        body: [
          {
            type: "VariableDeclaration",
            declarations: [
              {
                type: "VariableDeclarator",
                id: {
                  type: "Identifier",
                  name: "result"
                },
                init: {
                  type: "Literal",
                  value: false,
                  raw: "false"
                },
                kind: "let"
              }
            ],
            kind: "let"
          },
          {
            type: "WhileStatement",
            test: test,
            body: {
              type: "BlockStatement",
              body: [
                {
                  type: "ExpressionStatement",
                  expression: buildAssignmentExpression("result", "=", body)
                }
              ]
            },
          },
          {
            type: "ReturnStatement",
            argument: {
              type: "Identifier",
              name: "result"
            },
          },
        ],
      },
      async: false,
      generator: false,
      id: null,
      expression: false
    },
    arguments: [],
  };
}

Se declara la función anónima (función flecha sin parámetros y nombre) que retorna un valor
Se inicializa result a false. Aquí se almacena el resultado que devuelve la función
Se construye el bucle while. test es la condición de parada. buildAssignmentExpression permite asignar el valor de la función a result
Se retorna el resultado

while

for

Para la traducción de expresiones for, en la gramática se llama a buildForExpression, árbol que se encuentra en ast-build.js

function buildForExpression(init, test, update, body) {
  return {
    type: "CallExpression",
    callee: {
      type: "ArrowFunctionExpression",
      id: null,
      params: [],
      body: {
        type: "BlockStatement",
        body: [
          {
            type: "VariableDeclaration",
            declarations: [
              {
                type: "VariableDeclarator",
                id: {
                  type: "Identifier",
                  name: "result"
                },
                init: {
                  type: "Literal",
                  value: false,
                  raw: "false"
                },
                kind: "let"
              }
            ],
            kind: "let"
          },
          {
            type: "ForStatement",
            init: init,
            test: test,
            update: update,
            body: {
              type: "BlockStatement",
              body: [
                {
                  type: "ExpressionStatement",
                  expression: buildAssignmentExpression("result", "=", body)
                }
              ]
            },
          },
          {
            type: "ReturnStatement",
            argument: {
              type: "Identifier",
              name: "result"
            },
          },
        ],
      },
      async: false,
      generator: false,
      id: null,
      expression: false
    },
    arguments: [],
  };
}

Se declara la función anónima (función flecha sin parámetros y nombre) que retorna un valor
Se inicializa result a false. Aquí se almacena el resultado que devuelve la función
Se construye el bucle for. init es la inicialización, test es la condición de prueba y update es la actualización buildAssignmentExpression permite asignar el valor de la función a result
Se retorna el resultado

for

strings

Para la traducción de strings, se han seguido los siguientes pasos:

Definir en el lexer la ER: \"(?:[^"\\]|\\.)*\" para capturar cadenas de carácteres encerradas entre comillas dobles
Cuando la ER captura algo, se llama a removeQuiotes para quitarle las comillas. Se retorna luego el token STRING
En la gramática se llama a buildLiteral, cuya propiedad raw representa cómo aparece el literal en el código fuente

string

Simetría

Para lograr la simetría con operaciones de distintos tipos se ha hecho lo siguiente: Ejemplo bool con string y viceversa

bool op string

booleanHandler.string = function (op, other) {
  if (op === 'add') {
    return String(this) + other;
  } else if (op === 'equals') {
    return String(this) === other ? true : "false";
  } else if (op === 'lessThan') {
    return String(this).length < other.length ? true : "false";
  } else if (op === 'greaterThan') {
    return String(this).length > other.length ? true : "false";
  } else if (op === 'greaterThanOrEquals') {
    return String(this).length >= other.length ? true : "false";
  } else if (op === 'lessThanOrEquals') {
    return String(this).length <= other.length ? true : "false";
  }
}

Si el primer operando es bool, se llama a booleanHandler y si el segundo es string, se le concatena .string.
Se define exactamente lo que se quiere hacer con cada operador. En este caso se convierte el valor booleano en string y si es una suma, se concatenan. Si es una operación de comparación, también se convierte el valor booleano en string y se comparan. Si la expresión retorna true, se retorna ese valor bool. Pero si retorna false, se devuelve como string. Eso es para evitar errores.

stringHandler.boolean = function (op, other) {
  if (op === 'add') {
    return this + String(other);
  } else if (op === 'equals') {
    return (this == String(other)) ? true : "false";
  } else if (op === 'lessThan') {
    return (this.length < String(other).length) ? true : "false";
  } else if (op === 'greaterThan') {
    return (this.length > String(other).length) ? true : "false";
  } else if (op === 'greaterThanOrEquals') {
    return (this.length >= String(other).length) ? true : "false";
  } else if (op === 'lessThanOrEquals') {
    return (this.length <= String(other).length) ? true : "false";
  }
}

Si el primer operando es string, se llama a stringHandler y si el segundo es bool, se le concatena .boolean.
Se hace exactamente igual que antes. Se transforma el valor bool en string y se ejecutan las operaciones.

for (let op in Operators) {
  // Extending the boolean class to give error messages for all airthmetic operations
  Boolean.prototype[op] = function (other) {
    if (booleanHandler[typeof other]?.call(this, op, other) === "false") return false;
    return booleanHandler[typeof other]?.call(this, op, other) || booleanHandler.default.call(this, op, other)
  };
  Function.prototype[op] = function (other) {
    if (booleanHandler[typeof other]?.call(this, op, other) === "false") return false;
    return functionHandler[typeof other]?.call(this, op, other) || functionHandler.default.call(this, op, other)
  };
  String.prototype[op] = function (other) {
    if (booleanHandler[typeof other]?.call(this, op, other) === "false") return false;
    return stringHandler[typeof other]?.call(this, op, other) || stringHandler.default.call(this, op, other)
  }
}

Este último fragmento es lo que permite las llamadas a los handlers anteriores.
El if sirve para cuando retornamos el string "false". Si retornara false como bool, la condición del or no se compliría y saliaría a la siguiente parte del or (esto daría problemas)

Mensajes de error para operaciones de distinto tipo no soportadas

La segunda parte del or anterior es lo que permite esto. El default handler.

stringHandler.default = function (op, other) {
  throw new Error(`String "${this}" does not support "${Operators[op] || op}" for "${other}"`)
}

Cuando la primera expresión del or no se cumple, salta a la segunda, que contiene este mensaje de error.

def_handler

Tests

Antes de ejecutar los tests se deben completar una serie de pasos:

Se imprime la salida del programa en un archivo de salida: bin/calc2js.mjs test/data/test4.calc -o test/data/correct4.js
Se ejecuta con node y se comprueba que la salida es correcta: node test/data/correct4.js
Se imprime la salida anterior en el fichero de salida: node test/data/correct4.js > test/data/correct-out4.txt
Se añade a test-description.mjs el archivo:

  {
    input: 'test4.calc',
    output: 'out4.js',
    expected: 'correct4.js',
    correctOut: 'correct-out4.txt'
  },

Se ejecuta el test: npx mocha --grep 'test4'
Para ejecutarlos todos a la vez: npm run test

tests

Uso de la IA

Para la documentación se utilizó Github Copilot y se realizó alguna consulta a ChatGPT para mayor entendimiento del funcionamiento del programa

Examples

References

Repo ULL-ESIT-GRADOII-PL/esprima-pegjs-jsconfeu-talk
crguezl/hello-jison
Espree
- Options for parse and tokenize methods
astexplorer.net demo
idgrep.js
Introducción a los Compiladores con Jison y Espree

ull jison espree compiler

ast-types c8 chmod commander complex.js dotenv jison recast set-operations shelljs.exec

1.0.0

2 years ago