* Re: [Caml-list] Parsing
2007-06-21 23:14 Parsing Jon Harrop
@ 2007-06-21 23:26 ` Jonathan Bryant
2007-06-21 23:45 ` Christian Stork
` (2 subsequent siblings)
3 siblings, 0 replies; 9+ messages in thread
From: Jonathan Bryant @ 2007-06-21 23:26 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: [Caml-list] Parsing
2007-06-21 23:14 Parsing Jon Harrop
2007-06-21 23:26 ` [Caml-list] Parsing Jonathan Bryant
@ 2007-06-21 23:45 ` Christian Stork
2007-06-22 4:03 ` skaller
2007-06-22 10:14 ` Bruno De Fraine
3 siblings, 0 replies; 9+ messages in thread
From: Christian Stork @ 2007-06-21 23:45 UTC (permalink / raw)
To: caml-list
On Fri, Jun 22, 2007 at 12:14:39AM +0100, 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:
...
> 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?
Yes. If you want to look forward non-destructively use Stream.peek or
Stream.npeek.
> Could the camlp4 macro
> not factor the pattern match for me?
Yes, and camlp4 grammars do indeed perform this kind of
left-factorization.
> Are there other parser tools that integrate into the language and do a better
> job?
Yes, camlp4 grammars.
--
Chris Stork <> Support eff.org! <> http://www.ics.uci.edu/~cstork/
OpenPGP fingerprint: B08B 602C C806 C492 D069 021E 41F3 8C8D 50F9 CA2F
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Caml-list] Parsing
2007-06-21 23:14 Parsing Jon Harrop
2007-06-21 23:26 ` [Caml-list] Parsing Jonathan Bryant
2007-06-21 23:45 ` Christian Stork
@ 2007-06-22 4:03 ` skaller
2007-06-22 10:14 ` Bruno De Fraine
3 siblings, 0 replies; 9+ messages in thread
From: skaller @ 2007-06-22 4:03 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list, Emmanuel Onzon
On Fri, 2007-06-22 at 00:14 +0100, 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:
[]
> However, you must factor heads in the pattern matches.
> Why is this? Is it because the streams are destructive?
Yes.
> Are there other parser tools that integrate into the language and do a better
> job?
Yes. Dypgen. I'm cc'ing to emmanuel, because a Dypgen parser using
a stream as an input would be very cool!
Dypgen is GLR, so all the cases get considered simultaneously.
The current build uses an LR0 kernel I think, so there's no
lookahead.
Also, dypgen is extensible, so you can build grammars at
run time and then parse with them. Doing that requires
a bit more code, some of which could be 'libraried' and the
rest probably supported with camlp4 macros if you're into that.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [Caml-list] Parsing
2007-06-21 23:14 Parsing Jon Harrop
` (2 preceding siblings ...)
2007-06-22 4:03 ` skaller
@ 2007-06-22 10:14 ` Bruno De Fraine
2007-06-24 17:17 ` Jon Harrop
3 siblings, 1 reply; 9+ messages in thread
From: Bruno De Fraine @ 2007-06-22 10:14 UTC (permalink / raw)
To: Jon Harrop; +Cc: caml-list
On 22 Jun 2007, at 01:14, Jon Harrop wrote:
> 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
Actually you must write something like:
and parse_expr = parser
| [< e1=parse_factor; stream >] ->
let rec aux e1 = parser
| [< 'Kwd "+"; e2=parse_factor; stream >] -> aux (e1 +: e2)
stream
| [< 'Kwd "-"; e2=parse_factor; stream >] -> aux (e1 -: e2)
stream
| [< >] -> e1
in aux e1 stream
Although you get the precedences right by organizing different levels
for expr/factor/atom, you've made the operations right associative by
greedily parsing "e2" as an expression. "+" and "-" should be left
associative, unless you want 1-2+3 to evaluate to -4.
> Why is this? Is it because the streams are destructive? Could the
> camlp4 macro
> not factor the pattern match for me?
camlp4's extensible grammar system can handle levels and
associativities for you. Read
http://caml.inria.fr/pub/docs/tutorial-camlp4/tutorial003.html
for more information.
This is your example in the new camlp4:
$ ocaml camlp4of.cma
Objective Caml version 3.10.0
Camlp4 Parsing version 3.10.0
# type expr = Num of int | Add of expr * expr | Sub of expr * expr |
Mult of expr * expr ;;
type expr =
Num of int
| Add of expr * expr
| Sub of expr * expr
| Mult of expr * expr
# let (+:) e1 e2 = Add(e1,e2) ;;
val ( +: ) : expr -> expr -> expr = <fun>
# let (-:) e1 e2 = Sub(e1,e2) ;;
val ( -: ) : expr -> expr -> expr = <fun>
# let ( *: ) e1 e2 = Mult(e1,e2) ;;
val ( *: ) : expr -> expr -> expr = <fun>
# open Camlp4.PreCast ;;
# let expr = Gram.Entry.mk "expr" ;;
val expr : '_a Camlp4.PreCast.Gram.Entry.t = <abstr>
# EXTEND Gram
expr:
[ "add" LEFTA
[ e1 = expr; "+"; e2 = expr -> e1 +: e2
| e1 = expr; "-"; e2 = expr -> e1 -: e2 ]
| "mult" LEFTA
[ e1 = expr; "*"; e2 = expr -> e1 *: e2 ]
| "simple" NONA
[ n = INT -> Num(int_of_string n)
| "("; e = expr; ")" -> e ] ]
;
END ;;
- : unit = ()
# Gram.parse expr Loc.ghost (Stream.of_string "1-2+3*4") ;;
- : expr = Add (Sub (Num 1, Num 2), Mult (Num 3, Num 4))
Another reason to use camlp4 Grammars is that you get automatic
syntax error descriptions. However, this seems to contain bugs in the
current camlp4:
# Gram.parse expr Loc.ghost (Stream.of_string "1+2*(3+)-4") ;;
- : expr = Sub (Add (Num 1, Mult (Num 2, Num 3)), Num 4)
(This should not be accepted. It used to give: Stream.Error "[expr]
expected after '+' (in [expr])")
# Gram.parse expr Loc.ghost (Stream.of_string "1+2*(3+!)-4") ;;
Exception:
Loc.Exc_located (<abstr>,
Stream.Error "[expr] expected after \"(\" (in [expr])").
(This is wrong, because there is a legal expression after "(", namely
"3".)
Regards,
Bruno
--
Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, DINF - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.De.Fraine@vub.ac.be
^ permalink raw reply [flat|nested] 9+ messages in thread