Fairly dumb ocamlyacc question

Fairly dumb ocamlyacc question

[David Allsopp]

This should be obvious, but I can't quite solve it!

If I use the following ocamlyacc script:

------------
%token BEFORE_KWD      AFTER_KWD
%token FAILS_KWD

%token       <int> WEEKDAY
%token    <string> NAME

%type <unit> top
%start top
%%

top:
  WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
| WEEKDAY relative NAME {()}
;

relative:
  BEFORE_KWD {()}
| AFTER_KWD {()}
;
------------

Then I get a shift/reduce having parsed WEEKDAY AFTER_KWD... the parser
can't figure out what to do if it sees NAME. This problem can be made to
disappear by expanding the relative rules to give:

top:
  WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
| WEEKDAY AFTER_KWD NAME {()}
| WEEKDAY BEFORE_KWD NAME {()}
;

I've tried a couple of tricks with %prec but can't get the parser to come
out the same way with the first rule... please could someone put me out of
my misery!!

Thanks,


David

Re: [Caml-list] Fairly dumb ocamlyacc question

[Yann Régis-Gianas]

Hello,

Have you tried menhir :

http://pauillac.inria.fr/~fpottier/menhir/menhir.html.en ?

Menhir generates an explanation of your conflicts and is 90%
compatible with ocamlyacc.

Hope this helps,

--
Yann R.-G.

On 10/24/06, David Allsopp <dra-news@metastack.com> wrote:
> This should be obvious, but I can't quite solve it!
>
> If I use the following ocamlyacc script:
>
> ------------
> %token BEFORE_KWD      AFTER_KWD
> %token FAILS_KWD
>
> %token       <int> WEEKDAY
> %token    <string> NAME
>
> %type <unit> top
> %start top
> %%
>
> top:
>   WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
> | WEEKDAY relative NAME {()}
> ;
>
> relative:
>   BEFORE_KWD {()}
> | AFTER_KWD {()}
> ;
> ------------
>
> Then I get a shift/reduce having parsed WEEKDAY AFTER_KWD... the parser
> can't figure out what to do if it sees NAME. This problem can be made to
> disappear by expanding the relative rules to give:
>
> top:
>   WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
> | WEEKDAY AFTER_KWD NAME {()}
> | WEEKDAY BEFORE_KWD NAME {()}
> ;
>
> I've tried a couple of tricks with %prec but can't get the parser to come
> out the same way with the first rule... please could someone put me out of
> my misery!!
>
> Thanks,
>
>
> David
>
> _______________________________________________
> 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
>


-- 
Yann

Re: [Caml-list] Fairly dumb ocamlyacc question

[skaller]

On Tue, 2006-10-24 at 17:04 -0400, David Allsopp wrote:
> This should be obvious, but I can't quite solve it!

> top:
>   WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
> | WEEKDAY relative NAME {()}
> ;
> 
> relative:
>   BEFORE_KWD {()}
> | AFTER_KWD {()}
> ;
> ------------
> 
> Then I get a shift/reduce having parsed WEEKDAY AFTER_KWD... the parser
> can't figure out what to do if it sees NAME. 

That's right. Consider:

	WEEKDAY AFTER_KWD . NAME
	up to here  ------^

There are two way to parse this: your first and second rule,
and NAME doesn't disambiguate them.

Although you may think about these as the same ..
the parser cannot see into your action rules. 

It has to choose whether to parse AFTER_KWD as a single
token or to reduce the non-terminal 'relative',
and either choice could be wrong depending one what can
come *after* the token NAME -- which it can't take
into account because it's only an LALR(1) parser:
one token lookahead.


> This problem can be made to
> disappear by expanding the relative rules to give:
> 
> top:
>   WEEKDAY AFTER_KWD NAME BEFORE_KWD NAME FAILS_KWD top {()}
> | WEEKDAY AFTER_KWD NAME {()}
> | WEEKDAY BEFORE_KWD NAME {()}
> ;

Yes. There is another way too: to *contract* the rules:

relative:
  BEFORE_KWD { `Before }
| AFTER_KWD { `After }
;
-
top:
  WEEKDAY relative NAME BEFORE_KWD NAME FAILS_KWD top 
  {
    match $2 with
    | `Before -> failwith "BEFORE not allowed here"
    | `After -> ()
  }
| WEEKDAY relative NAME {()}
;

As a general rule of thumb: LR is bottom up not
top down. It isn't goal oriented, but *driven*
by the input. So the thing to do is provide
a unique, no exceptions, way to build small parts
up, such as 'relative' above, and use that always.

So to generalise you should write:

  WEEKDAY relative NAME relative NAME FAILS_KWD top 

and use a match in the action rule to refine
the allowed cases. Think of the syntax as a 
CRUDE way of understanding the input, without
much semantic content, which will parse a much
too general set of inputs .. then subtract the
bad inputs out with further analysis.

For big parsers you get more extreme .. no semantics
in the action rules .. just build the parse tree,
and analyse it later.


> I've tried a couple of tricks with %prec 

Don't ;(

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net