Subject: Re: ABNF sets and sequences

From: <[email-masked]>
Date: Wed, 12 Jul 2000 08:46:25 +0100

Keith,

As I tried to make clear in my first foray into this subject, ABNF defines
the syntax of a notation that serves two distinct purposes:

        1. it allows a human to determine whether a string is legal or
illegal, and

        2. it can be fed as a control string into a limited context
automatic parser that will then report whether a string is legal or
illegal.

Though he didn't state this explicitly, Dave pointed out that there
syntactic constructs for which these purposes are in conflict. To whit, in
order to satisfy the second purpose, ABNF requires an unordered set of
sub-strings to be notationaly expressed as:

        set = *( a / b / c )

which allows a, b, or c to appear in any order and any number of times
from 0 to N. Syntactic (no semantics to be seen here) constraints on the
number of occurrences of a, b, and c cannot be expressed.

What a number of us have been attempting to do since Dave's initial note
is to see if we can introduce an (extended) ABNF notation that will allow
syntactic constraints on the number of occurrences of a, b, or c to be
specified in a way that allows a human can easily determine whether a
string formed from 0 or more occurrences of a, b, and c is legal or
illegal. My feeling is that a notation (previously  described) of the
form:

        set = "{" 2*( *c-wsp member ) *c-wsp "}"
        member = ( rulename / "[" rulename "]" / [repeat] rulename

satisfies these requirements. I.e., a human being can easily determine
whether a set of strings satisfy the syntactic constraints of, for
example:

        valid = { [ a ] b *c }
        a = "x" "y"
        b = "u"
        c = "v"

What cannot be done, for reasons you stated most eloquently

> note that for a parser to implement a rule like this it would
> have to keep track of all sequences of symbols which had
> matched 'name' within that rule, until the rule no longer
> matched new input symbols....which requires an arbitrary
> amount of state..

is to feed the above into an automatic limited context parser which would
determine whether any presented string was legal or illegal.

What almost certainly (without running code, who knows for sure) could be
done in an (extended)  ABNF syntax checker is to treat

        valid = { [ a ] b *c }

as

        valid = * ( a / b / c )

for limited context parsing purposes, and then build an internal
occurrences table that allowed the syntax checker to determine whether an
input string satisfied or violated the occurrences constraints expressed
in by the (extended) ABNF notation.

So in conclusion, in order to proceed, we need to answer two questions
with rough consensus.

1. Can we and have we come up with an (extended) ABNF  notation that
allows us to express occurrences constraints on an unordered set of
sub-strings, such that the vast majority of human readers is easily able
to determine whether a string formed from a sequence of sub-strings is
legal or illegal?

2. Are we willing to relax the constraint that all valid ABNF grammars can
be fed as a control string into a limited context automatic parser for the
purpose of determining whether a presented string is legal or not?

My answer is yes and yes.

Nick

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

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

---

From: Keith Moore <[email-masked]>
Date: Wed, 12 Jul 2000 07:35:06 -0400

Nick,

one problem I have with the 

        valid = { [ a ] b *c }

notation is the use of [ ] and * to mean things that are actually
quite different from the use of these symbols outside the { and }.

while it's true that human languages often change the meaning of
words or symbols based on subtle differences in context, a language 
like ABNF, intended for use in writing technical specifications, needs 
to be less ambiguous than that.   especially when in practice it seems
likely that there will be a need to use both kinds of * or
[ ] in close proximity to one another.

that, and I can't see any way, using the notation above, to say
something like "you can define your own names for addiional parameters 
but none of these may appear more than once". as would presumably
be the case for content-disposition parameters, content-type parameters,
RFC 1894 per-recipient or per-message indicators, etc.

now, we could pick different characters to mean "it's an error if
this symbol is matched more than once within this rule" (say %) or 
"it is an error if this symbol does not match at least once within 
this rule" (say &).  so we would then have

	header = *(
		%&to_field /
		%from_field /
		%sender_field /
		%subject_field /
		received_field 
	)

but offhand I still don't see a way to specify "sender_field must be
present if from_field is missing" with a notation like this.  

and I still find it both clearer, and more useful from an implementor's
point-of-view, to separate "parsing" from other kinds of syntax checking.

Keith