Subject: Re: ABNF sets and sequences

From: <[email-masked]>
Date: Tue, 11 Jul 2000 06:57:39 -0400

OK!

So initially I was won over by Chis' proposal that we use the *( a / b /
c) syntactic construct accompanied by a standardized table to specify
occurrence and other constraints for unordered sets.

BUT!

Dave makes that the point that *( a / b / c) is syntactically weaker than
it could (or should) be, because it lacks any occurrence information.

I think that we can all agree that there is no problem with a SET
construct that specifies mandatory "xxx" or optional [ "xxx" ] inclusion
of a single string, the problem occurs with possible multiple occurrences
m*n( "xxx") of a string. One simple way around this would be to require
the components of a SET construct to be non-terminals. In this case, it is
the strings that correspond to each non-terminal that may appear in any
order. If this were done then we would have a notation which follows BNF
conventions, and which would allow the specification of occurrence
constraints in a very transparent and easily understood way. This seems
like a good idea.

We shouldn't get hung up here about whether a grammar containing a SET
construct can be treated as a control string to an automatic parser. It
may well be the case that the processing of a SET ( [a] b *c 1*d )
construct is best implemented by treating it syntactically as a *( a / b /
c /d) construct with a table that specifies that a may occur 0-1 times, b
must occur 1 time, c may occur 0-n times and d may occur 1-n times.

Certainly, I think that it is hard to argue against the expressive
notational power of SET ( [a] b *c 1*d ), and I at least am beginning to
convince myself that we should pursue this idea further.

Nick

Nick Shelness, IBM Fellow
Chief Technology Officer
Lotus Development Corp
Tel: (617) 693-7484

Assistant: Mary McGurran
Tel: (617) 693-4321

---

From: Robert Elz <[email-masked]>
Date: Wed, 12 Jul 2000 02:16:25 +1000

Date:        Tue, 11 Jul 2000 06:57:39 -0400
    From:        <[email-masked]>
    Message-ID:  <[email-masked]>

  | One simple way around this would be to require
  | the components of a SET construct to be non-terminals. In this case, it is
  | the strings that correspond to each non-terminal that may appear in any
  | order.

That isn't defined well enough to be useful.

Eg: consider

	rule = SET ( a b c )
	a = x y

	or even
	rule = SET ( (x y) b c )

are you then going to allow b x c y ?

What exactly are the "strings that correspond to a non-terminal"?

This is the kind of complication that Dave was attempting to avoid
by limiting the ordering to apply only into the top level, and not
descend.

Just maybe one way around this might be to add to ABNF a rule

	set = "{" 2*( *c-wsp repetition ) *c-wsp "}"

and make set one of the alternatives for element.   (I prefer to use
"{" "}" over "SET (" ")" but that's just syntax drivel, what counts here
is the semantics).

The "2*" is the only thing that makes logical sense, but 1* or even 0*
(ie: just *) wouldn't hurt.

The semantic would be that the elements generated directly by each
repetition (considered all together) could appear in any order, but that
the expansion of each element itself would not be subject to reordering.

The effect would be that

	rule = { a b c }
	a = *x

and

	rule = { *x b c }

would not define the same language, as in the first case 'a' is a
repetition with the optional repeat omitted, hence leading to a single
element, that element (which happens to be generated by *x) could come
anywhere with respect to b and c, but couldn't be split.  On the other
hand, in the second case, the *x contains the indefinite repetition
of the element 'x' and so the various x's could be ordered anywhere
wrt the b and c.

I haven't thought about this for long enough to see the difficulties
that it exposes, though I think it quite unlikely that there are none.

kre

ps: draft dependencies can be a non-issue here - the way to avoid that
problem would be to not republish an amended ABNF, but to publish an
ammendment to ABNF.   Anything that is using 2234 just continues to do
so, and gets to advance as that does.  Anything that wants to use sets
would necessarily post-date the new RFC, and so need not be restricted
by it (unless of course, there's just one use of sets, in which case
the new one may never get past proposed).

That is, apart from explanation, boilerplate, and noise, the new
RFC would be just 

	element =/ set
	set = "{" 2*( *c-wsp repitition ) *c-wsp "}"