Subject: Re: ABNF sets and sequences

From: <[email-masked]>
Date: Tue, 11 Jul 2000 17:55:29 -0400

Robert,

I think that we are in heated agreement, just approaching it along
different paths.

>  | One simple way around this would be to
>  | 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

OK

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

Having thought about this a bit more, I would view this as ill formed. I
now think that a member of a set should only be one of

                 repeat rulename / rulename / "[" rulename "]"

where rulename and "[" rulename "]" are notationaly cleaner but otherwise
syntactically identical to "1*1" rulename and "0*1" rulename.

No other forms would be allowed.

Note, that in my earlier note I used the generic term non-terminal to mean
the ABNF construct rulename.

> are you then going to allow b x c y ?

Under your first set of rules - No.

Given

                 rule = SET ( a b c )
                 a = "x" "y"
                 b = "u"
                 c = "v"

then  "xyuv", "xyvu", "uxyv", "uvxy", "vxyu", and "vuxy" would be legal
strings. Any other combinations of u v x and y would not.

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

Those produced by the rule with the rulename specified as a member of the
SET construct.

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

That's also what I'm trying to achieve. What I hadn't attempted to do, and
which I now think is needed, and which you are now doing, is to rigorously
define the syntax of a set and by extension an element.

> ...

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

If I stick with your {} conventions, then I guess I'm proposing

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

which is more restrictive, but I think notationaly cleaner.

What do you think?

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: Tue, 11 Jul 2000 22:02:20 -0400

I think this is all somewhat misplaced.  if we want a way to be
able to specify that elements in a list may occur in any order,
we can easily specify the syntax of the list, e.g.:

	list = name "=" value  *( ; name "=" value )

	name = atom

	value = string

what we then want to do is to formally specify that no
symbol (or sequence of symbols?) that matches one 'name' 
is the same as the symbol (or sequence) that matches 
any other occurance of 'name'.

that's easy to specify: just invent some syntax to say 
"it is an error if this lexical symbol matches the same
sequence of input symbols more than once within a single
application of this rule"

so if we used '$' to denote such symbols, then:

	list = $name "=" value *( ; $name "=" value )

	name = atom

	value = string

would suffice to express that no input symbol or sequence
of input symbols could match 'name' more than once during
the appliation of the rule.

note that this error is NOT a parse error - if the parser
sees the string

a="1";b="2";a="3";d="4"

it does not stop matching 'list' when it sees the second 
occurance of "a=" - rather 'list' still matches the entire
string above but then the recognizer signals an error that
the name 'a' occurrred more than once.

also this doesn't say anything at all about what the values
might correspond to 'name' - but that's not a big problem, as 
these are not really something you want to wire into a parser anyway.

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

now if you also wanted to impose other constraints, such
as "the name "X" occurs exactly once, or the name "Y"
never occurs, it's really hard to do this with grammar
rules - but you could add a set of formally-specified
conditions.  instead of a rule looking like

	nonterminal "="  *symbol

you could instead have

	nonterminal "=" *symbol [ ":" condition ]

where you have a separate language to describe conditions.
a condition might look like a Boolean expression, say,
using a subset of C syntax.

imagine a notation where #name would mean the number of times
the symbol 'name' was matchined within a rule and #(name:"string") 
would mean the number of times the nonterminal 'name' matched the
sequence of input symbols "string" within that rule.

then we could describe message headers more-or-less like this
(leaving out gory details of white space and folding)

	header = *(
		$return-path ":" return-path-body /
		$recipient ":" recipient-body /
		$from ":" from-body /
		"received" ":" received-body /
		$field-name ":" *text 
		) : #return-path == 1 &&
		    #(recipient:"to") == 1 &&
		    #(recipient:"cc") <= 1 &&
		    #(recipient:"reply-to") <= 1 &&
		    #from == 1 &&
		    #(field-name:"subject") <= 1
	
	return-path = "return-path"
	
	recipient = "to" / "cc" / "reply-to" 
	
	from = "from"
	
	field-name = atom
	 
and in fact we could leave out the $ syntax altogether. e.g.

        header = *(
                return-path ":" return-path-body /
                recipient ":" recipient-body /
                from ":" from-body /
                "received" ":" received-body /
                field-name ":" *text
                ) : #return-path == 1 &&
                    #(recipient:"to") == 1 &&
                    #(recipient:"cc") <= 1 &&
                    #(recipient:"reply-to") <= 1 &&
                    #from == 1 &&
                    #(field-name:"subject") <= 1

        return-path = "return-path"

        recipient = "to" / "cc" / "reply-to"

        from = "from"

        field-name = atom

the point is that while it really might be useful to specify
the "at least once" or "at most once" conditions formally,
rather than in prose - these aren't an issue for parsing - 
and ABNF is designed to specify parsing.  you want to parse 
these strings normally  only then then signal an error if 
the conditions are violated.  

so it make sense to specify the conditions separately from
the grammar.  OTOH I don't immediately see why ABNF couldn't
be extended in this way to allow the writer to define a set of
conditions to be checked after every rule.

it is a pain to implement in a general fashion-  it forces the 
recognizer to keep track of an arbitrary amount of state. 
but another nice thing about this notation is that it cleanly
separates the things that can easily be parsed from the 
conditions that typically have to be implemented in some other way.

Keith