# [Haskell-cafe] Parsec-like parser combinator that handles left recursion?

Nils Anders Danielsson nad at Cs.Nott.AC.UK
Thu Dec 10 08:24:33 EST 2009

```On 2009-12-10 07:16, oleg at 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?

--