[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?
--
/NAD
More information about the Haskell-Cafe
mailing list