WG211/M19Yallop
From WG 2.11
A typed, algebraic approach to parsing by Jeremy Yallop, joint work with Neel Krishnaswami
Context-free expressions are an algebraic presentation of context-free languages. We define a core type system for context-free expressions that identifies those expressions which can be parsed unambiguously by recursive descent or LL(1).
We next use these typed grammar expressions to build parser combinators that guarantee linear-time parsing without backtracking and with single-token lookahead, and that respect the natural denotational semantics.
Finally, we exploit the type information to stage the combinators, yielding dramatic increases in performance, even outperforming code generated by (ocaml)yacc.
