[Caml-list] Weird behavior of Camlp4 Parser

[Caml-list] Weird behavior of Camlp4 Parser

[bob zhang]

Hi List,
I have came across a strange behavior of the camlp4 parser, (maybe not
that weird due to my limited knowledge of the parser)
The contrived mini-examples as follows :
module MGram = MakeGram(Lexer) ;;
EXTEND MGram
GLOBAL: m_expr ;
m_expr :
[[ "foo"; f -> print_endline "first"
| "foo" ; "bar"; "baz" -> print_endline "second"]
];
f : [["bar"; "baz" ]]; END;;
MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
second (** choose the second branch, maybe the token rule has a higher
priority *)

MGram.Entry.clear m_expr;;
EXTEND MGram
GLOBAL: m_expr ;
m_expr :
[[ "foo"; f -> print_endline "first"
| "foo" ; "bar"; "bax" -> print_endline "second"]
];
f : [["bar"; "baz" ]]; END;;
- : unit = ()
# MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
first (** here choose the first branch, but the token rule can consume
one token, I thought this should fail *)

Many Thanks

Re: [Caml-list] Weird behavior of Camlp4 Parser

[Gabriel Scherer]

Camlp4 performs grammar factorizations that make its behavior non
strictly LL(k).

I never bothered to learn the exact semantics of Camlp4 grammar rules;
they're complex and, I suspect, possibly fragile. If you avoid being
clever with ambiguities, you can get away with the gory details.

You should have a look at Jake Donham excellent blog series about Camlp4:
  http://ambassadortothecomputers.blogspot.com/2010/05/reading-camlp4-part-6-parsing.html

2011/11/24 bob zhang <bobzhang1988@gmail.com>:
> Hi List,
> I have came across a strange behavior of the camlp4 parser, (maybe not
> that weird due to my limited knowledge of the parser)
> The contrived mini-examples as follows :
> module MGram = MakeGram(Lexer) ;;
> EXTEND MGram
> GLOBAL: m_expr ;
> m_expr :
> [[ "foo"; f -> print_endline "first"
> | "foo" ; "bar"; "baz" -> print_endline "second"]
> ];
> f : [["bar"; "baz" ]]; END;;
> MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
> second (** choose the second branch, maybe the token rule has a higher
> priority *)
>
> MGram.Entry.clear m_expr;;
> EXTEND MGram
> GLOBAL: m_expr ;
> m_expr :
> [[ "foo"; f -> print_endline "first"
> | "foo" ; "bar"; "bax" -> print_endline "second"]
> ];
> f : [["bar"; "baz" ]]; END;;
> - : unit = ()
> # MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
> first (** here choose the first branch, but the token rule can consume
> one token, I thought this should fail *)
>
> Many Thanks
>
>
> --
> 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] Weird behavior of Camlp4 Parser

[bob zhang]

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

Thanks for quick reply.
I have read Jake's camlp4 series carefully, unfortunately it does not cover
my case :-(

On Thu, Nov 24, 2011 at 10:47 AM, Gabriel Scherer <gabriel.scherer@gmail.com
> wrote:

> Camlp4 performs grammar factorizations that make its behavior non
> strictly LL(k).
>
> I never bothered to learn the exact semantics of Camlp4 grammar rules;
> they're complex and, I suspect, possibly fragile. If you avoid being
> clever with ambiguities, you can get away with the gory details.
>
> You should have a look at Jake Donham excellent blog series about Camlp4:
>
> http://ambassadortothecomputers.blogspot.com/2010/05/reading-camlp4-part-6-parsing.html
>
> 2011/11/24 bob zhang <bobzhang1988@gmail.com>:
> > Hi List,
> > I have came across a strange behavior of the camlp4 parser, (maybe not
> > that weird due to my limited knowledge of the parser)
> > The contrived mini-examples as follows :
> > module MGram = MakeGram(Lexer) ;;
> > EXTEND MGram
> > GLOBAL: m_expr ;
> > m_expr :
> > [[ "foo"; f -> print_endline "first"
> > | "foo" ; "bar"; "baz" -> print_endline "second"]
> > ];
> > f : [["bar"; "baz" ]]; END;;
> > MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
> > second (** choose the second branch, maybe the token rule has a higher
> > priority *)
> >
> > MGram.Entry.clear m_expr;;
> > EXTEND MGram
> > GLOBAL: m_expr ;
> > m_expr :
> > [[ "foo"; f -> print_endline "first"
> > | "foo" ; "bar"; "bax" -> print_endline "second"]
> > ];
> > f : [["bar"; "baz" ]]; END;;
> > - : unit = ()
> > # MGram.parse_string m_expr (Loc.mk "<string>") "foo bar baz ";;
> > first (** here choose the first branch, but the token rule can consume
> > one token, I thought this should fail *)
> >
> > Many Thanks
> >
> >
> > --
> > 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
> >
> >
>



-- 
Best, bob

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

Re: [Caml-list] Weird behavior of Camlp4 Parser

[Joel Reymont]

Bob,

On Nov 24, 2011, at 3:22 PM, bob zhang wrote:

> m_expr :
> [[ "foo"; f -> print_endline "first"
> | "foo" ; "bar"; "baz" -> print_endline "second"]
> ];


Since camlp4 is a recursive-descent parser, I don't think you can have "foo"; ... | "foo"; "bar".

I would suggest having a single "foo" in the rule above and have a separate rule that branches depending on whether "bar" is found.

--------------------------------------------------------------------------
- for hire: mac osx device driver ninja, kernel extensions and usb drivers
---------------------+------------+---------------------------------------
http://wagerlabs.com | @wagerlabs | http://www.linkedin.com/in/joelreymont
---------------------+------------+---------------------------------------

Re: [Caml-list] Weird behavior of Camlp4 Parser

[bob zhang]

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

Hi, Joel, camlp4 will do the left factorization automatically.
It's weird because after factorization the order of the rule is changed and
no documentation specify how the rules will be re-organized

2011/11/24 Joel Reymont <joelr1@gmail.com>

> Bob,
>
> On Nov 24, 2011, at 3:22 PM, bob zhang wrote:
>
> > m_expr :
> > [[ "foo"; f -> print_endline "first"
> > | "foo" ; "bar"; "baz" -> print_endline "second"]
> > ];
>
>
> Since camlp4 is a recursive-descent parser, I don't think you can have
> "foo"; ... | "foo"; "bar".
>
> I would suggest having a single "foo" in the rule above and have a
> separate rule that branches depending on whether "bar" is found.
>
> --------------------------------------------------------------------------
> - for hire: mac osx device driver ninja, kernel extensions and usb drivers
> ---------------------+------------+---------------------------------------
> http://wagerlabs.com | @wagerlabs | http://www.linkedin.com/in/joelreymont
> ---------------------+------------+---------------------------------------
>
>


-- 
Best, bob

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