[Haskell-cafe] uu-parsinglib

[S D Swierstra]

The there is an amb combinator which you can use to lift an ambiguous parser into one which returns a list of results. This will take care that the part after the ambiguous non-terminal is only parsed once.

Like most libraries I do indeed not cache results of applying parsers at specific positions, besides the use of amb. This is more than most other libraries do. Besides this there are various greedy versions of combinators which take care of repeating construct; so there is an pChainL and a pChainL_ng etc. This has a bit the same effect as the try combinator, but in a more structured way.

Of course applying some left-factoring is always a good idea; but i think this should only be done once real problems arise, which is not very often. 

In case these solutions are not sufficient one could of course take one of the more advanced libraries, which performa real grammar analysis, such as a left corner transform. There are two libraries supporting this: the grammar-combinator package of Dominique deVriese and the Christmas tree package from Utrecht, which is mainly aimed at solving problems with the exponential complexity in GHC's implementation of the function read for values of data types with infix constructors. The first one uses many recent GHC extensions. Both are less of a combinator parsing style, since support for freely abstracting over common grammatical patterns is somewhat more problematic. Both can use uu-parsinglib  as back end,

 Doaitse

PS: previous implementations of GHC made some assumptions about the kind of programs people would write. Unfortunately some parsers using the older uulib package were thus spending 99.5% of their time in garbage collection. This has been cured, thanks to work by Simon Marlow. Some parsers run over 50  times faster!!


 


On Jan 21, 2012, at 9:47 , Roman Cheplyaka wrote:

> * S D Swierstra <doaitse at uu.nl> [2012-01-20 16:32:00+0100]
>> Thus far i have only happy users, and if you are having any problems
>> please let me know.
> 
> Hi Doaitse,
> 
> One thing that I'm curious about is how you avoid combinatorial
> explosion when parsing in a breadth-first fashion. Do you somehow manage
> to merge the branches? Or just hope that in practice it won't be too bad?
> 
> -- 
> Roman I. Cheplyaka :: http://ro-che.info/