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 QAA02638; Fri, 12 Sep 2003 16:56:24 +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 QAA05509 for <caml-list@pauillac.inria.fr>; Fri, 12 Sep 2003 16:56:22 +0200 (MET DST)
Received: from ux9.sp.cs.cmu.edu (UX9.SP.CS.CMU.EDU [128.2.220.166])
	by concorde.inria.fr (8.11.1/8.11.1) with SMTP id h8CEuLf24162
	for <caml-list@inria.fr>; Fri, 12 Sep 2003 16:56:22 +0200 (MET DST)
Received: from 12-203-149-172.client.attbi.com ([12.203.149.172])
          by ux9.sp.cs.cmu.edu id aa09188; 12 Sep 2003 10:55 EDT
Received: from ecc by stratocaster.home with local (Exim 3.36 #1 (Debian))
	id 19xpKh-00086c-00
	for <caml-list@inria.fr>; Fri, 12 Sep 2003 10:55:35 -0400
Date: Fri, 12 Sep 2003 10:55:35 -0400
To: caml-list@inria.fr
Subject: Re: [Caml-list] eliminating shift/reduce conflicts
Message-ID: <20030912145535.GB30895@ecooper.com>
Mail-Followup-To: caml-list@inria.fr
References: <20030912082632.GA9048@imperium.ph>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20030912082632.GA9048@imperium.ph>
User-Agent: Mutt/1.5.4i
From: "Eric C. Cooper" <ecc@cmu.edu>
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; caml-list:01 rafael:01 'dido':01 foo:01 foo:01 baz:01 baz:01 compiler:01 approaches:01 sep:01 checking:01 parser:02 objects:02 wrote:03 sevilla:03 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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