[Caml-list] lazy evaluation of combinator parsers

[Jeffrey Loren Shaw]

Hello fellow Camlers,

I'm trying to write a combinator parser in ocaml that uses lazy evaluation.
My goal is that it won't get stuck on infinite loops. So for instance I want
to be able to parse something like (in regex syntax)

a*

let alt p1 p2 xs = append (p1 xs) (p2 xs)

(* regex ? *)
let opt a = alt a epsilon

let rec recseq a =
seq
a
(recseq a)

(* regex * *)
let rec star a =
recseq (opt a)

However, "star (symbol 'a')" causes a stack overflow. I'm not sure why,
since my seq and alt functions are lazy. seq depends on fold_right, map and
append, and alt depends on append. fold_right, map and append are all lazy.
The definitions of alt and seq contain no Lazy.forces.

sources:

http://www.msu.edu/~shawjef3/combparslazy3.ml
http://www.msu.edu/~shawjef3/lazylist3.ml

I would greatly appreciate any help!

Jeff

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[skaller]

On Fri, 2007-03-23 at 21:28 -0400, Jeffrey Loren Shaw wrote:

> let alt p1 p2 xs = append (p1 xs) (p2 xs)
>
> (* regex ? *)
> let opt a = alt a epsilon
>
> let rec recseq a =
> seq
> a
> (recseq a)
>
> (* regex * *)
> let rec star a =
> recseq (opt a)
>
> However, "star (symbol 'a')" causes a stack overflow. I'm not sure why,
> since my seq and alt functions are lazy.

Arguments are evaluated right to left eagerly, so

let rec recseq a = seq a (recseq a)

is instantly an infinite loop. seq is not called here,
it's second argument diverges.

--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net