[Caml-list] What's wrong with my parser ?

[Caml-list] What's wrong with my parser ?

[Nicolas FRANCOIS]

I define a polynom parser like this :

  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

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

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

What's the problem ?

\bye

-- 

                   Nicolas FRANCOIS
            http://nicolas.francois.free.fr
 A TRUE Klingon programmer does NOT comment his code
-------------------
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

Re: [Caml-list] What's wrong with my parser ?

[John Prevost]

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

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

{...}

    nf> What's the problem ?

What's the definition of R.parse?  It isn't in the code you excerpted.

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

Re: [Caml-list] What's wrong with my parser ?

[John Prevost]

>>>>> "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

Re: [Caml-list] What's wrong with my parser ?

[Daniel de Rauglaudre]

Hi,

On Thu, Jul 11, 2002 at 10:59:20PM -0400, John Prevost wrote:

> 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

It is not the point: even testing the end of the stream would not
help, since the example did not reach the end of the stream, it
took no token at all (no character at all) from the stream.

> --and it's been removed from the O'Caml manual.

It has been copied is in the Camlp4 manual, but perhaps not yet in
the 3.04 version.
    http://caml.inria.fr/camlp4/manual/manual003.html

However the module "Stream" is still part of the OCaml manual. To test
the empty stream, call the parser Stream.empty:
     [< _ = Stream.empty >] ->

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
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

Re: [Caml-list] What's wrong with my parser ?

[Nicolas FRANCOIS]

OK, this is my new polynom parser, it seems to work OK, thanks to your
explanations.

  let rec parse s =
    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 = parse_coeff; e = parse_x >] ->
	  monome n e
      | [< e = parse_x >] ->
	  monome R.one e
    in
    let rec parse_suite = parser
      | [< ''+'; m = parse_monome; p = parse_suite >] ->
	  m ++ p
      | [< ''-'; m = parse_monome; p = parse_suite >] ->
	  (opp m) ++ p
      | [< >] -> zero
    in
      match s with parser
	| [< m = parse_monome >] ->
	    match parse_suite s with
	      | p -> m ++ p

and the results :

# print (P.parse (Stream.of_string "-1+3X+4X^2"));;
[3: -1, 3, 4]- : unit = ()
# print (P.parse (Stream.of_string ""));;
[1: 1]- : unit = ()

Oups !!

What do you think about this ?

\bye

-- 

                   Nicolas FRANCOIS
            http://nicolas.francois.free.fr
 A TRUE Klingon programmer does NOT comment his code
-------------------
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

Re: [Caml-list] What's wrong with my parser ?

[Ryan Tarpine]

>From: Nicolas FRANCOIS (AKA El Bofo) <nicolas.francois@free.fr>
>To: Nicolas FRANCOIS (AKA El Bofo) <nicolas.francois@free.fr>
>CC: caml-list@inria.fr
>Subject: Re: [Caml-list] What's wrong with my parser ?
>Date: Sat, 13 Jul 2002 13:27:34 +0200
>
>OK, this is my new polynom parser, it seems to work OK, thanks to your
>explanations.
>
>   let rec parse s =
><snip>
>     let parse_coeff = parser
>       | [< n = R.parse >] -> n
>       | [< >] -> R.one
>     in
>     let parse_monome = parser
>       | [< n = parse_coeff; e = parse_x >] ->
>	  monome n e
>       | [< e = parse_x >] ->
>	  monome R.one e
><snip>
>     in
>       match s with parser
>	| [< m = parse_monome >] ->
>	    match parse_suite s with
>	      | p -> m ++ p
>
><snip>
># print (P.parse (Stream.of_string ""));;
>[1: 1]- : unit = ()
>

Parsing the empty string calls parse_monome, which calls parse_coeff, which 
returns R.one.  My take at this is that you need 2 versions of parse_x: one 
that requires an X to be there, and one that can parse an X but doesn't need 
it.

If there is no leading coefficient (the second option to parse_monome), the 
X *must* be there.  If the coeffecient is there (the first option), then the 
X doesn't have to be.  The empty string, which has no coefficient, should 
fail parse_monome because it doesn't have an X either.  If passed the string 
"X" or "2", though, parse_monome should succeed.

Ryan Tarpine, rtarpine@hotmail.com
"To err is human, to compute divine.  Trust your computer but not its 
programmer."
  - Morris Kingston

_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com

-------------------
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