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

[Carsten Bormann <[e-mail]>]

Hi Paul,

> The obvious revision would be to simply change the syntax of rule to:
> 
>     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…