Subject: [Cbor] cddl 0.8.17: Add .abnf (draft-ietf-cbor-cddl-control)

From: Carsten Bormann <[email-masked]>
Date: Thu, 25 Feb 2021 23:58:24 +0100

After the discussion yesterday, I hacked together a quick PoC of the ABNF support in draft-ietf-cbor-cddl-control.

This is still rather rough:

* Error messages.  Ugh(*).
* It really conforms to RFC 5234, so *no leading whitespace* on your ABNF.
* I haven’t done .abnfb yet, and I expect some rough edges around the unicode handling in .abnf as well.

But the below example from the draft works (generate and validate), after fixing the leading whitespace.

The only surprise for me (beyond the fact that this stuff is so easy that I needed less than six hours to implement this PoC, after all) was how thoroughly I had forgotten about the leading whitespace limitation in RFC 5234 (before Julian Reschke reminded me in a completely unrelated thread a couple of days ago).  Of course, the bap tool has some adaptive handling here that makes this “feature” invisible to spec writers.

Not sure that this surprise should lead to changes in the draft.
The below spec example certainly is less readable than the text in the draft was.
We could add text that removes the common leading whitespace before processing the ABNF proper; this still requires the catted pieces to agree on the leading whitespace (which is bad if you are catting together pieces from different sources).  We could simply stipulate, say, two spaces.

Grüße, Carsten

(*) actually, my ABNF parser has pretty good error messages.
The integration into the (old version of the) CDDL tool is the bummer here.

start = [Tag0, Tag1004]

; for RFC8943:
Tag1004 = #6.1004(text .abnf full-date)
; for RFC 7049
Tag0 = #6.0(text .abnf date-time)

full-date = "full-date" .cat rfc3339
date-time = "date-time" .cat rfc3339

; Note the trick of idiomatically starting with a newline, separating
;   off the element in the .cat from the rule-list
rfc3339 = '
date-fullyear   = 4DIGIT
date-month      = 2DIGIT  ; 01-12
date-mday       = 2DIGIT  ; 01-28, 01-29, 01-30, 01-31 based on
                        ; month/year
time-hour       = 2DIGIT  ; 00-23
time-minute     = 2DIGIT  ; 00-59
time-second     = 2DIGIT  ; 00-58, 00-59, 00-60 based on leap sec
                        ; rules
time-secfrac    = "." 1*DIGIT
time-numoffset  = ("+" / "-") time-hour ":" time-minute
time-offset     = "Z" / time-numoffset

partial-time    = time-hour ":" time-minute ":" time-second
                [time-secfrac]
full-date       = date-fullyear "-" date-month "-" date-mday
full-time       = partial-time time-offset

date-time       = full-date "T" full-time
' .cat rfc5234-core

rfc5234-core = '
DIGIT          =  %x30-39 ; 0-9
; abbreviated here
'

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 26 Feb 2021 11:53:34 +0100

0.8.19 now implements .anbfb as well.

You can now do seriously weird things such as:

message = text .abnfb ("message" .cat rfc4505)

rfc4505 = '
message     = [ email / token ]
              ;; to be prepared in accordance with Section 3

UTF1        = %x00-3F / %x41-7F ;; less "@" (U+0040)
UTF2        = %xC2-DF UTF0
UTF3        = %xE0 %xA0-BF UTF0 / %xE1-EC 2(UTF0) /
              %xED %x80-9F UTF0 / %xEE-EF 2(UTF0)
UTF4        = %xF0 %x90-BF 2(UTF0) / %xF1-F3 3(UTF0) /
              %xF4 %x80-8F 2(UTF0)
UTF0        = %x80-BF

TCHAR       = UTF1 / UTF2 / UTF3 / UTF4
              ;; any UTF-8 encoded Unicode character
              ;; except "@" (U+0040)

email        = "[email-masked]"; for this example
;email       = addr-spec
              ;; as defined in [IMAIL]

token       = 1*255TCHAR
'

or

oid = bytes .abnfb ("oid" .cat cbor-tags-oid)

cbor-tags-oid = '
oid = 1*arc
roid = *arc
arc = [nlsb] %x00-7f
nlsb = %x81-ff *%x80-ff
‘

Enjoy!

Grüße, Carsten

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 26 Feb 2021 11:53:54 -0500

> The only surprise for me (beyond the fact that this stuff is so easy that I needed less than six hours to implement this PoC, after all) was how thoroughly I had forgotten about the leading whitesp…
...
> We could add text that removes the common leading whitespace before processing the ABNF proper; this still requires the catted pieces to agree on the leading whitespace (which is bad if you are cat…

Perhaps off topic here, but ...

IMO it would be good to make a revision to 5234 to resolve the leading 
whitespace issue. As it stands, there must be multitude of hacks to work 
around it, and AFAIK the assumptions made within those hacks are poorly 
documented and probably inconsistent.

The first thing to resolve would be to decide how to resolve the 
ambiguity when leading whitespace is allowed. Unfortunately I don't 
think there is any backward compatible extension that could itself be 
defined in abnf.

	Thanks,
	Paul

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 26 Feb 2021 18:42:05 +0100

> Perhaps off topic here, but ...

Well, there is no ABNF working group :-)
The CBOR WG with its CDDL work item actually is the closest you get at the moment.

> IMO it would be good to make a revision to 5234 to resolve the leading whitespace issue. As it stands, there must be multitude of hacks to work around it, and AFAIK the assumptions made within those hacks are poorly documented and probably inconsistent.

Yes, and the hacks are so prevalent that I actually had to build a tool based on the ABNF in 5234 to be reminded of it :-)

> The first thing to resolve would be to decide how to resolve the ambiguity when leading whitespace is allowed.

Is there one?
AFAIK, the only “problem” is lack of LL(1) parsing, and I don’t really care that much about that in 2021.

> Unfortunately I don't think there is any backward compatible extension that could itself be defined in abnf.

OK, I don’t think I can parse that before I understand the answer to my previous question.

Grüße, Carsten

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 26 Feb 2021 17:26:41 -0500

> Well, there is no ABNF working group :-)

True, but here is [email-masked]

> OK, I don’t think I can parse that before I understand the answer to my previous question.

The obvious revision would be to simply change the syntax of rule to:

      rule           =  WSP rulename defined-as elements c-nl

That seems unambiguous to me. But my formal parsing knowledge isn't 
sufficient to say if it is LL(1). BAP is old school and parses using 
yacc and lex. (And doesn't derive its parser from the abnf of abnf.) 
That means its an LALR parser.

Is there a public tool that can generate a parser from abnf that can 
parse abnf?

	Thanks,
	Paul

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 27 Feb 2021 00:51:55 +0100

Hi Paul,

>     rule           =  WSP rulename defined-as elements c-nl

Well, a single WSP won’t cut it…

    rule           =  *WSP rulename defined-as elements c-nl

> 
> That seems unambiguous to me. But my formal parsing knowledge isn't sufficient to say if it is LL(1).

Once you allow white space before rulenames, it is most definitely not LL(1).

When you see…

A = B
  C

…you need to look ahead one more to distinguish, say…

A = B
  C = D
(New rule)

…from…

A = B
  C D
(Still in same rule.)

I do think it is LL(2), but I didn’t formally check.

I think that’s why 5234 insists on having an indent on continuation lines, as in

         c-wsp          =  WSP / (c-nl WSP)

(Having at least one WSP after a c-nl identifies the line as continuation line.)

So a naive parser can parse out the rule structure by simply throwing away comments and newlines before leading whitespace and combining them into rules.

If this looks like RFC 822 continuation lines to you, that is not a surprise :-) 
(Ken L. Harrenstien invented the ABNF notation for RFC 733 that then became RFC 822; previous versions of this document had used a more conventional ::= style BNF as in
         <field>           ::=   <field-name> ":" <field-body>
         <field-body>      ::=   <field-body-contents>
                               | <field-body-contents> <crlf>
                                    <linear-white-space-char>
                                    <field-body>
in RFC 724.  Shudder.)

> BAP is old school and parses using yacc and lex.

The trick is that BAP's lexer (scanner.l) keeps a current indent.
When that is not set, leading whitespace is ignored.
When a rule name is first seen, the indent is set to the current column.
After that, lines that have less leading whitespace than the indent cause warnings; the indent is essentially removed from the view of the parser.

The effect is pretty close to

indent = spec.lines.grep(/\S/).map {|l| l[/^\s*/].size}.min
spec = spec.lines.map {|l| l.sub(/^\s{#{indent}}/, "")}.join

…which I’m contemplating putting into the ABNF support of the CDDL tool (but then would need to get into the text of the CDDL .abnf spec as well).

> (And doesn't derive its parser from the abnf of abnf.) That means its an LALR parser.

Yes.  With those scanner hacks.

> Is there a public tool that can generate a parser from abnf that can parse abnf?

Well, I have been using my abnftt tool(*), https://github.com/cabo/abnftt
as part of the CDDL tool’s ABNF capability.  It converts an ABNF grammar into a PEG grammar (in “treetop” syntax); this can then be used for validation.
Note that a PEG grammar behaves slightly different from a traditional BNF grammar, so I had to make this change to the ABNF grammar of ABNF:

         defined-as     =  *c-wsp ("=" / "=/") *c-wsp
➔
         defined-as     =  *c-wsp ("=/" / "=") *c-wsp

(PEG rules make the first “=“ stick before the “=/“ can match; this is called “prioritized choice”.)

I once heard there is an ANTLR module for ABNF (not just an ANTLR parser for ABNF!), but I didn’t follow up.

Who else should we draw into this conversation?

Grüße, Carsten

(*) which is a rewrite of the abnc tool that I used to align the ABNF in Appendix A of RFC 4997 https://tools.ietf.org/html/rfc4997#appendix-A with that RFC’s examples (note the case-sensitive literals on the next page :-).
The abnc tool still is the core of the CDDL tool, which I need to port to abnftt…

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 27 Feb 2021 14:36:52 +0100

So RFC 5234 has this indentation problem:

cbor-tags-oid = '
  oid = 1*arc
  roid = *arc
  arc = [nlsb] %x00-7f
  nlsb = %x81-ff *%x80-ff
'

…does not work, as the ABNF is indented, which is not allowed by RFC 5234.
Outdenting the ABNF works, but reduces readability (it also is too easy to confuse  ABNF with CDDL rules!).

So how do we make something like the above work?

(1) We could fix ABNF.  This is an Internet Standard, so I’d expect this to be a slow process; we want to be done with the new controls earlier than that.
(2) We could make CDDL work with ABNF as is, but still allow something like the above.

Now how can we do (2):

(2a) We define .abnf/.abnfb to ignore leading whitespace.  This requires some elaborate rules like the ones bap uses (see previous mail).  The main problem with this is that if the ABNF is concatenated together from different sources, these must agree on the amount of leading whitespace for this to work.  And this is rather likely as 5234 and other places define “libraries” that need to combined with ABNF from protocol spec RFCs.

(2b) We leave .abnf/.abnfb as is, and define an outdenting version of .cat.
Let’s call that .bat for the moment.

Fix the above example:
oid = bytes .abnfb ("oid" .bat cbor-tags-oid)
Done.

More precisely, .bat takes its controller (right hand side argument), computes the indent (leading whitespace of least-indented non-blank line), and reduces the amount of leading whitespace on each line by the indent.

This is only done on the right hand side as it fits the most common use cases.  It also allows keeping some leading whitespace for the target (left hand side argument).  If really both sides need to be outdented, use something like

ant<v1, v2> = ("" .bat v1) .bat v2

As the outdenting is done before concatenation, .bat has no problems dealing with pieces that are indented by different amounts.

I have little problem with introducing this control operator, as there are features in other languages that have similar outdenting semantics, e.g., <<~ in Ruby.

CDDL tool 0.8.20 has .bat, if you want to play with that.

The retronym generation process for .bat is now officially started (or maybe you have a different name for this that also is short and to the point; .cat-with-undenting-of-right-hand-side is not it).

Grüße, Carsten

---

From: Paul Kyzivat <[email-masked]>
Date: Sat, 27 Feb 2021 10:41:40 -0500

> I do think it is LL(2), but I didn’t formally check.

If there is no separate lexer, so that terminal symbols are all single 
bytes, then isn't the required effectively unbounded?

> Who else should we draw into this conversation?

We should restart the discussion on abnf-discuss.

	Thanks,
	Paul

---

From: Paul Kyzivat <[email-masked]>
Date: Sat, 27 Feb 2021 10:50:12 -0500

Fixing the indentation problem by removing common leading whitespace 
breaks if both spaces and HT are used in varying combinations to achieve 
the indentation. You can try to fix that by transforming HT into spaces 
using the algorithm of your choice, but it fails if your algorithm 
differs from that used by the author of the abnf.

That argues for "fixing" abnf itself. But I agree that won't happen 
quickly if at all.

	Thanks,
	Paul

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 27 Feb 2021 17:02:31 +0100

Good point for older languages (it is fun to read the discussion about HT issues when <<~ was introduced to Ruby).
But literal HT is not allowed in CDDL(*), so we are covered there.

Grüße, Carsten

(*) Yeah, you could enter it in hex or base64url.  But that doesn’t turn it into whitespace we would be concerned with.

> On 27. Feb 2021, at 16:50, Paul Kyzivat <[email-masked]> wrote:
> 
> Fixing the indentation problem by removing common leading whitespace breaks if both spaces and HT are used in varying combinations to achieve the indentation. You can try to fix that by transforming HT into spaces using the algorithm of your choice, but it fails if your algorithm differs from that used by the author of the abnf.
> 
> That argues for "fixing" abnf itself. But I agree that won't happen quickly if at all.
> 
> 	Thanks,
> 	Paul
>

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 27 Feb 2021 20:30:51 +0100

The CBOR WG maintains CDDL, the ABNF equivalent for data structured in a JSON or CBOR like manner.

Over at [email-masked], we are currently discussing the integration of ABNF support into CDDL for describing the content of text and byte strings [1].  

[1]: <https://www.ietf.org/archive/id/draft-ietf-cbor-cddl-control-02.html#name-embedded-abnf>

A prototype for that support already is implemented in the original CDDL tool; support in another CDDL tool is in progress.

The one surprise that I had when I implemented this was that I had completely forgotten that ABNF is indentation sensitive (or, more precisely, rules out indentation except on continuation lines, where indentation is required).  Tools like BAP have been working around this aspect in a sufficiently effective way that I simply lost track of that fact.

I think we have a way forward for dealing with this in CDDL (namely, dealing with indentation before handing over parts to ABNF).
But several interesting side discussions ensued, and Paul suggested below that maybe we should take this to abnf-discuss now.

One question was how the fact that proper ABNF does not accept indentation on a rule can be repaired.  A followup question was, of course, how much the parsing of ABNF depends on the way indentation is handled.  More below; a whole thread is in the archive [2].  (Another question is how a relaxed syntax could be expressed in ABNF itself.)

[2]: <https://mailarchive.ietf.org/arch/msg/cbor/p5D3G6DNy5ZAiurp2HLA4E8VtAM>

Opinions welcome; I have set reply-to to abnf-discuss (but am aware that this setting is ignored for wide-replies by most mail readers).

Grüße, Carsten

> On 2021-02-27, at 16:41, Paul Kyzivat <[email-masked]> wrote:
> 
> If there is no separate lexer, so that terminal symbols are all single bytes, then isn't the required effectively unbounded?
> 
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor