On 2009-12-10 07:16, oleg@okmij.org wrote:
There are at least two parser combinator libraries that can deal with *any* left-recursive grammars.
Parser combinators are often used to describe infinite grammars (with a finite number of parametrised non-terminals). The library described by Frost et al. cannot handle all such grammars. For instance, it fails to terminate on p n = memoize n (p (1 + n)). (I don't think they claim that their library can handle such grammars.) Your library seems to handle infinite grammars better, as long as you can find a way to insert the incs correctly. I like the definition of Stream; I read Inc as being coinductive, and Plus as being inductive, and then it is easy to see that run is terminating (assuming that its arguments are well-behaved). However, it seems as if one has to be very careful in the placement of incs. Consider the following grammar: S -> A A -> S | B B -> A | eps The easiest implementation is incorrect: g1 = s where s = inc $ a a = inc $ s <+> b b = inc $ a <+> eps run "" g1 = Nothing The following one, where I have been more careful to only insert incs where absolutely necessary, works: g2 = s where s = a a = inc s <+> b b = inc a <+> eps run "" g2 = Just "" If I move the incs around it stops working again, though: g3 = s where s = inc a a = s <+> inc b b = a <+> eps run "" g3 = Nothing Have you proved that it is always possible to place the incs correctly? -- /NAD