Received-SPF: fail (google.com: domain of abnf-discuss-bounces@ietf.org does not designate 2001:1890:123a::1:1e as permitted sender) client-ip=2001:1890:123a::1:1e;
Date: Wed, 13 Jun 2012 17:15:01 +0100
From: Tony Finch <dot@dotat.at>
To: Bill McQuillan <McQuilWP@pobox.com>
In-Reply-To: <125452205.20120613090251@pobox.com>
Message-ID: <alpine.LSU.2.00.1206131705130.10149@hermes-2.csi.cam.ac.uk>
References: <2CCD27F5-B8D5-4C51-A830-54E6E2676029@lineone.net>
	<4FD79FAD.8040409@alum.mit.edu>
	<alpine.LSU.2.00.1206131151160.10149@hermes-2.csi.cam.ac.uk>
	<125452205.20120613090251@pobox.com>
User-Agent: Alpine 2.00 (LSU 1167 2008-08-23)
MIME-Version: 1.0
Cc: ABNF-Discuss <abnf-discuss@ietf.org>
Subject: Re: [abnf-discuss] Unordered lists with specific cardinality
Precedence: list
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: abnf-discuss-bounces@ietf.org
Errors-To: abnf-discuss-bounces@ietf.org

Bill McQuillan <McQuilWP@pobox.com> wrote:
>
> Although my parser theory may be a little rusty, isn't this the
> equivalent of forcing a context-sensitive feature into a
> context-free grammar?

For the simple case of a list of items that can occur at most once in any
order, it "just" leads to grammars whose size is quadratic in the number
of possible items.

abc_list = [ "a" bc_list
           / "b" ac_list
           / "c" ab_list ]

ab_list = [ "a" b_list
          / "b" a_list ]

ac_list = [ "a" c_list
          / "c" a_list ]

bc_list = [ "b" c_list
          / "c" b_list ]

a_list = [ "a" ]
b_list = [ "b" ]
c_list = [ "c" ]

Tony.
-- 
f.anthony.n.finch  <dot@dotat.at>  http://dotat.at/
Fisher: Northwesterly 5 or 6, occasionally 7 later in northeast. Moderate or
rough. Showers. Good.
_______________________________________________
abnf-discuss mailing list
abnf-discuss@ietf.org
https://www.ietf.org/mailman/listinfo/abnf-discuss