* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 8:26 [Caml-list] eliminating shift/reduce conflicts Rafael 'Dido' Sevilla
@ 2003-09-12 8:36 ` Benjamin Geer
2003-09-12 8:40 ` Christian Lindig
` (3 subsequent siblings)
4 siblings, 0 replies; 8+ messages in thread
From: Benjamin Geer @ 2003-09-12 8:36 UTC (permalink / raw)
To: Rafael 'Dido' Sevilla; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 8:26 [Caml-list] eliminating shift/reduce conflicts Rafael 'Dido' Sevilla
2003-09-12 8:36 ` Benjamin Geer
@ 2003-09-12 8:40 ` Christian Lindig
2003-09-12 9:22 ` Rafael 'Dido' Sevilla
2003-09-12 9:29 ` Eckart Goehler
` (2 subsequent siblings)
4 siblings, 1 reply; 8+ messages in thread
From: Christian Lindig @ 2003-09-12 8:40 UTC (permalink / raw)
To: Rafael 'Dido' Sevilla; +Cc: Caml Mailing List
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
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 8:26 [Caml-list] eliminating shift/reduce conflicts Rafael 'Dido' Sevilla
2003-09-12 8:36 ` Benjamin Geer
2003-09-12 8:40 ` Christian Lindig
@ 2003-09-12 9:29 ` Eckart Goehler
2003-09-12 10:46 ` Remi Vanicat
2003-09-12 14:04 ` Ken Rose
2003-09-12 14:55 ` Eric C. Cooper
4 siblings, 1 reply; 8+ messages in thread
From: Eckart Goehler @ 2003-09-12 9:29 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 9:29 ` Eckart Goehler
@ 2003-09-12 10:46 ` Remi Vanicat
0 siblings, 0 replies; 8+ messages in thread
From: Remi Vanicat @ 2003-09-12 10:46 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 8:26 [Caml-list] eliminating shift/reduce conflicts Rafael 'Dido' Sevilla
` (2 preceding siblings ...)
2003-09-12 9:29 ` Eckart Goehler
@ 2003-09-12 14:04 ` Ken Rose
2003-09-12 14:55 ` Eric C. Cooper
4 siblings, 0 replies; 8+ messages in thread
From: Ken Rose @ 2003-09-12 14:04 UTC (permalink / raw)
To: Rafael 'Dido' Sevilla; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [Caml-list] eliminating shift/reduce conflicts
2003-09-12 8:26 [Caml-list] eliminating shift/reduce conflicts Rafael 'Dido' Sevilla
` (3 preceding siblings ...)
2003-09-12 14:04 ` Ken Rose
@ 2003-09-12 14:55 ` Eric C. Cooper
4 siblings, 0 replies; 8+ messages in thread
From: Eric C. Cooper @ 2003-09-12 14:55 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 8+ messages in thread