Author:

Keywords:

Science & Technology, Technology, Computer Science, Artificial Intelligence, Computer Science, Software Engineering, Computer Science, Theory & Methods, Computer Science, Context-Free Grammars, Haskell, grammar-combinators

Abstract:

We propose a novel context-free grammar representation for parsing libraries in a pure programming language. Our representation explicitizes the recursion in the grammar, thus avoiding fundamental limitations of the grammar model currently employed by parser combinator libraries. Additionally, we decouple the grammar from its semantic actions using techniques from the Multirec generic programming library. The look and feel of the grammar and semantic actions remain close to traditional EBNF and syntax-directed definitions respectively. In an accompanying technical report, we demonstrate that our representation supports more declarative implementations of grammar transformations than other work. The ideas described in this paper form the basis for our freely available grammar-combinators parsing library. © 2011 Springer-Verlag.