El análisis Pratt es uno de los algoritmos más elegantes en el diseño de compiladores. Maneja la precedencia de operadores sin una tabla de gramática, es extensible sin reescribir el bucle principal y cabe en menos de 200 líneas de Rust. Cuando necesitábamos construir el parser de FLIN -- un parser que maneja aritmética, comparaciones, operadores lógicos, acceso a miembros, llamadas a funciones, consultas temporales, expresiones de intención IA y construcciones de vista similares a HTML -- el análisis Pratt fue la elección obvia.
Este artículo explica cómo funciona el análisis Pratt, por qué lo elegimos sobre las alternativas y cómo lo extendimos para manejar las características inusuales de FLIN como la construcción de entidades, el operador temporal @ y las expresiones de intención ask/search.
El corazón del parser Pratt es un método que llamamos parse_expression, que delega a parse_precedence:
rustfn parse_expression(&mut self) -> Result<Expr, ParseError> {
self.parse_precedence(Precedence::Assignment)
}
fn parse_precedence(&mut self, min_prec: Precedence) -> Result<Expr, ParseError> {
let mut left = self.parse_prefix()?;
while let Some(prec) = self.infix_precedence() {
if prec < min_prec {
break;
}
left = self.parse_infix(left, prec)?;
}
Ok(left)
}Ese es todo el bucle Pratt. Catorce líneas. La magia está en parse_prefix, parse_infix e infix_precedence -- los tres métodos que le dicen al bucle qué hacer con cada token.
Al final de las sesiones 5 y 6, el parser estaba funcionalmente completo para programas FLIN básicos. 149 pruebas totales.
Esta es la Parte 13 de la serie "Cómo construimos FLIN".