Ups: Created page with "''A typed, algebraic approach to parsing'' by Jeremy Yallop, joint work with Neel Krishnaswami Context-free expressions are an algebraic presentation of context-free language..."

2019-04-29T01:03:37Z

Created page with "''A typed, algebraic approach to parsing'' by Jeremy Yallop, joint work with Neel Krishnaswami Context-free expressions are an algebraic presentation of context-free language..."

New page

''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.

WG211/M19Yallop - Revision history

Ups: Created page with "''A typed, algebraic approach to parsing'' by Jeremy Yallop, joint work with Neel Krishnaswami Context-free expressions are an algebraic presentation of context-free language..."