User loginNavigation 
The fundamental limitations of parser combinators... and how to fix them.I am presenting a paper at PADL 2011, in which I discuss the fundamental limitations of current Haskell parser combinator libraries like Parsec and UUParse. The limitations are inherent to the modelling of nonterminal references using direct recursion in a referentially transparent functional language like Haskell. The basic problem is that because of the model used, an algorithm can only ever "look at" a finite top part of the infinite tree representation of the grammar, and the full grammar can never be observed. If you have ever wondered why libraries like Parsec or UUParse only ever use LLstyle algorithms (sometimes with memoization or lazy computation of first sets), it is because only these algorithms can work with such a finite top part of a grammar. Bottomup algorithms or grammar transformations (which are common in parsing literature and widely used in parser generators) cannot be implemented. Even printing a BNF representation of the grammar is fundamentally impossible. In my paper, I show how a different representation of the recursion in the grammar allows for a full "view" on the structure of the grammar, while keeping the DSL very shallow. I demonstrate the additional power with implementations of a few grammar algorithms in the accompanying technical report. An elaborate implementation is available in the grammarcombinators library (featuring a packrat parsing algorithm, leftcorner grammar transform, many grammar manipulation primitives, basic UUParse and Parsec compatibility etc.). Details are in the paper. I'm very interested in feedback from the community. For those of you interested in playing with the code, there is a tutorial available. By Dominique Devriese at 20101215 13:04  LtU Forum  previous forum topic  next forum topic  other blogs  11489 reads

Browse archives
Active forum topics

Recent comments
13 weeks 4 days ago
17 weeks 6 days ago
19 weeks 3 days ago
19 weeks 3 days ago
22 weeks 1 day ago
26 weeks 5 days ago
26 weeks 5 days ago
27 weeks 1 day ago
27 weeks 1 day ago
30 weeks 4 hours ago