Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] eliminating shift/reduce conflicts
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Ken Rose <kenrose@t...>
Subject: Re: [Caml-list] eliminating shift/reduce conflicts
Rafael 'Dido' Sevilla wrote:
> I have an ocamlyacc grammar that contains productions that look like:
> 
> foo_list: FOO { [$1] }
>   | foo_list COMMA FOO { $3 :: $1 }
>   ;
> 
> which creates a list of FOO objects.  I however have some rules that
> need to be prefixed by either a single FOO or a foo_list, like so:
> 
> bar: foo_list COLON xyzzy { ... }
> 
> and
> 
> baz: FOO COLON yzzyx { ... }
> 
> This of course produces a shift/reduce conflict, and shifting fails to
> parse the 'bar' correctly.  Perhaps I need to read a compiler
> construction textbook more thoroughly to figure out this answer, but any
> hints out there on getting rid of this shift/reduce.

The general opinion on comp.compilers, which I agree with, is that the 
best way to deal with this is to parse a superset of what you "really" 
want and then use the semantic phase to reject the excess.  In this 
case, that means you'd define

baz: foo_list COLON yzzyx

and later (or even in the semantic action right here) issue an error 
message if the foo_list is longer than 1.

Good luck

  - ken

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners