@sofidfr/while

Lab Add Loops and Strings

• Author: Sofía De Fuentes Rosella
• Email: [e-mail]

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: [],
  };
}

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

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: [],
  };
}

1. Se declara la función anónima (función flecha sin parámetros y nombre) que retorna un valor
2. Se inicializa result a false. Aquí se almacena el resultado que devuelve la función
3. 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
4. Se retorna el resultado

strings

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

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

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.

Tests

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

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

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

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

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