Generalized Parser fractional harvesters in Haskell

Question

I am wondering why there are no generalized parser combinators for Bottom-up analysis in Haskell, like Parsec combinators for top-down parsing.
(I could find that some studies were conducted during 2004, but after https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/ ~ jpf / Site / Publications_files / technicalReport.pdf )

Is there any specific reason for achieving it?

Answer 1

This is due to referential transparency. Just as no function can distinguish

let x = 1:x let x = 1:1:1:x let x = 1:1:1:1:1:1:1:1:1:... -- if this were writeable 

no function can distinguish a grammar from a leaf graph and a grammar that is an infinite tree. Partitioning algorithms from below should be able to see the grammar in the form of a graph in order to list all possible states of parsing.

The fact that parsers see their input from top to bottom, because infinite trees allow them to be more powerful, because a tree can be computationally more complex than any graph; eg,

 numSequence n = string (show n) *> option () (numSequence (n+1)) 

accepts any finite ascending sequence of numbers starting with n . This has infinitely many different parsing states. (Perhaps this could have been imagined without context, but it would have been difficult and would have required a greater understanding of the code than, I think, a parsing library could use)

The combinatorial library can be written from the bottom up, although it is a bit ugly, requiring all parsers to be "labeled" in such a way that

• the same label always refers to the same parser, and
• there is only a finite set of labels

at this point, it begins to resemble the traditional specification of grammar much more than the combinatorial specification. However, it can still be enjoyable; you would only have to stick recursive works, which would rule out any infinitely large rules such as numSequence .

Answer 2

As an answer, luqui points out that a bottom-up combinatorial analyzer library is not realistic. In case someone gets to this page just looking for the haskell bottom up syntax generator, what you are looking for is called the Happy parser generator . This is similar to yacc for haskell.

Answer 3

As luqui said above: Haskell examines the definitions of a recursive parser and does not allow you to define upstream parsing libraries. Parsing libraries below are possible, though, if you present recursive grammars in different ways. With an apology for self-promotion, there is one (research) parser library that uses this approach, grammar-combinators . It implements a grammar transformation called the uniform Paul transformation, which can be combined with a top-down parsing algorithm to obtain a bottom-up parser for the original grammar.