From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA28591; Fri, 12 Sep 2003 12:46:04 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA00948 for ; Fri, 12 Sep 2003 12:46:03 +0200 (MET DST) Received: from mwinf0501.wanadoo.fr (smtp4.wanadoo.fr [193.252.22.26]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h8CAk3f22063 for ; Fri, 12 Sep 2003 12:46:03 +0200 (MET DST) Received: from debian (ca-bordeaux-2-213.w80-8.abo.wanadoo.fr [80.8.74.213]) by mwinf0501.wanadoo.fr (SMTP Server) with ESMTP id EB599400229 for ; Fri, 12 Sep 2003 12:46:02 +0200 (CEST) Received: from moi by debian with local (Exim 3.36 #1 (Debian)) id 19xlRC-0001uN-00 for ; Fri, 12 Sep 2003 12:46:02 +0200 To: caml-list@inria.fr Subject: Re: [Caml-list] eliminating shift/reduce conflicts References: From: Remi Vanicat Mail-Copy-To: never Date: Fri, 12 Sep 2003 12:46:02 +0200 In-Reply-To: (Eckart Goehler's message of "Fri, 12 Sep 2003 11:29:29 +0200 (CEST)") Message-ID: <87fzj2474l.dlv@wanadoo.fr> User-Agent: Gnus/5.090024 (Oort Gnus v0.24) Emacs/21.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-15 Content-Transfer-Encoding: 8bit X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 foo:01 foo:01 baz:01 lalr:01 baz:01 shifted:01 char:01 char:01 rafael:01 'dido':01 bug:01 faq:01 faq:01 beginner's:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Eckart Goehler 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 FOO > %token COLON > %token COMMA > %token CHAR > > %start main > %type 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