Subject: Proposal of Non-Sequential Group Notion in ABNF w/ a SIP case

From: Munjo Yu <[email-masked]>
Date: Wed, 1 Apr 2009 20:17:58 -0500

Hi all,

I am Munjo Yu and currently working with Jong Sung Kim of a network
solution start-up in Korea, VineGen Inc.
During the 74th IETF in San Francisco, Dave Crocker and Lisa Dusseault
suggested us to post in the Application mailing list.
And I thought the SIP mailing list is a good place too, since we have
a use case of our extension with SIP.

Jong Sung Kim noticed there should be a better version of the ABNF
definition section of RFC 3261
while developing a "complete" ABNF parser generator.
The parser generator is complete in the sense that generated parser code
does not need any hand coding.

In Section 7 of RFC 3261, Request is defined like following.

   Request        =  Request-Line
                     *( message-header )
                     CRLF
                     [ message-body ]

where,

   message-header  =  (Accept
                   /  Accept-Encoding
                   .
                   /  Call-ID
                   .
                   /  CSeq
                   .
                  /  Via
                   .
                  /  extension-header) CRLF

I omitted most part of the long "message-header" for sake of readability.

>From the above, one can tell that *(message-header) achieves a group
whose elements are
non-sequential and optional.
So, any of the following complies with the definition.

() ; empty group
(Accept)
(Accept, Accept)
(Accept, Call-ID)
(Call-ID, Accept)

and so on.

However, only a small portion of all the possible combinations
are legitimate according to some sections like 8.1.1 as follows.

   8.1.1 Generating the Request

      A valid SIP request formulated by a UAC MUST, at a minimum, contain
      the following header fields: To, From, CSeq, Call-ID, Max-Forwards,
      and Via; all of these header fields are mandatory in all SIP
      requests.  These six header fields are the fundamental building
      blocks of a SIP message,
      .
      .

As shown above, few elements like To, From, CSeq, are mandatory - the
first sign that the ABNF definition is not self-contained.
In fact, all the "additional" definitions of message-header are
embedded in various sections in the RFC
, which makes it impractical ( if not impossible ) to build a complete
parser generator.

So, Jong Sung Kim had to add an extension, "non-sequential" group to ABNF, and
he named it as SET whose is already available elsewhere like ASN.1

SET is described simply as follows, using a pair of braces:

SET                             {Rule1 Rule2}

Using SET, a redefinition of the above Request is something like following:

   Request        =  Request-Line
                     message-header
                     CRLF
                     [ message-body ]

where,

   message-header  =  {
                   Call-ID
                   CSeq
                   .
                  1*Via
                   .
                  0*1Accept
                  0*1Accept-Encoding
                   .
                  0*1extension-header} CRLF

This new version makes quite a few parts of the RFC paragraphs
unnecessary and redundant, resulting in a self-contained,
straightforward, easy-to-maintain, and parser generator friendly
definition.

We'd like to know what SIP folks would think about this,
and if there are other cases that can benefit from this extension.
Also would like to hear from App folks, such as
balance between feature and simplicity, architectural point, etc.

Regards,
-Munjo Yu

P.S. we'd like to express our thanks to Dave Crocker and Lisa Dusseault,
and other WG chairs for their help and kindness during the meeting.

---

From: "eburger" <[email-masked]>
Date: Thu, 2 Apr 2009 01:26:51 +0000

Personally, I don't understand why we didn't just use YACC. I am really in favor of using a formal language for specifying grammar. As Munjo states, the ABNF is essentially documentation fluff - useless at best and wrong at worst. 

As for this particular suggestion, I am ambivalent as to whether we hack ABNF, adopt YACC, or even adopt ASN.1. 

--
Eric Burger

Sent from my mobile device; sorry if terse. All mobile users need lemonade.  See <http://www.standardstrack.com/ietf/lemonade> for more information.

-----Original Message-----
From: Munjo Yu <[email-masked]>

Date: Wed, 1 Apr 2009 20:17:58 
To: <[email-masked]>; <[email-masked]>
Subject: Proposal of Non-Sequential Group Notion in ABNF w/ a SIP case

Hi all,

   Request        =  Request-Line
                     *( message-header )
                     CRLF
                     [ message-body ]

where,

   message-header  =  (Accept
                   /  Accept-Encoding
                   .
                   /  Call-ID
                   .
                   /  CSeq
                   .
                  /  Via
                   .
                  /  extension-header) CRLF

() ; empty group
(Accept)
(Accept, Accept)
(Accept, Call-ID)
(Call-ID, Accept)

and so on.

SET                             {Rule1 Rule2}

   Request        =  Request-Line
                     message-header
                     CRLF
                     [ message-body ]

where,

   message-header  =  {
                   Call-ID
                   CSeq
                   .
                  1*Via
                   .
                  0*1Accept
                  0*1Accept-Encoding
                   .

Regards,
-Munjo Yu

P.S. we'd like to express our thanks to Dave Crocker and Lisa Dusseault,
and other WG chairs for their help and kindness during the meeting.
_______________________________________________
Apps-Discuss mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/apps-discuss

---

From: Keith Moore <[email-masked]>
Date: Thu, 02 Apr 2009 00:55:37 -0400

If memory serves, we discussed a very similar
notation within the DRUMS working group (around 12 years ago), which is
where the RFC 822 ABNF was generalized

to its present form.  Obviously we decided not to include it.  I don't
recall

why, but I think it had something to with the fact that having the n*m
notation mean one thing when applied to an expression outside of a
"SET", and something else when used inside a "SET", creates an
ambiguity in the notation.  You can resolve the ambiguity by various
means, but the trick is to keep the result from being

confusing to humans.

Keith

Hi all,

Request = Request-Line
*( message-header )
CRLF
[ message-body ]

where,

message-header = (Accept
/ Accept-Encoding
.
/ Call-ID
.
/ CSeq
.
/ Via
.
/ extension-header) CRLF

whose elements are

() ; empty group
(Accept)
(Accept, Accept)
(Accept, Call-ID)
(Call-ID, Accept)

and so on.

SET {Rule1 Rule2}

Request = Request-Line
message-header
CRLF
[ message-body ]

where,

message-header = {
Call-ID
CSeq
.
1*Via
.
0*1Accept
0*1Accept-Encoding
.

Regards,
-Munjo Yu

---

From: Keith Moore <[email-masked]>
Date: Thu, 02 Apr 2009 00:59:10 -0400

eburger wrote:

Personally, I don't understand why we didn't just use YACC.

Exercise: write an RFC ?822 parse in yacc.  It can be done, but not
easily, as the RFC ?822 grammar is not LALR(1).

I am really in favor of using a formal language for specifying grammar. As Munjo states, the ABNF is essentially documentation fluff - useless at best and wrong at worst.

One lesson from the DRUMS effort - rewrite an existing grammar at your
peril.  Even if the old specification has errors, writing a new grammar
which verifiably recognizes exactly the same language as the old one
can be difficult.  And even if you restrict the language that new
implementations can emit, you generally have to accept the old language
for compatibility's sake.  So you end up with two grammars where one
was formerly (almost) good enough.

Keith

---

From: Keith Moore <[email-masked]>
Date: Thu, 02 Apr 2009 19:46:02 -0400

Paul Kyzivat wrote:
> I agree with Keith about the inadvisability of rewriting the grammar.
> Save it for SIP/3.0.
>
> In any case, I think the issue isn't with ABNF per se, its with the
> way ABNF was used for SIP. ABNF isn't actually able to represent
> everything that was desired for sip, so some things were simply
> handled as exceptions in the text.
>
> Of course the "right" thing to do would have been to either give up on
> anything that couldn't legitimately be represented, or else switch to
> some other specification language that could express what was intended.
not clear.  IMHO, trying to specify every aspect of detail of a protocol
syntax using a formal specification language can be misleading and cause
more interop failures, than a looser specification written in ABNF plus
some exceptions in the text.   One reason for the additional failures
when using the precise formal specification is that you don't really
benefit from that specification unless you feed it to a program that
will automatically generate the recognizer.  And if you do automatically
generate a recognizer from the formal specification, you often find that
it doesn't report errors in the way that you'd like, doesn't perform as
well as you want, etc.

The trick is to design the protocol in such a way that a precise formal
syntax specification is not necessary.   This implies having a certain
degree of simplicity and regularity in the protocol.
>
> But there is a big tradeoff there. At least many people are capable of
> reading ABNF, and a reasonable number of those can accurately
> understand what it means. A somewhat smaller, but still significant,
> number can write it correctly. Its important that the people involved
> in the standardization process, and that implement the standard, be
> able to understand it. A more powerful specification language, that
> fewer people could understand, might not be such a great choice.
exactly.

Keith

---

From: Munjo Yu <[email-masked]>
Date: Thu, 2 Apr 2009 19:01:53 -0500

Thanks for the historical insights.
Yes, I found the following section from
http://tools.ietf.org/html/draft-ietf-drums-abnf-02

    3.5 Set Group: {Rule 1 Rule2}

    Elements enclosed in braces (squiggly brackets) are treated
    as a single, UNORDERED element.  Its contents may occur in
    any order.  Hence:

         {elem foo} bar

    would match (elem foo bar) and (foo elem bar).

    NOTE: Specifying alternatives is quite different from
    specifying set grouping.  Alternatives indicate the matching
    of exactly one (sub-)rule out of the total grouping.  The set
    mechanism indicates the matching of a string which contains
    all of the elements within the group; however the elements
    may occur in any order.

And it was dropped from the following revisions.
To understand the ambiguity Keith mentioned, I tried to find any
discussion archives which led to the decision, but no luck so far.
Anyone knows about such an archive somewhere?

thanks,
-Munjo

---

From: John C Klensin <[email-masked]>
Date: Thu, 02 Apr 2009 21:46:53 -0400

--On Thursday, April 02, 2009 19:46 -0400 Keith Moore
<[email-masked]> wrote:

> not clear.  IMHO, trying to specify every aspect of detail of
> a protocol syntax using a formal specification language can be
> misleading and cause more interop failures, than a looser
> specification written in ABNF plus some exceptions in the
> text.   One reason for the additional failures when using the
> precise formal specification is that you don't really benefit
> from that specification unless you feed it to a program that
> will automatically generate the recognizer.  And if you do
> automatically generate a recognizer from the formal
> specification, you often find that it doesn't report errors in
> the way that you'd like, doesn't perform as well as you want,
> etc.

Yes.  And if the protocol is even nearly as complicated as SIP,
you need a formal language that can specify semantics as well as
syntax to get even close to a full description of the protocol.
Syntax alone just doesn't do it.  I would slightly disagree with
Keith's characterization because those things can be good for
generating reference implementations that can be checked against
production ones to see if the latter are working correctly.  But
I agree that such a reference implementation isn't likely to be
something one would like to use in production for the reasons he
gives.

I could suggest a few specification languages of that variety
from experience (and there are more in the literature), but, as
you point out...

>> But there is a big tradeoff there. At least many people are
>> capable of reading ABNF, and a reasonable number of those can
>> accurately understand what it means. A somewhat smaller, but
>> still significant, number can write it correctly. Its
>> important that the people involved in the standardization
>> process, and that implement the standard, be able to
>> understand it. A more powerful specification language, that

>...
the languages that can be used to specify not just static syntax
but semantics and actions require serious work to understand how
to read and even more to be able to write, leading to only a
small population who can really understand such a specification.
That is usually considered bad news although I've been in
situations in which it is considered job security.

> The trick is to design the protocol in such a way that a
> precise formal syntax specification is not necessary.   This
> implies having a certain degree of simplicity and regularity
> in the protocol.

Unfortunately, SIP probably fails the test that implies.  And no
alternate choice of specification method is going to change that.

    john

---

From: Paul Kyzivat <[email-masked]>
Date: Thu, 02 Apr 2009 19:21:55 -0400

In any case, I think the issue isn't with ABNF per se, its with the way 
ABNF was used for SIP. ABNF isn't actually able to represent everything 
that was desired for sip, so some things were simply handled as 
exceptions in the text.

But there is a big tradeoff there. At least many people are capable of 
reading ABNF, and a reasonable number of those can accurately understand 
what it means. A somewhat smaller, but still significant, number can 
write it correctly. Its important that the people involved in the 
standardization process, and that implement the standard, be able to 
understand it. A more powerful specification language, that fewer people 
could understand, might not be such a great choice.

	Thanks,
	Paul

Keith Moore wrote:
> which verifiably recognizes exactly the same language as the old one can 
> be difficult.  And even if you restrict the language that new 
> for compatibility's sake.  So you end up with two grammars where one was 
> formerly (almost) good enough.
> 
> Keith
> 
> 
> ------------------------------------------------------------------------
> 
> Sip mailing list  https://www.ietf.org/mailman/listinfo/sip
> This list is for NEW development of the core SIP Protocol
> Use [email-masked] for questions on current sip
> Use [email-masked] for new developments on the application of sip

---

From: "Dale Worley" <[email-masked]>
Date: Fri, 10 Apr 2009 17:56:41 -0400

> SET is described simply as follows, using a pair of braces:

As a start, I would like to see a fully accurate description of how the
SET construction is written, and what its significance is.  Given that
SET is a *tool for writing specifications*, we must be careful to define
it exactly.  Currently, all we have is one example of its use.

Dale

---

From: Munjo Yu <[email-masked]>
Date: Tue, 14 Apr 2009 19:48:54 -0400

Hi all, again.

We find two keywords from the responses.

- trade-off between features and simplicity
- ambiguities in Set

These two may well have been the main reasons why Set was dropped from
the draft 3
(http://tools.ietf.org/html/draft-ietf-drums-abnf-03) about 12 years ago.
Since then, Internet flourished and so did protocols.
Along the line, the pivot for trading off might have shifted towards
"features" from "simplicity" a little bit, we wonder.
And we still hope that overall gain from adding "Set" might be positive.

The biggest advantage of introducing Set again is:

- self-contained definitions in describing a message whose components
can come unordered.
- more readability
- far better for parser generation

And of course, we sacrifice its simplicity, a little bit.

The following is a writing of Set specifications.
We are looking forward to hearing overall integrity concerns, among
other things.

3.6.  Variable Repetition:  *Rule
.
.

3.6.1. Element's Repetition in Sequence, Concatenation, etc, other than Set
   An element with a repetition is expanded sequentially.

   Example: Element's Repetition in non-Set types which results in forming
                a Sequence group
       3A = (A A A)

   So, ...
   Example: Sequence Group in a Set
      set  =  {(3A) X}  = {(A A A) X} =  ((A A A) X)/ (X (A A A)) =
(A A A X) / (X A A A)

   Example: Sequence Group in Set
       set = {(A B C) X} = (A B C X) / (X A B C)

3.6.2. Element's Repetition in Set
   An element with a repetition in a Set is expanded non-sequentially.

   Example: Element's Repetition in Set
       set   =  {3A X}  = {A A A X} = (A A A X)  / (A A X A)  / (A X
A A) / (X A A A)

3.6.3. Set's Repetition
  A Set with a repetition is expanded only atomically.
  Example:
      SETa   =  {A B}
      2SETa = 2{A B} = 2((A B)/(B A)) = ((A B) (A B)) / ((B A) (B A))
= (A B A B) / (B A B A)

********************

4.  ABNF Definition of ABNF
.
.

        element        =  rulename / group / set / option /
                          char-val / num-val / prose-val

        set            =  "{" repetition *(1*c-wsp repetition ) "}"
                           ; repetitions in any order

Note that the rule "element" above now includes "set" and the rule set
is of course
the new addition for Set.

In addition to probing into this new specifications, please raise a
red flag for any possible disruptions of existing RFCs by this new
Set, even though we are pretty sure that no existing specifications
would be affected by this change.

Thanks,
-Munjo Yu, VineGen Inc.