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  9144 reads

Browse archivesActive forum topics 
Recent comments
3 hours 48 min ago
14 hours 13 min ago
15 hours 27 min ago
1 day 14 hours ago
1 day 17 hours ago
1 day 19 hours ago
1 day 19 hours ago
1 day 20 hours ago
2 days 2 min ago
2 days 54 min ago