Re: [abnf-discuss] Unordered lists with specific cardinality

Paul M,

Yes, I see issues like this quite a lot, though I would characterize the 
issue a little differently. I usually see this as a desire to have a 
list of optional items. The actual items each have their own syntax, and 
each must appear at most once in the list. E.g.

optionlist = [option *[COMMA option]]
option = "A" | "B" | "C"

The above syntax allows: A,B,C and B,A and C.
But it also allows: A,A,B,A,B,C which isn't intended.

For small numbers of options this can be solved by brute force:

optionslist = "A" [COMMA "B" [COMMA "C"]]
             / "A" [COMMA "C" [COMMA "B"]]
             / "B" [COMMA "A" [COMMA "C"]]
             / "B" [COMMA "C" [COMMA "A"]]
             / "C" [COMMA "A" [COMMA "B"]]
             / "C" [COMMA "B" [COMMA "A"]]

But its too cumbersome to do that in practice. So we get by by giving 
something at is too loose and tightening it down with words.

It would be nice to extend ABNF with some syntax to help with this. But 
no good syntax for this leaps into my mind.

	Thanks,
	Paul

On 6/11/12 9:56 PM, Paul Moore wrote:
> Hi everyone,
>
> *Background*
>
> I'm documenting a vendor specific media type
> (application/vnd.whosebill+json) which I intend to publish as an
> Informational RFC. However, I'm having some trouble with the handling of
> unordered lists in ABNF.
>
> Broadly, from my research it would appear that this has been a
> long-standing problem, and authors have typically used one of two
> approaches:
>
> *Approach A - Specific cardinality, unordered nature in prose*
>
> In this approach, authors document the list as an ordered rule, *and*
> annotate the list to communicate the unordered nature:
>
>     myobject = begin-object members end-object
>     members = member-a [separator member-b] separator member-c
>     ; the ordering of the members is unimportant
>     begin-object = %x7B ; "{"
>     end-object = %x7D ; "}"
>     separator = %x2C ; ","
>
>
> Pros: Cardinality is ABNF specific (as 'member-b').
> Cons: Ordering has to *fixed* by prose.
> Example: RFC 2045 (MIME Format) - MIME Header Fields
> <http://tools.ietf.org/html/rfc2045#section-3> which states "/The
> ordering of the header fields implied by this BNF definition should be
> ignored"/
>
> or,
>
> *Approach B - Specific unordered nature, cardinality in prose*
>
> In this approach, authors document the list as a selection of
> alternatives, and annotate the cardinality of each member in prose
>
>     myobject = begin-object member *( separator member ) end-object
>     member = member-a
>     / member-b ; required
>     / member-c
>     begin-object = %x7B ; "{"
>     end-object = %x7D ; "}"
>     separator = %x2C ; ","
>
>
> Pros: Unordered nature is implicit through the combination of optional
> alternative values.
> Cons: Cardinality concerns are reduced to prose.
> Example: RFC 5988 (Web Linking) - Link grammar
> <http://tools.ietf.org/html/rfc5988#page-7>. There is some discussion
> about this specific approach in a rejected erratum
> <http://www.rfc-editor.org/errata_search.php?eid=3080> of the same RFC,
> where Mark Nottingham notes "/The proposed ABNF makes ordering
> significant, which is NOT specified or intended. ABNF can never capture
> all of the constraints on syntax; that's why we have prose."/
> *Problem*
>
> My (limited) research implies that ABNF cannot precisely articulate
> unordered lists with specific cardinality; authors are left with a
> choice as to which aspect to handle in prose.
>
> There is some discussion about the problem by Chris Newman here
> <http://www.imc.org/ietf-calendar/archive1/msg03550.html>, and Chris
> advocates a more formulated arrangement of the cardinality in prose
> approach here
> <http://tools.ietf.org/html/draft-ietf-drums-msg-fmt-07#section-3.6>.
>
> Additionally, from examination of the earlier ABNF drafts (RFC 2234) I
> see there was some discussion of a 'list rule' (#rule) and latterly a 'set
> group' with similar intent, but none of these proposals made it to the
> final versions.
>
> I also stumbled across a thread which implicated that use of the 'list
> rule' / 'set group' proposals would cause ambiguities in ABNF, and
> therefore were not pursued. I appreciate that syntax features must be
> carefully designed so as not to introduce ambiguity, but I'm not a lexer
> / parser specialist, and so would like to get a view of whether this is
> something that could be considered for a latter revision of ABNF?
>
> *Questions*
> *
> *
> 1. Is my understanding that ABNF is unable to articulate unordered lists
> with specific cardinality correct, or am I missing something?
>
> 2. Would introducing functionality to allow such lists fundamentally
> introduce ambiguity into the ABNF syntax?
>
>
> Many thanks for your time
>
> Paul
>
>
> _______________________________________________
> abnf-discuss mailing list
> abnf-discuss@ietf.org
> https://www.ietf.org/mailman/listinfo/abnf-discuss

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