From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id EAA14144; Fri, 12 Jul 2002 04:52:48 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id EAA14139 for <caml-list@pauillac.inria.fr>; Fri, 12 Jul 2002 04:52:47 +0200 (MET DST)
Received: from laurelin.dementia.org ([208.167.88.73])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g6C2qk516381
	for <caml-list@inria.fr>; Fri, 12 Jul 2002 04:52:46 +0200 (MET DST)
Received: by laurelin.dementia.org (Postfix, from userid 1001)
	id 03CDE70C3; Thu, 11 Jul 2002 22:59:21 -0400 (EDT)
To: Nicolas FRANCOIS (AKA El Bofo) <nicolas.francois@free.fr>
Cc: Caml List <caml-list@inria.fr>
Subject: Re: [Caml-list] What's wrong with my parser ?
References: <20020712044121.3f253c69.nicolas.francois@free.fr>
From: John Prevost <j.prevost@cs.cmu.edu>
Date: 11 Jul 2002 22:59:20 -0400 (12.454 UMT)
In-Reply-To: <20020712044121.3f253c69.nicolas.francois@free.fr>
Message-ID: <86it3l3b3r.fsf@laurelin.dementia.org>
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

>>>>> "nf" == Nicolas FRANCOIS (AKA El Bofo) <nicolas.francois@free.fr> writes:

    nf> I define a polynom parser like this : let rec parse = let

  let rec parse =
    let parse_puissance = parser
      | [< ''^'; e = parse_int >] -> e
      | [< >] -> 1
    in
    let parse_x = parser
      | [< ''X'; e = parse_puissance >] -> e
      | [< >] -> 0
    in
    let parse_coeff = parser
      | [< n = R.parse >] -> n
      | [< >] -> R.one
    in
    let parse_monome = parser
      | [< n = R.parse; e = parse_x >] ->
	  monome n e
      | [< e = parse_x >] ->
	  monome R.one e
    in
      parser
	| [< ''+'; m = parse_monome; p = parse >] ->
	    m ++ p
	| [< ''-'; m = parse_monome; p = parse >] ->
	    (opp m) ++ p
	| [< m = parse_monome; p = parse >] ->
	    m ++ p
	| [< >] -> zero


    nf> parse_int and the R.parse functions work OK, and I'll add all
    nf> the "_=parse_space" after. But :

# let p1 = P.parse (Stream.of_string "1+X");;
Stack overflow during evaluation (looping recursion?).

    nf> What's the problem ?

Ahh.  I didn't look closely enough.  The problem can be seen by
looking at what happens when you try to parse the empty stream:

in parse:
  [< >] -> cases 1 and 2 fail, tries [< m = parse_monome; p = parse >]
    in m = parse_monome:
      [< >] -> I assume R.parse fails, so it tries [< e = parse_x >]
        in parse_x
          [< >] -> case 1 fails, case 2 [< >] succeeds
          parse_x returns 0
      parse_monome returns monome R.one 0
  [< m = parse_monome; ... >] succeeded, move to [< ...; p = parse >]

And at this point, parse is called on [< >] again and it loops.
Unfortunately, I can't remember how to explicitly check for the end of
the stream--and it's been removed from the O'Caml manual.  That's what
you have to do to avoid this.  A quick and dirty hack is to have a
special symbol (";", for instance) at the end of every phrase.

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners