Re: [Caml-list] Parsing

[Jonathan Bryant <jtbryant@valdosta.edu>]

It's because with Streams you're doing recursive descent parsing  
which is LL, so rules can't contain left recursion.  It's one of the  
disadvantages of using LL over LALR, such as OCamlYacc (not saying  
that LL doesn't also have it's advantages).

--Jonathan

On Jun 21, 2007, at 7:14 PM, Jon Harrop wrote:

>
> I'm not a parser junkie, so please bear with me if this is silly...
>
> The camlp4 stream parsing syntax extension is a very cool way to write
> efficient parsers for simple grammars:
>
>   http://www.ffconsultancy.com/ocaml/benefits/parsing.html
>
> # let rec parse_atom = parser
>     | [< 'Int n >] -> Num n
>     | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e
>
>   and parse_factor = parser
>     | [< e1=parse_atom; stream >] ->
>         (parser
>          | [< 'Kwd "*"; e2=parse_factor >] -> e1 *: e2
>          | [< >] -> e1) stream
>
>   and parse_expr = parser
>     | [< e1=parse_factor; stream >] ->
>         (parser
>          | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
>          | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
>          | [< >] -> e1) stream;;
> val parse_atom : Genlex.token Stream.t -> expr = <fun>
> val parse_factor : Genlex.token Stream.t -> expr = <fun>
> val parse_expr : Genlex.token Stream.t -> expr = <fun>
>
> However, you must factor heads in the pattern matches. So instead of:
>
>   and parse_expr = parser
>     | [< e1=parse_factor; 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
>     | [< e1=parse_factor; 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
>     | [< e1=parse_factor  >] -> e1
>
> you must write:
>
>   and parse_expr = parser
>     | [< e1=parse_factor; stream >] ->
>         (parser
>          | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
>          | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
>          | [< >] -> e1) stream
>
> Why is this? Is it because the streams are destructive? Could the  
> camlp4 macro
> not factor the pattern match for me?
>
> Are there other parser tools that integrate into the language and  
> do a better
> job?
>
> -- 
> Dr Jon D Harrop, Flying Frog Consultancy Ltd.
> The OCaml Journal
> http://www.ffconsultancy.com/products/ocaml_journal/?e
>
> _______________________________________________
> 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