A Typed, Algebraic Approach to Parsing

Add to your list(s) Download to your calendar using vCal

• Neel Krishnaswami (University of Cambridge)
• Monday 17 March 2025, 13:00-14:00
• FS07, Computer Laboratory.

If you have a question about this talk, please contact Ariadne Si Suo .

In this talk, we recall the definition of the context-free expressions (or µ-regular expressions), an algebraic presentation of the context-free languages. Then, we define a core type system for the context-free expressions which gives a compositional criterion for identifying those context-free expressions which can be parsed unambiguously by predictive algorithms in the style of recursive descent or LL(1). Next, we show how these typed grammar expressions can be used to derive a parser combinator library which both guarantees linear-time parsing with no backtracking and single-token lookahead, and which respects the natural denotational semantics of context-free expressions.

This was joint work with Jeremy Yallop.

This talk is part of the SANDWICH Seminar (Computer Laboratory) series.

This talk is included in these lists:

• FS07, Computer Laboratory
• tcw57’s list

Note that ex-directory lists are not shown.