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

[Nils Anders Danielsson]

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?

--
/NAD