De las palabras a los árboles

El lexer entrega una lista: 1, +, 2, *, 3. Cualquier escolar sabe que el resultado es 7 y no 9, porque la multiplicación «va primero». La lista no lo dice. La regla vive en la gramática del lenguaje, y el analizador sintáctico (parser) la aplica para construir un árbol en el que 2 * 3 cuelga por debajo del +. A partir de aquí el compilador ya no vuelve a mirar el texto: trabaja con árboles.

§Gramáticas

En 1956 el lingüista Noam Chomsky clasificó las formas de describir lenguajes según cuánta memoria necesita una máquina para reconocerlos. Los lenguajes regulares (los del lexer, capítulo 01) necesitan una memoria finita; un nivel más arriba, los lenguajes independientes del contexto necesitan una pila y pueden expresar anidamientos de cualquier profundidad. La sintaxis de casi todos los lenguajes de programación se diseña para ser independiente del contexto.

Tres años después John Backus, recién salido de FORTRAN, necesitaba una forma precisa de definir la sintaxis del nuevo lenguaje internacional ALGOL. Su notación, pulida por Peter Naur como editor del informe de ALGOL 60, se convirtió en la BNF (forma de Backus–Naur), y toda definición de lenguaje posterior desciende de ella. Esta es parte de la gramática de Wahoo en su forma extendida, con [ ] para lo opcional y { } para la repetición:

program  := item*
item     := 'pipe' NAME '(' [param {',' param}] ')' ['->' NAME] block
          | 'world' INT '-' INT block
block    := '{' stmt* '}'
stmt     := 'coin' NAME [':' NAME] '=' expr
          | 'question' expr block ['else' (question | block)]
          | 'bounce' expr block
          | 'run' NAME 'from' expr 'to' expr block
          | 'flag' [expr]
          | NAME '=' expr
          | call
expr     := or
or       := and {'or' and}
and      := not {'and' not}
not      := 'not' not | cmp
cmp      := sum [('==' | '!=' | '<' | '<=' | '>' | '>=') sum]
sum      := term {('+' | '-') term}
term     := unary {('*' | '/' | '%') unary}
unary    := '-' unary | primary
primary  := INT | TEXT | 'star' | 'goomba' | call | NAME | '(' expr ')'

Lee las reglas de las expresiones de arriba abajo: cada nivel se construye con el de debajo, así que cuanto más abajo está una regla, más fuerte ligan sus operadores. Ese escalonamiento es la tabla de precedencias, escrita como gramática.

§Árboles de análisis y árboles de sintaxis abstracta

Una derivación puede dibujarse como un árbol de análisis, con un nodo por cada regla aplicada. Lo registra todo, incluidos los paréntesis y la cadena expr → or → and → not → cmp → sum por la que pasa un número solitario. Los compiladores guardan una versión más delgada, el árbol de sintaxis abstracta (AST): un nodo por cada construcción que significa algo, sin puntuación ni agrupaciones, porque la forma del árbol ya las codifica. En la figura, (1 + 2) * 3 no tiene nodo de paréntesis; el + simplemente está debajo del *.

§Ambigüedad, precedencia y asociatividad

La gramática obvia para la aritmética, expr := expr op expr | INT, es ambigua: 10 - 4 - 3 tiene dos árboles, uno que significa (10 - 4) - 3 = 3 y otro 10 - (4 - 3) = 9. Un lenguaje tiene que elegir, y dos datos zanjan todos los casos:

• La precedencia dice qué operadores ligan más: * antes que +, ambos antes que <, este antes que and, y este antes que or.
• La asociatividad dice cómo agrupar una cadena de operadores del mismo nivel: por la izquierda para - y / (así 10 - 4 - 3 = 3), por la derecha para la potencia en los lenguajes que la tienen (2 ** 3 ** 2 = 2 ** 9 en Python).

La ambigüedad más famosa del diseño de lenguajes es el else colgante: en if a if b x else y, ¿a qué if pertenece el else? C y Java dicen «al más cercano». Wahoo esquiva la pregunta haciendo obligatorias las llaves: question a { question b { x } else { y } } solo puede leerse de una manera.

Las comparaciones merecen una decisión especial. En C, 1 < 2 < 3 es legal y significa (1 < 2) < 3, es decir 1 < 3, que es cierto por casualidad; 3 > 2 > 1 es falso por la misma razón. Python lo lee como 1 < 2 and 2 < 3. Wahoo lo rechaza (error E102) y te pide que escribas el and.

§Descenso recursivo

La forma más natural de escribir un parser a mano es convertir cada regla de la gramática en una función. block espera una { y luego llama a stmt hasta ver una }; stmt mira el siguiente token y decide qué regla aplicar; question llama a expr y luego a block. Las funciones se llaman unas a otras recursivamente igual que las reglas se refieren unas a otras, y la pila de llamadas hace el papel de la pila que necesitan los lenguajes independientes del contexto. Es el descenso recursivo, y así analizan GCC, Clang, rustc, Go, V8 y Wahoo.

Funciona con soltura cuando basta un token de anticipación para elegir la regla, una propiedad llamada LL(1). Las sentencias de Wahoo se diseñaron para ello: cada una empieza por su propia palabra clave, salvo la asignación y las llamadas, que empiezan ambas por un nombre y se distinguen por el token siguiente (= o (). Lo único que el descenso recursivo no puede hacer es la recursión por la izquierda: una regla sum := sum '+' term haría que sum se llamara a sí misma antes de consumir nada, para siempre. Por eso la gramática de arriba usa repetición, sum := term {'+' term}, y construye en un bucle el árbol inclinado a la izquierda.

§El parsing de Pratt

Ocho niveles de reglas de expresión suponen ocho llamadas anidadas solo para analizar el número 3. En 1973 Vaughan Pratt propuso un método más limpio, la precedencia de operadores descendente: dar a cada operador infijo dos números, una potencia de ligadura izquierda y otra derecha, y analizar todas las expresiones con un único bucle.

Operadores	Potencia izquierda	Potencia derecha	Efecto
or	1	2	el más débil, asociativo por la izquierda
and	3	4	asociativo por la izquierda
not (prefijo)	—	5	se aplica a una comparación entera
== != < <= > >=	7	8	no encadenables (se comprueba aparte)
+ -	9	10	asociativos por la izquierda
* / %	11	12	asociativos por la izquierda
- (prefijo)	—	13	el que más liga

El parser lee un operando y mira el operador siguiente. Si su potencia izquierda llega al mínimo que le pidieron, toma el operador y analiza el lado derecho con la potencia derecha del operador como nuevo mínimo; si no, se detiene y devuelve lo que tiene. Una potencia derecha una unidad mayor que la izquierda hace que una cadena se agrupe por la izquierda; potencias iguales la agruparían por la derecha. Este es el corazón del parser de expresiones de Wahoo:

fn expr_bp(&mut self, min_power: u8) -> PResult<Expr> {
    let mut lhs = self.prefix()?;                      // un número, un nombre, (…), -x, not x
    while let Some((op, left, right)) = infix(&self.peek().kind) {
        if left < min_power {
            break;                                     // liga demasiado poco: que lo tome quien llamó
        }
        self.advance();
        let rhs = self.expr_bp(right)?;
        lhs = Expr::binary(op, lhs, rhs);
    }
    Ok(lhs)
}

§Análisis ascendente: LL frente a LR

El descenso recursivo construye el árbol desde la raíz hacia abajo, prediciendo qué regla viene: es un parser descendente, LL. La otra gran familia trabaja de abajo arriba: va apilando tokens y, cuando la cima de la pila coincide con la parte derecha de una regla, la reduce al no terminal de esa regla. En 1965 Donald Knuth definió las gramáticas LR(k) que pueden analizarse así de forma determinista, una clase estrictamente mayor que LL(k) que incluye reglas recursivas por la izquierda. Las tablas eran enormes para los ordenadores de la época, hasta que el LALR(1) de Frank DeRemer (1969) las hizo prácticas. En 1975 el Yacc de Stephen Johnson (Yet Another Compiler-Compiler) generaba parsers LALR a partir de un fichero de gramática, y su descendiente Bison todavía se usa.

Los generadores no ganaron en todas partes. Los mensajes de error de los parsers guiados por tablas suelen ser pobres («error de sintaxis cerca de la línea 12»), y las gramáticas de los lenguajes reales están llenas de casos especiales. GCC sustituyó en 2004 su parser de C++ hecho con Bison por uno de descenso recursivo escrito a mano, e hizo lo mismo con el de C dos años después. Los generadores prosperan en otros sitios: ANTLR para herramientas y lenguajes de dominio específico, y tree-sitter (2018), que analiza de forma incremental mientras escribes y da sus árboles sintácticos a editores como Neovim y al visor de código de GitHub.

§Cuando el análisis falla

Un parser que se detiene en el primer error de sintaxis es fácil de escribir y molesto de usar. El de Wahoo usa la recuperación en modo pánico: tras informar de un error, se salta tokens hasta llegar a un punto seguro, el comienzo de una línea que empieza una sentencia o la } que cierra el bloque actual, y continúa desde ahí. Así una errata en la línea 3 y otra en la 9 se informan en la misma pasada. Una heurística más atrapa el despiste más común de todos, una } olvidada: si aparece un pipe o un world nuevo al principio de una línea dentro de un bloque, el bloque se cierra ahí y el error lo señala.

error[E101]: se esperaba `}`, pero hay `world`
 --> nivel.wahoo:5:1
  |
5 | world 1-1 {
  | ^^^^^ Lakitu ha perdido el hilo aquí

Recuperarse es cuestión de criterio, no de teoría: si se salta demasiado poco, un error produce una cascada de errores falsos; si se salta demasiado, se pierden errores reales. Wahoo además se detiene tras veinte errores, porque para entonces los últimos suelen ser ecos del primero. Pero que un programa se analice bien no significa que sea correcto: wahoo(vida) es gramatical aunque nadie haya declarado nunca vida. El significado es asunto del capítulo siguiente.

§Referencias

1. N. Chomsky (1956). “Three Models for the Description of Language”. IRE Transactions on Information Theory, 2(3).
2. J. W. Backus (1959). “The Syntax and Semantics of the Proposed International Algebraic Language of the Zurich ACM-GAMM Conference”. Proceedings of the International Conference on Information Processing, UNESCO.
3. P. Naur (ed.) (1960). “Report on the Algorithmic Language ALGOL 60”. Communications of the ACM, 3(5).
4. D. E. Knuth (1965). “On the Translation of Languages from Left to Right”. Information and Control, 8(6).
5. V. R. Pratt (1973). “Top Down Operator Precedence”. Proceedings of the 1st ACM Symposium on Principles of Programming Languages.
6. S. C. Johnson (1975). Yacc: Yet Another Compiler-Compiler. Bell Laboratories Computing Science Technical Report 32.