WG211/M19Yallop

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.