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;
Message-ID: <4FDA3FEB.2000009@alum.mit.edu>
Date: Thu, 14 Jun 2012 21:47:55 +0200
From: Paul Kyzivat <pkyzivat@alum.mit.edu>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7;
	rv:12.0) Gecko/20120428 Thunderbird/12.0.1
MIME-Version: 1.0
To: abnf-discuss@ietf.org
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>
	<alpine.LSU.2.00.1206131705130.10149@hermes-2.csi.cam.ac.uk>
In-Reply-To: <alpine.LSU.2.00.1206131705130.10149@hermes-2.csi.cam.ac.uk>
Subject: Re: [abnf-discuss] Unordered lists with specific cardinality
Precedence: list
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="us-ascii"; Format="flowed"
Sender: abnf-discuss-bounces@ietf.org
Errors-To: abnf-discuss-bounces@ietf.org

On 6/13/12 6:15 PM, Tony Finch wrote:
> 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.

Right. So if there were some ABNF syntax for it, that could simply be 
viewed as a sort of macro - expanding to ABNF without that feature.

But as I said, while I haven't thought about it a lot, I don't offhand 
have a plausible syntax in mind. So this is all hypothetical.

	Thanks,
	Paul

> 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.

_______________________________________________
abnf-discuss mailing list
abnf-discuss@ietf.org
https://www.ietf.org/mailman/listinfo/abnf-discuss