[Caml-list] eliminating shift/reduce conflicts

[Caml-list] eliminating shift/reduce conflicts

[Rafael 'Dido' Sevilla]

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

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

[Benjamin Geer]

Rafael 'Dido' Sevilla wrote:
> I however have some rules that
> need to be prefixed by either a single FOO or a foo_list

It might be easier to always parse a foo_list, even if it only contains 
one element.

Ben

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

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

[Christian Lindig]

On Fri, Sep 12, 2003 at 04:26:32PM +0800, 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 }
>   ;
> 
> bar: foo_list COLON xyzzy { ... }
> baz: FOO COLON yzzyx { ... }
> 
> This of course produces a shift/reduce conflict, and shifting fails to
> parse the 'bar' correctly.  

I have tried to build a little grammar to reproduce your problem but
failed. If you could post a small stand-alone grammar for OCamlyacc
somebody might be able to help you. The easiest way to remove conflicts
in Yacc is to alter the precedence of individual tokens using %left or
%right. Read the section about 'Declarations' in the OCamlYacc manual.
My toy grammar is below.


%token COLON COMMA FOO ETC
%start start
%type<unit>start

%%
start
    : foo_list ETC bar ETC baz  {}
    ;

foo_list
    : FOO                   {}
    | foo_list COMMA FOO    {}
    ;

bar
    : foo_list COLON ETC    {}
    ;

baz
    : FOO COLON ETC         {}

%%

-- Christian

--
Christian Lindig         http://www.st.cs.uni-sb.de/~lindig/

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

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

[Rafael 'Dido' Sevilla]

On Fri, Sep 12, 2003 at 10:40:47AM +0200, Christian Lindig wrote:
> I have tried to build a little grammar to reproduce your problem but
> failed. If you could post a small stand-alone grammar for OCamlyacc
> somebody might be able to help you.

Here then:

%token COLON COMMA FOO BAR BAZ
%start start
%type <unit>start
%%

start: bar {}
  | baz {}
  ;

foo_list: FOO {}
  | foo_list COMMA FOO {}
  ;

bar: foo_list COLON BAR {}
  ;

baz: FOO COLON BAZ {}
  ;

produces a shift/reduce on COLON.


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

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

[Eckart Goehler]

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

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

[Remi Vanicat]

Eckart Goehler <goehler@astro.uni-tuebingen.de> writes:

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

This is shifting, not 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).

This is not at all the way an LALR parser work.

the problem here is when a parser read the COLON in something like :

FOO COLON ...

then it don't know if it's in the middle of the bar rule (FOO being a
foo_list, and then the foo_list is to be reduce) or in the middle of a
baz rule (that should be shifted from before the COLON to after the
COLON). 

By the way this grammar doesn't seem to be even LR(1), so the
simplification seem very difficult. the only way I see is :

bar: foo_list COLON xyzzy { $3 }

baz: foo_list COLON yzzyx { match $1 with 
                            | [_] -> $3
                            | _   -> raise an error here }




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

-- 
Rémi Vanicat
remi.vanicat@laposte.net

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

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

[Ken Rose]

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

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

[Eric C. Cooper]

On Fri, Sep 12, 2003 at 04:26:32PM +0800, 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.

Here are two approaches.  If the grammar is simple enough, you can
split the bar rule (and other similar ones) into two productions:

    bar: FOO COLON xyzzy | foo_list COLON xyzzy

and require foo_list to have at least two members:

    foo_list: FOO COMMA FOO | foo_list COMMA FOO

Of course, now you have duplicated semantic actions for the two cases,
and it can make the grammar pretty ugly.

Another approach is to accept a more liberal language in the parser,
and do more checking in the semantic action:

    bar: foo_list COLON xyzzy { ... }
    baz: foo_list COLON yzzyx { check_single_foo $1; ... }

Hope this helps.

-- 
Eric C. Cooper          e c c @ c m u . e d u

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