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

[Remi Vanicat <vanicat@labri.u-bordeaux.fr>]

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