Explicitly Recursive Grammar Combinators A Better Model for Shallow Parser DSLs

摘要

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 combi-nator 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 library1.