[Caml-list] Parsing

[Caml-list] Parsing

[malc]

Was the fact that:

        Objective Caml version 3.12.1

# if 0=0then 1else 0;;
- : int = 1

runs at all intended?

-- 
mailto:av1474@comtv.ru

Re: [Caml-list] Parsing

[Ashish Agarwal]

[-- Attachment #1: Type: text/plain, Size: 496 bytes --]

Why do you think it shouldn't?

On Fri, Feb 10, 2012 at 9:07 PM, malc <av1474@comtv.ru> wrote:

> Was the fact that:
>
>        Objective Caml version 3.12.1
>
> # if 0=0then 1else 0;;
> - : int = 1
>
> runs at all intended?
>
> --
> mailto:av1474@comtv.ru
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

[-- Attachment #2: Type: text/html, Size: 1104 bytes --]

Re: [Caml-list] Parsing

[Esther Baruk]

In fact, variable names cannot begin with an other type of character than a lowercase letter between 'a' and 'z' or '_'. So parsing in this case is straightforward. 
 
Esther Baruk

On 11 févr. 2012, at 03:07, malc <av1474@comtv.ru> wrote:

> Was the fact that:
> 
>        Objective Caml version 3.12.1
> 
> # if 0=0then 1else 0;;
> - : int = 1
> 
> runs at all intended?
> 
> -- 
> mailto:av1474@comtv.ru
> 
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 

Re: [Caml-list] Parsing

[Jon Harrop]

Thanks for the help!

On Friday 22 June 2007 11:14:56 Bruno De Fraine wrote:
> Another reason to use camlp4 Grammars is that you get automatic
> syntax error descriptions. However, this seems to contain bugs in the
> current camlp4:

I think the documentation is a bit out of date as well. I found that this 
compile line works:

  ocamlopt -pp camlp4of -I +camlp4 camlp4lib.cmxa -c tinyml.ml

Looks great though!

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e

Re: [Caml-list] Parsing

[Bruno De Fraine]

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

Re: [Caml-list] Parsing

[skaller]

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

Re: [Caml-list] Parsing

[Christian Stork]

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

Re: [Caml-list] Parsing

[Jonathan Bryant]

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