PL 21/22

# Como Escribir un Generador de Analizadores Léxicos

# lastIndex

Regular expression objects have properties.

One such property is source, which contains the string that expression was created from.

Another property is lastIndex, which controls, in some limited circumstances, where the next match will start.

If your regular expression uses the g flag, you can use the exec method multiple times to find successive matches in the same string. When you do so, the search starts at the substring specified by the regular expression’s lastIndex property.

      > re = /d(b+)(d)/ig
      /d(b+)(d)/gi
      > z = "dBdxdbbdzdbd"
      'dBdxdbbdzdbd'
      > result = re.exec(z)
      [ 'dBd', 'B', 'd', index: 0, input: 'dBdxdbbdzdbd' ]
      > re.lastIndex
      3
      > result = re.exec(z)
      [ 'dbbd', 'bb', 'd', index: 4, input: 'dBdxdbbdzdbd' ]
      > re.lastIndex
      8
      > result = re.exec(z)
      [ 'dbd', 'b', 'd', index: 9, input: 'dBdxdbbdzdbd' ]
      > re.lastIndex
      12
      > z.length
      12
      > result = re.exec(z)
      null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Thus, we can write a loop like this:

let input = "A string with 3 numbers in it... 42 and 88.";
let number = /\b\d+\b/g;
let match;
while (match = number.exec(input)) {
  console.log("Found", match[0], "at", match.index);
}
// → Found 3 at 14
//   Found 42 at 33
//   Found 88 at 40
1
2
3
4
5
6
7
8
9

# Sticky flag "y", searching at position

Regular expressions can have options, which are written after the closing slash.

  • The g option makes the expression global, which, among other things, causes the replace method to replace all instances instead of just the first.
  • The y option makes it sticky, which means that it will not search ahead and skip part of the string when looking for a match.

The difference between the global and the sticky options is that, when sticky is enabled, the match will succeed only if it starts directly at lastIndex, whereas with global, it will search ahead for a position where a match can start.

let global = /abc/g;
console.log(global.exec("xyz abc"));
// → ["abc"]
let sticky = /abc/y;
console.log(sticky.exec("xyz abc"));
// → null
1
2
3
4
5
6
let str = 'let varName = "value"';

let regexp = /\w+/y;

regexp.lastIndex = 3;
console.log( regexp.exec(str) ); // null (there's a space at position 3, not a word)

regexp.lastIndex = 4;
console.log( regexp.exec(str) ); // varName (word at position 4)
1
2
3
4
5
6
7
8
9

Véase también:

# Sugerencias para la construcción de buildLexer

El siguiente código ilustra el uso combinado de la opción sticky y los grupos con nombre para encontrar la solución a esta práctica:

const str = 'const varName = "value"';
console.log(str);

const SPACE = /(?<SPACE>\s+)/;
const RESERVEDWORD = /(?<RESERVEDWORD>\b(const|let)\b)/;
const ID = /(?<ID>([a-z_]\w+))/;
const STRING = /(?<STRING>"([^\\"]|\\.")*")/;
const OP = /(?<OP>[+*\/=-])/;

const tokens = [
  ['SPACE', SPACE], ['RESERVEDWORD', RESERVEDWORD], ['ID', ID], 
  ['STRING', STRING], ['OP', OP] 
];

const tokenNames = tokens.map(t => t[0]);
const tokenRegs  = tokens.map(t => t[1]);

const buildOrRegexp = (regexps) => {
  const sources = regexps.map(r => r.source);
  const union = sources.join('|');
  // console.log(union);
  return new RegExp(union, 'y');
};

const regexp = buildOrRegexp(tokenRegs);

const getToken = (m) => tokenNames.find(tn => typeof m[tn] !== 'undefined');

let match;
while (match = regexp.exec(str)) {
  //console.log(match.groups);
  let t = getToken(match.groups);
  console.log(`Found token '${t}' with value '${match.groups[t]}'`);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

escribiendo una función buildLexer que recibe como argumentos un array tokens como en el ejemplo y retorna una función que hace el análisis léxico correspondiente a esos tokens.

# Analizadores Léxicos usando la Sticky flag

Si combinamos la flag sticky con el uso de paréntesis con nombre podemos construir un analizador léxico.

Recuerda que la función de un analizador léxico es la de proporcionarnos un stream de tokens a partir de la cadena de entrada.

Por ejemplo, el tokenizer de espree funciona así:

> const espree = require('espree')
undefined
> espree.tokenize('var a = "hello"')
[
  Token { type: 'Keyword', value: 'var', start: 0, end: 3 },
  Token { type: 'Identifier', value: 'a', start: 4, end: 5 },
  Token { type: 'Punctuator', value: '=', start: 6, end: 7 },
  Token { type: 'String', value: '"hello"', start: 8, end: 15 }
]
1
2
3
4
5
6
7
8
9

Queremos hacer algo parecido.

Para ello usaremos el hecho de que podemos acceder al paréntesis que casa via el nombre:

> RE = /(?<NUM>\d+)|(?<ID>[a-z]+)|(?<OP>[-+*=])/y;
/(?<NUM>\d+)|(?<ID>[a-z]+)|(?<OP>[-+*=])/y
> input = 'x=2+b'
'x=2+b'
> while (m = RE.exec(input)) { console.log(m.groups) }
[Object: null prototype] { NUM: undefined, ID: 'x', OP: undefined }
[Object: null prototype] { NUM: undefined, ID: undefined, OP: '=' }
[Object: null prototype] { NUM: '2', ID: undefined, OP: undefined }
[Object: null prototype] { NUM: undefined, ID: undefined, OP: '+' }
[Object: null prototype] { NUM: undefined, ID: 'b', OP: undefined }
1
2
3
4
5
6
7
8
9
10

Puesto que la expresión regular es un OR, sólo una de las subexpresiones casa y el resto está undefined. Para detectar el token debemos recorrer el objeto buscando la clave cuyo valor no está undefined:

> RE = /(?<NUM>\d+)|(?<ID>[a-z]+)|(?<OP>[-+*=])/y;
/(?<NUM>\d+)|(?<ID>[a-z]+)|(?<OP>[-+*=])/y
> input = 'x=2+b'
'x=2+b'
> names = ['NUM', 'ID', 'OP']
[ 'NUM', 'ID', 'OP' ]
> while (m = RE.exec(input)) { 
  console.log(names.find(n => m.groups[n] !== undefined)) }
ID
OP
NUM
OP
ID
1
2
3
4
5
6
7
8
9
10
11
12
13

El siguiente ejemplo ilustra la técnica:

[~/.../practicas/p2-t2-lexer(master)]$ cat sticky.js
1
const str = 'const varName = "value"';
console.log(str);

const SPACE = /(?<SPACE>\s+)/;
const RESERVEDWORD = /(?<RESERVEDWORD>\b(const|let)\b)/;
const ID = /(?<ID>([a-z_]\w+))/;
const STRING = /(?<STRING>"([^\\"]|\\.")*")/;
const OP = /(?<OP>[+*\/-=])/;

const tokens = [
  ['SPACE', SPACE], ['RESERVEDWORD', RESERVEDWORD], ['ID', ID],
  ['STRING', STRING], ['OP', OP]
];

const tokenNames = tokens.map(t => t[0]);
const tokenRegs  = tokens.map(t => t[1]);

const buildOrRegexp = (regexps) => {
  const sources = regexps.map(r => r.source);
  const union = sources.join('|');
  // console.log(union);
  return new RegExp(union, 'y');
};

const regexp = buildOrRegexp(tokenRegs);

const getToken = (m) => tokenNames.find(tn => typeof m[tn] !== 'undefined');

let match;
while (match = regexp.exec(str)) {
  //console.log(match.groups);
  let t = getToken(match.groups);
  console.log(`Found token '${t}' with value '${match.groups[t]}'`);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Como obtener el nombre de una RegExp con nombre

Consideremos una expresión regular con nombre:

> NUM = /(?<NUM>\d+)/
/(?<NUM>\d+)/
1
2

La siguiente expresión regular tiene dos paréntesis para capturar el nombre y el resto de la regexp:

> getName = /^[(][?]<(\w+)>(.+)[)]$/
/^[(][?]<(\w+)>(.+)[)]$/
1
2

Cuando se tiene una regexp Re, el atributo Re.source contiene la cadena que defina la expresión regular.

Asi pues, cuando hacemos getName.exec(NUM.source) obtenemos:

> r = getName.exec(NUM.source)
[
  '(?<NUM>\\d+)',
  'NUM',
  '\\d+',
  index: 0,
  input: '(?<NUM>\\d+)',
  groups: undefined
]
1
2
3
4
5
6
7
8
9

En el primer paréntesis casamos con el nombre y en el segundo con la regexp:

> r[1]
'NUM'
> r[2]
'\\d+'
1
2
3
4

Para que nuestro generador de analizadores léxicos pueda funcionar cada una de las regexp proveídas debe tener un único paréntesis con nombre. Podemos comprobar si el cuerpo de la regexp en r[2] contiene mas paréntesis con nombre haciendo algo como esto:

> OP = /(?<OP>(?<OP2>[+*\/=-]))/
/(?<OP>(?<OP2>[+*\/=-]))/
> r = getName.exec(OP.source)
[
  '(?<OP>(?<OP2>[+*\\/=-]))',
  'OP',
  '(?<OP2>[+*\\/=-])',
  index: 0,
  input: '(?<OP>(?<OP2>[+*\\/=-]))',
  groups: undefined
]
1
2
3
4
5
6
7
8
9
10
11
> hasNamedParen = /[(][?]<(\w+)>(.+)[)]/
/[(][?]<(\w+)>(.+)[)]/
> hasNamedParen.exec(r[2])
[
  '(?<OP2>[+*\\/=-])',
  'OP2',
  '[+*\\/=-]',
  index: 0,
  input: '(?<OP2>[+*\\/=-])',
  groups: undefined
]
1
2
3
4
5
6
7
8
9
10
11

# Referencias

# Referencias Adicionales sobre Análisis Léxico

Last Updated: 10 months ago