Repository logo
 

A Typed, Algebraic Approach to Parsing

Accepted version
Peer-reviewed

Type

Conference Object

Change log

Authors

Krishnaswami, Neelakantan R 
Yallop, Jeremy 

Abstract

In this paper, 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. Finally, we show how to exploit the type information to write a staged version of this library, which produces dramatic increases in performance, even outperforming code generated by the standard parser generator tool ocamlyacc.

Description

Keywords

parsing, context-free languages, type theory, Kleene algebra

Journal Title

Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation

Conference Name

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Journal ISSN

Volume Title

Publisher

ACM

Rights

All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/N02706X/2)