Neel Krishnaswami y Jeremy Yallop, de la Universidad de Cambridge, presentan en PLDI '19 (Phoenix, 22–26 de junio de 2019) un trabajo que reconcilia dos tradiciones de la construcción de analizadores sintácticos: los generadores de parsers —basados en gramáticas BNF y autómatas, con análisis en tiempo lineal— y las bibliotecas de combinadores de parsers, populares en lenguajes con funciones de orden superior como ML, Haskell o Scala. Los combinadores aportan abstracciones expresivas, pero suelen carecer de una lectura declarativa clara del lenguaje aceptado y pueden presentar un rendimiento en el peor caso exponencial.
El artículo parte de las µ-expresiones regulares (Leiß, 1991), una presentación algebraica de los lenguajes independientes del contexto que sustituye los no terminales de BNF por variables y un operador de punto fijo. Sobre esa base, los autores definen un sistema de tipos semántico inspirado en la caracterización de Brüggemann-Klein y Wood (1992) para expresiones regulares no ambiguas, y lo refinan en un sistema de tipos sintáctico que verifica cuándo una expresión libre de contexto es apta para análisis predictivo —estilo recursivo descendente o LL(1)—: sin factorización a la izquierda, sin recursión a la izquierda y no ambigua. Demuestran que el sistema preserva tipos bajo sustitución sintáctica y es correcto respecto a la semántica denotacional, y que toda gramática bien tipada es no ambigua.
A partir de ese sistema, construyen una biblioteca de combinadores para OCaml con la API habitual (eps, chr, seq, alt, fix, map), pero que internamente representa las gramáticas bien tipadas en una forma de primer orden que rechaza gramáticas no tipables. Los analizadores resultantes se ejecutan en tiempo lineal, sin retrocesos y con lookahead de un solo token, conservando la lectura denotacional natural de las expresiones.
Finalmente, una versión escalonada (staged) implementada en MetaOCaml elimina la sobrecarga de interpretación de los combinadores. La información de tipos guía la generación de código y produce analizadores que, según los autores, superan en velocidad al código generado por el generador estándar ocamlyacc.