De los caracteres a las palabras

Abre un fichero .wahoo con un editor hexadecimal y la ilusión desaparece: no hay líneas, ni palabras clave, ni sangrías, solo una secuencia de bytes, uno de los cuales resulta ser el carácter de salto de línea. Cuando leemos coin vidas = 3 vemos cuatro palabras de un vistazo. Un compilador tiene que descubrirlas, y la parte que lo hace es el analizador léxico (también llamado lexer, scanner o tokenizador).

Su trabajo es modesto: recorrer los caracteres de izquierda a derecha, agruparlos en las unidades más pequeñas que significan algo, etiquetar cada unidad y desechar lo que al lenguaje no le importa (espacios, comentarios). Todo lo que viene después en el compilador trabaja con esa lista de unidades etiquetadas en vez de con texto en bruto, y eso lo simplifica muchísimo.

§Tokens, lexemas y clases

Wahoo tiene cinco clases de token:

• Palabras clave, 18 palabras reservadas: world pipe coin power_up damage by question else bounce run from to flag star goomba and or not.
• Nombres: una letra o guion bajo seguidos de letras, cifras o guiones bajos (vidas, es_primo, _tmp). Los nombres de tipo como coins son nombres corrientes; es el comprobador, no el lexer, quien sabe que denotan tipos.
• Números: cifras decimales, con guiones bajos opcionales para leerlos mejor (1_000), hasta 2147483647.
• Texto: caracteres entre comillas dobles, con los escapes \n \t \" \\.
• Símbolos: ( ) { } , : -> = + - * / % == != < <= > >=.

§Expresiones regulares y autómatas finitos

Cada clase de token puede describirse con una expresión regular, un patrón construido a partir de caracteres sueltos con tres operaciones: concatenación (una cosa y luego otra), alternativa (|, una cosa u otra) y repetición (*, cero o más veces):

nombre  = [A-Za-z_] [A-Za-z0-9_]*
número  = [0-9] [0-9_]*
texto   = " ( [^"\\\n] | \\ . )* "
le      = < =

En 1951 Stephen Kleene, estudiando qué podía reconocer el modelo de neuronas de McCulloch y Pitts, demostró que los lenguajes que describen las expresiones regulares son exactamente los que reconocen los autómatas finitos: máquinas con un conjunto fijo y finito de estados que leen un carácter cada vez y pasan de un estado a otro. No tienen más memoria que el estado actual, y precisamente por eso un lexer puede ser tan rápido: una consulta a una tabla por carácter. (También por eso tiene límites: un autómata finito no puede comprobar que los paréntesis están equilibrados, y la estructura se deja al parser. La web hermana Math of AI tiene autómatas interactivos y el lema de bombeo que lo demuestra.)

Ese «de forma mecánica» es lo que hizo posibles los generadores de analizadores léxicos. La construcción de Ken Thompson (1968) convierte una expresión regular en un autómata no determinista con unos pocos estados por símbolo; la construcción de subconjuntos lo convierte en uno determinista; y un bucle guiado por tablas lo ejecuta. En 1975 Mike Lesk y Eric Schmidt (entonces becario en los Bell Labs y años después consejero delegado de Google) escribieron Lex, que recibe una lista de expresiones regulares con sus acciones y genera el código C de un lexer completo. Su descendiente, Flex, todavía se usa.

§Gana la coincidencia más larga

Las expresiones regulares por sí solas dejan ambigüedades. ¿<= es un token, o < seguido de =? ¿power_up es una palabra clave, o el nombre power seguido de _up? Los lexers las resuelven con dos reglas:

1. La coincidencia más larga (maximal munch): en cada posición se toma el lexema más largo que encaje con alguna clase. Así <= es un único token y coins es el nombre coins, no la palabra clave coin más una s.
2. Prioridad: si dos clases encajan con el mismo lexema más largo, gana la primera. Wahoo lee cada palabra como un nombre y luego la busca en la tabla de palabras clave, lo que equivale a «palabras clave antes que nombres».

El lexer de Wahoo está escrito a mano, como los de Clang, rustc, Go y V8: un analizador escrito a mano es fácil de hacer rápido y permite dar buenos mensajes de error. Así trata los símbolos que pueden tener uno o dos caracteres; mira el carácter siguiente antes de decidir:

let kind = match (c, next) {
    ('-', Some('>')) => two(self, TokenKind::Arrow),   // ->
    ('=', Some('=')) => two(self, TokenKind::EqEq),    // ==
    ('<', Some('=')) => two(self, TokenKind::Le),      // <=
    ('<', _) => TokenKind::Lt,                         // <
    ('=', _) => TokenKind::Assign,                     // =
    // ...
    _ => { self.error(Kind::UnexpectedChar(c), start); return; }
};

§Cuando importan los saltos de línea

La mayoría de los lenguajes tratan un salto de línea como un espacio más. Algunos no. El lexer de Python emite tokens INDENT y DEDENT cuando cambia la sangría, de modo que el parser ve los bloques como si tuvieran llaves. El de Go inserta un punto y coma al final de una línea que acaba en un nombre, un literal o un cierre de paréntesis. El parser de JavaScript también inserta los puntos y coma que faltan, con una trampa famosa: un return seguido de un salto de línea devuelve undefined, venga lo que venga en la línea siguiente.

Wahoo opta por algo más ligero: cada token lleva una marca que dice si es el primero de su línea. El parser la usa exactamente en dos sitios. Un flag solo toma un valor de su misma línea, así que

flag
wahoo("hecho")

es un flag sin valor seguido de una impresión, no un flag que devuelve el resultado de imprimir. Y un nombre seguido de ( solo es una llamada cuando ambos están en la misma línea.

§Errores léxicos

A este nivel pueden ir mal pocas cosas: un carácter que no pertenece a ningún token (@, ;), un texto que nunca se cierra, un escape que el lenguaje no conoce, un número demasiado grande para 32 bits, cifras pegadas a letras (3vidas). La decisión interesante es qué hacer a continuación. Parar en el primer error es sencillo pero frustrante, así que el lexer de Wahoo informa del problema, se salta el carácter culpable y continúa, para que un carácter perdido no oculte todo lo que viene detrás. También conoce algunas costumbres de otros lenguajes y las convierte en pistas: una ! sugiere not, un ; explica que las sentencias acaban en el salto de línea, una comilla simple que el texto va entre comillas dobles.

error[E001]: carácter inesperado `!`
 --> partida.wahoo:3:12
  |
3 |   question !vivo {
  |            ^ Toad no sabe leer esto
  = pista: la negación se escribe `not`

Con los caracteres agrupados en palabras, el compilador puede empezar a preguntarse cómo encajan las palabras entre sí. Ese es el trabajo del parser.

§Referencias

1. S. C. Kleene (1956). “Representation of Events in Nerve Nets and Finite Automata”. En Automata Studies, Princeton University Press (circuló antes como informe de RAND en 1951).
2. R. McNaughton y H. Yamada (1960). “Regular Expressions and State Graphs for Automata”. IRE Transactions on Electronic Computers, EC-9(1).
3. K. Thompson (1968). “Regular Expression Search Algorithm”. Communications of the ACM, 11(6).
4. M. E. Lesk y E. Schmidt (1975). Lex — A Lexical Analyzer Generator. Bell Laboratories Computing Science Technical Report 39.
5. A. V. Aho, M. S. Lam, R. Sethi y J. D. Ullman (2006). Compilers: Principles, Techniques, and Tools, 2.ª ed., capítulo 3. Addison-Wesley.