Subject: Re: [abnf-discuss] [art] [Technical Errata Reported] RFC7601 (5435)

From: Peter Occil <[email-masked]>
Date: Mon, 23 Jul 2018 08:19:48 -0400

You have pointed to an unexpected weakness of ABNF.  As a result, it's unfortunate that many ABNF productions in RFCs can't generally be used as is in order to build a parser, since ABNF itself has no strong concept of matching.  

For example, RFC 5234 sec. 3.2 is silent on which order alternative productions are to be matched (although this silence can be useful, I admit, in order for the incremental alternatives feature, sec. 3.3, to work).  The production "received-token" in RFC 5322 is illustrative:

   received-token  =   word / angle-addr / addr-spec / domain

Both "word" and "domain" include the production "atom".  Thus, whether a received-token parser parses an "atom" as a "word" or as a "domain" depends on the context in which the "atom" appears, the kind of parser (greedy or not), or whether earlier alternatives take precedence over latter alternatives or vice versa, none of which is defined in RFC 5234. "Obviously", if the "atom" is part of a domain, then the received-token should be the whole "domain" regardless of the details just mentioned.

[ Additional context: https://www.ietf.org/mail-archive/web/art/current/msg00571.html ]

From: John R. Levine
Sent: Sunday, July 22, 2018 10:33 PM
To: Peter Occil
Cc: Murray Kucherawy; [email-masked]; Alexey Melnikov; [email-masked]; [email-masked]
Subject: RE: [art] [Technical Errata Reported] RFC7601 (5435)

> And also, the erratum I submitted can be correct for handling certain 
> parsers that skip the CFWS in the “pvalue”, set the pointer to after the 
> CFWS (if any), and move on to parsing the next “CFWS propspec” within 
> the (current) “resinfo” production (in other words, the parser does 
> “greedy” matching).

ABNF doesn't have to be LL(k) or LR(k), so greedy parsers won't work, at 
least not without rewriting the rules to factor out ambiguities.

Regards,
John Levine, [email-masked], Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

---

From: "John R. Levine" <[email-masked]>
Date: 23 Jul 2018 10:49:02 -0400

On Mon, 23 Jul 2018, Peter Occil wrote:
> You have pointed to an unexpected weakness of ABNF.  As a result, it's 
> unfortunate that many ABNF productions in RFCs can't generally be used 
> as is in order to build a parser, since ABNF itself has no strong 
> concept of matching.

Of course they can, if you have adequate parser tools.  I shamelessly 
recomemnd "flex & bison", published by O'Reilly.  See the discussion of 
GLR parsers on pages 230-231.  Personally I'd refactor them to LL(1) 
or LR(1) but tastes differ.

More to the point, the IETF has used ABNF in its current form for over 20 
years, and it's not going to change now.  Its purpose is to specify valid 
syntax, even if the grammar parses that syntax ambiguously.  So please do 
send errata like the one on Received-SPF, where the ABNF didn't match the 
actual syntax, but if it's correct but ambiguous, that's not a bug.

Also, having written my share of compilers (try fitting a Fortran-77 front 
end into 48Kb on a PDP-11) I can assure you that I never was able to build 
a parser from an unmodified reference grammar.  You always need to 
refactor it.

> Both "word" and "domain" include the production "atom".  Thus, whether a received-token parser parses an "atom" as a "word" or as a "domain" depends on the context in which the "atom" appears, the…

R's,
John

---

From: Dave Crocker <[email-masked]>
Date: Mon, 23 Jul 2018 08:40:59 -0700

On 7/23/2018 7:49 AM, John R. Levine wrote:
> More to the point, the IETF has used ABNF in its current form for over 
> 20 years,

41 years.

The changes made in the document since ABNF's inception in 1977 -- as 
part of RFC 733 -- are helpful but not fundamental.

And I'll take this opportunity to cite an error in credit I've been 
making over the years...

Within the set of RFC 733 authors, I was the newbie with no formal 
training and wound up as editor of the document.  I spent an afternoon 
in a technical bookstore, getting a little background on parsers.  There 
were lots of specifications being written in those days that did 
variants of BNF; ours was merely one more.

I remember being concerned that we hit a good balance between features 
(complexity) and utility (usability).  And I remember worrying quite a 
bit about the formatting of the ABNF, since that affects comprehension. 
(I was, at the time, in a nascent Human-Computer Interaction graduate 
program.)

What I didn't remember until reviewing the Introduction to RFC 733, 
recently, is that the core credit for creating ABNF goes to Ken Harrenstein.

d/

-- 
Dave Crocker
Brandenburg InternetWorking
bbiw.net

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 23 Jul 2018 21:19:18 +0200

On Jul 23, 2018, at 14:19, Peter Occil <[email-masked]> wrote:
> 
> Thus, whether a received-token parser parses an "atom" as a "word" or as a "domain" depends on the context in which the "atom" appears,

Hi Peter,

actually, this is not how BNF traditionally works.

BNF is a productive grammar that produces a language.

It doesn’t tell you how to “parse”, i.e., assign rules to sections of the strings that make up the language.

E.g.,

  Foo = Bar / Baz

  Bar = “abc”

  Baz = “ab” “c”

is perfectly fine as BNF (here in ABNF form modulo the smartquotes) and takes no position on whether “abc” is a Bar or a Baz; it is certainly part of the language (as is “aBc” but that is a different story).

Clearly, parser generators do generate “parsers" that do want to know, so they are happier if the decision can be made.

When writing software based on ABNF, I generally prefer to use PEG (parse expression grammar) parsers instead of traditional BNF-based parser generators; this sometimes means I have to massage the ABNF slightly.  I also try to deliver my ABNF in PEG-friendly form.  But none of that is supported by RFC 5234 (STD 68).

CDDL (the ABNF derivative for CBOR and JSON) does prefer a clear assignment of specific rules to a subtree of the data model item tree; we are using PEG semantics for this.

BTW, the first RFC to use BNF (without actually using that word) was RFC 5 of June 2, l969 [sic!]; this wasn’t Ken L. Harrenstien's version of BNF but already somewhat close.  Prepare for the “BNF in RFCs” fiftieth anniversary in 10.5 months…

Grüße, Carsten