Creación de un lenguaje: el lexer

En la entrada anterior definí los tokens de Codexivo y prometí que la siguiente hablaría del parser. Antes hay que corregir algo: entre el texto y el parser hay una pieza de la que todavía no escribí. El lexer, la parte que lee el código y produce esos tokens.

Leer letra por letra

Un lexer, o analizador léxico, recibe texto y regresa una lista de tokens. Para la computadora, variable año = 2023; no tiene palabras: es una fila de veinte caracteres. El lexer la recorre de izquierda a derecha, uno por uno, y va decidiendo dónde termina cada pieza y qué es.

En cada carácter el lexer se hace la misma pregunta: ¿esto continúa lo que estoy leyendo, o empieza otra cosa? Una v empieza un nombre, y el nombre sigue mientras haya letras. Al toparse con el espacio, la palabra está completa: variable. Solo entonces revisa si es una palabra reservada. Lo es, así que el token es LET. El espacio no produce nada, el = es un token por sí mismo y 2023 se lee igual que variable, pero con dígitos.

Hasta el final del programa cuenta: el lexer emite un token EOF para que el parser sepa que ya no viene nada más.

La primera versión

Lo estoy construyendo mientras tomo un curso sobre cómo crear un lenguaje de programación. El curso arma una versión básica de Python dentro de Python; yo tomo lo que es igual en cualquier lenguaje (tokens, árbol, evaluación) y lo voy escribiendo en TypeScript, con palabras en español.

El primer commit de Codexivo era casi solo eso: el lexer, los tokens y sus pruebas. El lexer era una cadena de if que comparaba el carácter actual contra una expresión regular por cada símbolo:

if (/^=$/.test(this.character))
  token = new Token(TokenType.ASSIGN, this.character);
else if (/^\+$/.test(this.character))
  token = new Token(TokenType.PLUS, this.character);
// …y así, un símbolo tras otro

Nada elegante. Pero ya cumplía algo que había prometido en el primer post: la función que reconoce letras aceptaba acentos y la ñ desde el primer día.

private isLetter(character: string): boolean {
  return /^[a-zA-Z_áéíóúÁÉÍÓÚñÑ]$/.test(character);
}

Gracias a esa línea, año es un nombre válido. Por la misma línea, pingüino no lo es: la ü se me quedó fuera. Ya la anoté.

Cuando orden se convirtió en o y rden

Dos días después cambié la cadena de if por una tabla. Cada símbolo apuntaba a su tipo de token, y los de dos caracteres (==, <=, !=) indicaban qué carácter tenía que seguir:

const tokenPatterns = {
  "=": [TokenType.ASSIGN, ["=", TokenType.EQ]],
  "<": [TokenType.LT, ["=", TokenType.LT_EQ]],
  // …
  y: [TokenType.AND],
  o: [TokenType.OR],
};

Las dos últimas líneas parecían razonables. y y o son operadores de una sola letra, igual que + es de un solo carácter. Si la tabla ya resolvía los símbolos, ¿por qué no ponerlos ahí?

Porque el lexer revisaba la tabla antes de preguntarse si estaba empezando una palabra. Cualquier nombre que empezara con o o con y se partía en dos.

variable orden = 1; producía un operador o seguido de una variable llamada rden. El parser recibía variable seguido de un operador y respondía con esto:

se esperaba que el siguiente token fuera IDENT pero se obtuvo OR

El mensaje era correcto y no ayudaba en nada. Nadie que lea eso piensa "ah, mi variable empieza con o".

Lo corregí al día siguiente: y y o se fueron a la lista de palabras reservadas, junto a si, mientras y variable. Ahí aprendí la regla que siguen casi todos los lexers: primero se lee la palabra completa, la más larga posible, y solo después se decide qué es. orden es una palabra y no es reservada, así que es un nombre. La o sola, entre espacios, sí lo es.

Dicho así parece obvio. Pero es justo el tipo de error que no aparece con los ejemplos que uno escribe para probar. Mis primeras pruebas usaban x, y, suma… hasta que una variable se llamó orden.

El otro problema: saber dónde estoy

El primer lexer manejaba dos cursores: position, el carácter actual, y readPosition, el siguiente. Para leer una palabra avanzaba hasta encontrar algo que no fuera letra y después retrocedía uno, porque se había pasado:

this.position -= 1;
this.readPosition -= 1;

Ese retroceso era frágil. Unos días después encontré que si el programa no terminaba en ;, el lexer entraba en un ciclo infinito. El arreglo de ese día cambió cómo se movían los dos cursores al llegar al final del texto. La lección fue más general: en un lexer casi todos los errores están en las orillas, y el final del archivo es la orilla que más fácil se olvida.

Después agregué línea y columna a cada token, para que los errores digan dónde están. Una tabulación cuenta como tres columnas, así que en código indentado con tabs las posiciones salen corridas. Para una consola alcanza, por ahora.

Lo que se queda

El lexer es la parte más pequeña del intérprete, y aun así es donde el lenguaje decide qué cuenta como una palabra. Eso tiene consecuencias: que año sea un nombre, que orden no se parta en dos, que la o sola sí sea un operador.

Quedan pendientes. La ü todavía no es una letra, así que pingüino no es un nombre válido. Las columnas salen corridas en cuanto hay tabulaciones. Y los errores, cuando llegan, los reporta el parser, lejos de la causa.

Eso último es lo que más me importa. En un lenguaje pensado para aprender, el primer error de alguien casi siempre es léxico: una comilla que falta, un símbolo que no existe. Si el mensaje que recibe es "se esperaba que el siguiente token fuera IDENT pero se obtuvo OR", lo único que aprende es que no entiende nada. Que el lexer diga exactamente dónde está el problema y qué revisar es una de las cosas que quiero que Codexivo haga bien.

Pruébalo

Abajo está el intérprete de Codexivo, no una animación. La vista de tokens muestra lo que produce el lexer con este código; si lo abres puedes cambiarlo e intentar romperlo.

variable orden = 10;
variable año = 2023;

En la siguiente entrega: el parser, la pieza que toma esta lista plana de tokens y decide qué va con qué.