Subject: Re: ABNF sets and sequences

From: <[email-masked]>
Date: Mon, 10 Jul 2000 09:23:42 +0100

Dave, Robert, Keith,

I think that two things are getting badly confused in this discussion.

ABNF, today, serves two purposes.

1. It is a notation that unambiguously (hopefully) allows a human being to
distinguish whether an arbitrary string is legal or not. This in turn
allows (again, hopefully) a human being to write a computer program that
only generates legal strings, and that if combined with sufficient semantic
information will correctly consume and process legal strings, and reject
illegal strings.

2. It can be used to specify a control string that can be fed into a
automatic parser (originally called a compiler compiler) which will then
automatically distinguish legal from illegal strings.

This in turn leads to two questions.

1. Do Dave's two new proposed constructs (if defined with enough rigor)
allow a human being to more easily distinguish whether an arbitrary string
is legal or not? My gut feeling is that they do, though clearly there are
some nasty problems to be solved. For example, under Dave's proposed
notation, are the two grammars

  foo = SET ( "a" "b" *("c"))

and

   foo = SET ( "a" "b" c)
   c = *("c")

equivalent? Everything I know about BNF would imply they are. My sense of
what Dave is saying is that they are not, and that "cabc" is legal under
the former, but not under the latter. Specifying this sufficiently and
intuitively may be very problematic. For example, will a naive reader of
RFC xxxx understand the meaning of SET ( blah blah blah) with sufficient
precision to not generate illegal strings? This clearly needs discussion!

2. It may well be possible to build an automatic parser that correctly
handles SET and SEQ constructs, then again, it may not. If it is not, it is
not clear that we should reject Dave's proposed constructs out of hand.
There are many unambiguous grammars that are incompatible with automatic
parsers!

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: Mon, 10 Jul 2000 09:07:17 -0400

Nick,

I agree with your clarifications; you've stated the points more clearly
than I did.

Keith