Lexer Generator

Objetivos

Usando el repo de la asignación de esta tarea construya un paquete npm y publíquelo como paquete privado en GitHub Registry con ámbito @ULL-ESIT-PL-2122 y con nombre el nombre de su repo lexgen-code-AluXXXteamName

Una parte de los conceptos y habilidades a ejercitar con esta práctica se explican en la sección Creating and publishing a node.js module en GitHub y en NPM.

El módulo deberá exportar un objeto con dos funciones

module.exports = { buildLexer, nearleyLexer };

que construyen analizadores léxicos.

La primera functión buildLexer devolverá un generador de analizadores léxicos genérico, mientras que la segunda nearleyLexer devolverá un analizador léxico compatible con Nearley.JS (opens new window).

La función buildLexer

const { buildLexer } =require('@ULL-ESIT-PL-2122/lexgen-code-aluTeam');

La función importada buildLexer se llamará con un array de expresiones regulares. Cada una de las expresiones regulares deberá ser un paréntesis con nombre. El nombre del paréntesis será el nombre/type del token/terminal.

  "use strict";
const { buildLexer } =require('@ULL-ESIT-PL-2122/lexgen-code-aluTeam');

const SPACE = /(?<SPACE>\s+)/; SPACE.skip = true;
const COMMENT = /(?<COMMENT>\/\/.*)/; COMMENT.skip = true;
const RESERVEDWORD = /(?<RESERVEDWORD>\b(const|let)\b)/;
const NUMBER = /(?<NUMBER>\d+)/; NUMBER.value = v => Number(v);
const ID = /(?<ID>\b([a-z_]\w*)\b)/;
const STRING = /(?<STRING>"([^\\"]|\\.")*")/;
const PUNCTUATOR = /(?<PUNCTUATOR>[-+*\/=;])/;
const myTokens = [SPACE, COMMENT, NUMBER, RESERVEDWORD, ID, STRING, PUNCTUATOR];

const { validTokens, lexer } = buildLexer(myTokens);

console.log(validTokens);
const str = 'const varName \n// An example of comment\n=\n 3;\nlet z = "value"';
const result = lexer(str);
console.log(result);

El array

myTokens = [SPACE, COMMENT, NUMBER, RESERVEDWORD, ID, STRING, PUNCTUATOR];

describe el componente léxico del lenguaje.

La llamada

const { validTokens, lexer } = buildLexer(myTokens)

retornará

1. Un objeto con una función lexer que es el analizador léxico y
2. Un mapa JS validTokens con claves los nombres/tipos de tokens y valores las RegExps asociadas.

El Mapa validTokens

Estos son los contenidos de ValidTokens volcados por la línea console.log(validTokens); en el ejemplo anterior:

➜  lexer-generator-solution git:(master) ✗ node examples/hello.js
Map(8) {
  'SPACE' => /(?<SPACE>\s+)/ { skip: true },
  'COMMENT' => /(?<COMMENT>\/\/.*)/ { skip: true },
  'NUMBER' => /(?<NUMBER>\d+)/ { value: [Function (anonymous)] },
  'RESERVEDWORD' => /(?<RESERVEDWORD>\b(const|let)\b)/,
  'ID' => /(?<ID>\b([a-z_]\w*)\b)/,
  'STRING' => /(?<STRING>"([^\\"]|\\.")*")/,
  'PUNCTUATOR' => /(?<PUNCTUATOR>[-+*\/=;])/,
  'ERROR' => /(?<ERROR>.+)/
}

El token ERROR

Observe como aparece un nuevo token ERROR como último en el mapa. El token ERROR es especial y será automáticamente retornado por el analizador léxico generado lexer en el caso de que la entrada contenga un error.

El analizador lexer

Cuando lexer es llamada con una cadena de entrada retornará el array de tokens de esa cadena conforme a la descripción léxica proveída:

Así, cuando al analizador léxico le damos una entrada como esta:

const str = 'const varName \n// An example of comment\n=\n 3;\nlet z = "value"';
const result = lexer(str);
console.log(result);

deberá producir una salida como esta:

[
  { type: 'RESERVEDWORD', value: 'const', line: 1, col: 1, length: 5 },
  { type: 'ID', value: 'varName', line: 1, col: 7, length: 7 },
  { type: 'PUNCTUATOR', value: '=', line: 3, col: 1, length: 1 },
  { type: 'NUMBER', value: 3, line: 4, col: 2, length: 1 },
  { type: 'PUNCTUATOR', value: ';', line: 4, col: 3, length: 1 },
  { type: 'RESERVEDWORD', value: 'let', line: 5, col: 1, length: 3 },
  { type: 'ID', value: 'z', line: 5, col: 5, length: 1 },
  { type: 'PUNCTUATOR', value: '=', line: 5, col: 7, length: 1 },
  { type: 'STRING', value: '"value"', line: 5, col: 9, length: 7 }
]

El atributo skip

Observe como en el array retornado no aparecen los tokens SPACE ni COMMENT. Esto es así porque pusimos los atributos skip de las correspondientes expresiones regulares a true:

const SPACE = /(?<SPACE>\s+)/; SPACE.skip = true;
const COMMENT = /(?<COMMENT>\/\/.*)/; COMMENT.skip = true;

El atributo value

Si se fija en los detalles observará que en el array de tokens, el atributo value del token NUMBER no es la cadena "3" sino el número 3:

{ type: 'NUMBER', value: 3, line: 4, col: 2, length: 1 },

Esto ha ocurrido porque hemos dotado a la regexp de NUMBER de un atributo value que es una función que actua como postprocessor:

const NUMBER = /(?<NUMBER>\d+)/; NUMBER.value = v => Number(v);

Sobre la conducta del lexer ante un error

Cuando se encuentra una entrada errónea lexer produce un token con nombre ERROR:

const str = 'const varName = {};';
r = lexer(str);
expected = [
  { type: 'RESERVEDWORD', value: 'const', line: 1, col: 1, length: 5 },
  { type: 'ID', value: 'varName', line: 1, col: 7, length: 7 },
  { type: 'PUNCTUATOR', value: '=', line: 1, col: 15, length: 1 },
  { type: 'ERROR', value: '{};', line: 1, col: 17, length: 3 }
];

Esta entrada es errónea por cuanto no hemos definido el token para las llaves. El token ERROR es especial en cuanto con que casa con cualquier entrada errónea.

Véase también el último ejemplo con errores en la sección Pruebas

Vídeos de clase explicando los fundamentos necesarios

2020/03/24

En este vídeo se introducen los conceptos de expresiones regulares que son necesarios para la realización de esta práctica. Especialmente

• El uso de lastindex se introduce en el minuto 19:30
• El uso de la sticky flag /y a partir del minuto 30
• Construcción de analizador léxico minuto 33:45

2020/03/25

En los primeros 25 minutos de este vídeo se explica como realizar una versión ligeramente diferente de esta práctica:

• Analizadores Léxicos: 03:00

Estúdielos antes de seguir adelante

Sugerencias para la construcción de buildLexer

Lea la sección

• Como Escribir un Generador de Analizadores Léxicos

La función nearleyLexer

A partir del analizador léxico generado por buildLexer(regexps) contruimos un segundo analizador léxico con la API que requiere nearley.JS (opens new window). Este es el código completo de la versión actual:

const nearleyLexer = function(regexps, options) {
  //debugger;
  const {validTokens, lexer} = buildLexer(regexps);
  validTokens.set("EOF");
  return {
    currentPos: 0,
    buffer: '',
    lexer: lexer,
    validTokens: validTokens,
    regexps: regexps,
    /**
     * Sets the internal buffer to data, and restores line/col/state info taken from save().
     * Compatibility not tested
     */
    reset: function(data, info) { 
      this.buffer = data || '';
      this.currentPos = 0;
      let line = info ? info.line : 1;
      this.tokens = lexer(data, line);
      
      let lastToken = {}; 
        // Replicate the last token if it exists
      Object.assign(lastToken, this.tokens[this.tokens.length-1]);
      lastToken.type = "EOF"
      lastToken.value = "EOF"

      this.tokens.push(lastToken);

      if (options && options.transform) {
        if (typeof options.transform === 'function') {
          debugger;
          this.tokens = options.transform(this.tokens);
        } else if (Array.isArray(options.transform)) {
          options.transform.forEach(trans => this.tokens = trans(this.tokens))
        }
      } 
      return this;
    },
    /**
     * Returns e.g. {type, value, line, col, …}. Only the value attribute is required.
     */
    next: function() { // next(): Token | undefined;
      if (this.currentPos < this.tokens.length)
        return this.tokens[this.currentPos++];
      return undefined;
    },
    has: function(tokenType) {
      return validTokens.has(tokenType);
    },
    /**
     * Returns an object describing the current line/col etc. This allows nearley.JS
     * to preserve this information between feed() calls, and also to support Parser#rewind().
     * The exact structure is lexer-specific; nearley doesn't care what's in it.
     */
    save: function() {
      return this.tokens[this.currentPos];
    }, // line and col
    /**
     * Returns a string with an error message describing the line/col of the offending token.
     * You might like to include a preview of the line in question.
     */
    formatError: function(token) {
      return `Error near "${token.value}" in line ${token.line}`;
    } // string with error message
  };
}

nearleyLexer retorna siempre EOF

Este nuevo lexer va a retornar siempre el token reservado EOF cuando se alcance el final de la entrada. Es por eso que lo añadimos al mapa de tokens válidos:

  validTokens.set("EOF");

y en reset() lo añadimos al final:

this.tokens = lexer(data, line);

let lastToken = {}; 
  // Replicate the last token if it exists
Object.assign(lastToken, this.tokens[this.tokens.length-1]);
lastToken.type = "EOF"
lastToken.value = "EOF"

this.tokens.push(lastToken);

Pruebas

Deberá añadir pruebas usando Jest.

Sigue un ejemplo:

➜  lexer-generator-solution git:(master) ✗ pwd -P
/Users/casianorodriguezleon/campus-virtual/2122/pl2122/practicas-alumnos/lexer-generator/lexer-generator-solution
➜  lexer-generator-solution git:(master) ✗ ls test
build-lexer.test.js          test-grammar-2-args.ne       test-grammar-error-tokens.ne test-grammar.ne
egg                          test-grammar-combined.ne     test-grammar.js

➜  lexer-generator-solution git:(master) ✗ cat test/build-lexer.test.js 

• Contenidos de test/build-lexer.test.js

Ejemplo de ejecución:

➜  lexer-generator-solution git:(master) ✗ npm test                           

> @ull-esit-pl-2122/lexgen-code-casiano-rodriguez-leon@3.1.1 test
> jest --coverage

 PASS  test/build-lexer.test.js
  buildLexer
    ✓ Assignment to string (2 ms)
    ✓ Assingment spanning two lines (1 ms)
    ✓ Input with errors
    ✓ Input with errors that aren't at the end of the line (1 ms)
    ✓ Shouldn't be possible to use unnamed Regexps (4 ms)
    ✓ Shouldn't be possible to use Regexps named more than once (1 ms)
    ✓ Should be possible to use Regexps with look behinds
  buildLexer with unicode
    ✓ Use of emoji operation

----------|---------|----------|---------|---------|-------------------
File      | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s 
----------|---------|----------|---------|---------|-------------------
All files |   64.58 |    58.33 |      50 |   64.58 |                   
 main.js  |   64.58 |    58.33 |      50 |   64.58 | 69,89-118         
----------|---------|----------|---------|---------|-------------------
Test Suites: 1 passed, 1 total
Tests:       8 passed, 8 total
Snapshots:   0 total
Time:        1.291 s
Ran all test suites.

Cubrimiento de las pruebas

• Añada pruebas para comprobar que el post-procesador value funciona correctamente
• Amplíe este ejemplo para comprobar que el analizador nearleyLexer puede ser utilizado correctamente desde Nearley.JS.
• Sustituya el analizador léxico basado en moo-ignore/moo usado en su práctica egg-parser por el correspondiente analizador generado con el generador de esta práctica y compruebe que funciona. Añádalo como una prueba de buen funcionamiento.

Integración Contínua usando GitHub Actions

Use GitHub Actions para la ejecución de las pruebas

Documentación

Documente el módulo incorporando un README.md y la documentación de la función exportada.

Publicar como paquete npm en GitHub Registry

Usando el repo de la asignación de esta tarea publique el paquete como paquete privado en GitHub Registry con ámbito @ULL-ESIT-PL-2122 y nombre el nombre de su repo lexgen-code-aluTeam

Semantic Versioning

Publique una mejora en la funcionalidad del módulo.

Por ejemplo añada la opción /u a la expresión regular creada para que Unicode sea soportado. De esta forma un analizador léxico como este debería funcionar conidentificadores griegos o rusos, números romanos o números en devanagari (opens new window), espacios en blanco como el medium mathematical space, etc.:

✗ cat hello-unicode.js 
"use strict";

const {buildLexer} = require("../src/main.js");

const SPACE = /(?<SPACE>\p{White_Space}+)/; SPACE.skip = true;
const COMMENT = /(?<COMMENT>\/\/.*)/; COMMENT.skip = true;
const RESERVEDWORD = /(?<RESERVEDWORD>\b(const|let)\b)/;
const NUMBER = /(?<NUMBER>\p{N}+)/; 
const ID = /(?<ID>\p{L}(\p{L}|\p{N})*)/;
const STRING = /(?<STRING>"([^\\"]|\\.")*")/;
const PUNCTUATOR = /(?<PUNCTUATOR>[-+*\/=;])/;
const myTokens = [SPACE, COMMENT, NUMBER, RESERVEDWORD, ID, STRING, PUNCTUATOR];
const { validTokens, lexer } = buildLexer(myTokens);

const str = "const αβ६६७ \u205F = ६६७ + Ⅻ"; // \u205F medium mathematical space
const result = lexer(str);
console.log(result);

Que daría como salida:

✗ node hello-unicode.js
[
  { type: 'RESERVEDWORD', value: 'const', line: 1, col: 1, length: 5 },
  { type: 'ID', value: 'αβ६६७', line: 1, col: 7, length: 5 },
  { type: 'PUNCTUATOR', value: '=', line: 1, col: 15, length: 1 },
  { type: 'NUMBER', value: '६६७', line: 1, col: 17, length: 3 },
  { type: 'PUNCTUATOR', value: '+', line: 1, col: 21, length: 1 },
  { type: 'NUMBER', value: 'Ⅻ', line: 1, col: 23, length: 1 }

¿Como debe cambiar el nº de versión?

Referencias

• Tema Expresiones Regulares y Análisis Léxico
  • Sección lastindex
  • Sticky flag
  • Analizadores Léxicos usando la Sticky flag
• Sección Creating and publishing a node.js module en GitHub y en NPM
• Jest
• Sección GitHub Registry
• Sección GitHub Actions
• Sección Módulos
• Sección Node.js Packages
• Sección Documentation