Re: [Caml-list] eliminating shift/reduce conflicts

[Eckart Goehler <goehler@astro.uni-tuebingen.de>]

Hi,

If I understand the ommited part right, the poor parser below seems te
have the burden to decide which rule to use when a "FOO" occurs: either
tracing bar expecting more "FOO"s from the foo_list (that is reducing), or
to decide for the "baz" rule and fail when the next token is a "COMMA"
instead of  a "COLON". Therefore ocamlyacc (and yacc also) complain, and
using the rule which performs the reduce step (bar) (AFAIK).

Thats what you result using a completed ocamlyacc example:
------------------------------------------------------------------
%token <string> FOO
%token <string> COLON
%token <string> COMMA
%token <string> CHAR

%start main
%type <string> main

%%

main: bar {$1}
  |   baz {$1}
      ;

bar: foo_list COLON xyzzy { $3 }

baz: FOO COLON yzzyx { $3 }


foo_list: FOO { [$1] }
  | foo_list COMMA FOO { $3 :: $1 }
  ;

xyzzy: CHAR { $1 }
    ;

yzzyx: CHAR { $1 }
    ;
-------------------------------------------------------------

If you really want to distinguish between bar (single FOO) and baz
(multiple FOO), eg. to store a variable declaration/list, you must this do
explicitely by stating that foo_list contains more than one item:

foo_list:  FOO COMMA FOO {$3::[$1]}
  | FOO COMMA foo_list { $3 :: $1 }
  ;

If your grammar is different, you have to supply a completed example.

ciao

eckart

On Fri, 12 Sep 2003, 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.
>
> -------------------
> 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
>

-----------------------------------------------------

	Eckart Goehler
        Sand 1
	IAAT, Astronomy
	72076 Tuebingen

	Tel.   : ++49-7071-297 54 73
	Fax.   : ++49-7071-29 34 58
	e-mail : goehler@astro.uni-tuebingen.de

-----------------------------------------------------

-------------------
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