Creación de un lenguaje: el parser

El lexer ya entrega tokens. Ahora toca la pieza que les da forma: el parser.

Del texto a un árbol

El lexer entrega una lista plana de tokens. El parser la convierte en un árbol, el AST, y ese árbol responde la pregunta que la lista no puede responder: ¿quién va con quién?

En 1 + 2 * 3 los tokens son los mismos sin importar cómo se lean, pero el resultado no. Si se agrupa como (1 + 2) * 3 da 9; si se agrupa como 1 + (2 * 3) da 7. El parser no calcula nada. Solo decide los grupos, y de esa decisión depende todo lo que viene después.

Quién se queda con el 2

El parser de Codexivo es de tipo Pratt. La idea es simple: cada operador tiene una fuerza. Cuando un valor queda entre dos operadores, los dos lo jalan, y se lo queda el más fuerte.

En 1 + 2 * 3, el 2 está entre + y *. Como * es más fuerte, el 2 se va con el *: primero se agrupa 2 * 3, y ese grupo completo es lo que se suma al 1.

En el código, esas fuerzas son una lista:

export enum Precedence {
  LOWEST = 1,
  EQUALS = 2,
  LESS_GREATER = 3,
  SUM = 4,
  PRODUCT = 5,
  PREFIX = 6,
  CALL = 7,
}

Un número más bajo es un operador más débil: == pierde contra <, < pierde contra +, + pierde contra *. Ese mismo día, en el commit que agregó el si, también entraron y y o. Los agregué al final de la lista, con la y por encima de la o, como en casi todos los lenguajes:

  CALL = 7,
  OR = 8,
  AND = 9,

Y les escribí sus pruebas. Cada una compara el código con el árbol que debería salir, escrito con paréntesis:

['verdadero o falso y verdadero;', '(verdadero o (falso y verdadero))'],
['verdadero y falso o verdadero;', '((verdadero y falso) o verdadero)'],

Las dos pasan.

Una llamada también es un operador

Lo que más me gustó de Pratt es lo poco que cambia el parser para cosas que no parecen operadores. Cada token puede tener dos funciones: una para cuando aparece al inicio de una expresión y otra para cuando aparece en medio, después de algo ya leído.

El - al inicio es un signo negativo; en medio, una resta. El ( al inicio agrupa; en medio, después de un nombre, es una llamada: doble(5) es doble seguido de un operador ( cuya fuerza es CALL, la más alta de la tabla, para que nada le quite el nombre. Hasta si funciona así: es una función de inicio que lee una condición, un bloque y, si hay, un si_no. Por eso en Codexivo un si es una expresión y tiene un valor.

Agregar algo al lenguaje se reduce casi siempre a dos preguntas: ¿qué hace este token al inicio?, ¿y en medio, con qué fuerza?

El pero_si

Después agregué pero_si, para no tener que anidar un si dentro de cada si_no. El parser lo lee en un ciclo: mientras el siguiente token sea pero_si, lee una condición y un bloque, y los guarda como la alternativa del si. Al final, si hay un si_no, lee su bloque.

si (1 > 2) { 10 } pero_si (1 < 2) { 20 }

Este programa da 20. Las pruebas cubren los dos casos que me importaban, con y sin si_no, y pasan:

['si (1 > 2) { 10 } pero_si (1 < 2) { 20 }', 20],
['si (1 > 2) { 10 } pero_si (1 > 2) { 20 } si_no { 30 }', 30],

Lo que se queda

El parser no calcula nada, y aun así es donde el lenguaje decide cómo se lee. La tabla de precedencias parece un detalle de implementación, pero es una decisión de diseño: dice qué va primero cuando alguien escribe sin paréntesis, y quien aprende con Codexivo nunca la va a ver, solo sus consecuencias.

Por eso trato cada fuerza como una regla más del lenguaje, y quiero pocas reglas, cada una con una razón. * antes que +, porque así se aprende en la escuela. y antes que o, porque así lo hacen casi todos los lenguajes, y quien pase de Codexivo a otro no debería tener que reaprenderlo.

Pruébalo

Este es el intérprete de Codexivo. La vista de construcción muestra, paso a paso, cómo se arma el árbol de la misma expresión:

1 + 2 * 3

En la siguiente entrega: el evaluador, la parte que por fin hace algo con el árbol.