Subject: Re: [Cbor] Parsing CDDL

From: Carsten Bormann <[email-masked]>
Date: Wed, 1 Aug 2018 10:58:29 +0200

> On Aug 1, 2018, at 00:58, David Brown <[email-masked]> wrote:
> 
> I have written up a small (220 line) parser based on the
> draft-ietf-cbor-cddl-03 document.  The code can be found at
> https://github.com/d3zd3z/suit-play/blob/master/cddl.rkt.  I used the
> Racket lexer and parser tools to make this easier.
> 
> I believe this parser parses (nearly) the same language described in
> the ABNF grammar in the draft (see below about spaces).  However, a
> couple of observations:
> 
> - in the rule for 'rule', since a 'type' by itself is a valid
>   'grpent', this rule is ambiguous.  I made the parser work by
>   simply commenting out the first alternate.  I would gather that a
>   tool using the output of this parser would have to store all
>   entities, and check that a name used elsewhere as a type must be
>   restricted to the ‘type' form.

Yes, that is the way the existing cddl tool is implemented.

Specifically, the ABNF given is “ambiguous” in the sense of

A = B

being parsable as both a type and a group.  This “ambiguity” does not cause any problems with the grammar, but needs unification before feeding the grammar to a classic parser generator).

(In a PEG parser, the first rule always matches, so there is no “ambiguity”.)

(I’m using “ambiguous” in quotes, because the spec is not ambiguous here — just the assignment of the parse to one or the other rule; both generate the same language.)

> - Spaces are a little complicated, and I'm not sure quite as
>   intended.  One production (for #6(...)) has a comment "note no
>   space", however there are a few other places that are missing
>   spaces (such as the space after the open paren on the
> 
>      "(" type ")"
> 
>   alternate.  

Right.  The grammar is trying to keep the opportunities for inserting spaces explicit, but that did not quite work out here (“type” allows for trailing, but not leading white space):

type = type1 S *(“/“ S type1 S)

This probably should be cleaned up to

type = type1 *(S “/“ S type1)

and then changing type2 as in:

type2 = value
      / typename [genericarg]
      / “(“ S type S “)”

> I found this much easier to handle by consuming spaces
>   in the lexer and not making them part of the grammar at all.  

Lexers made sense for certain environments and languages.
ABNF does not have them, so CDDL's ABNF grammar is not trying to introduce them.

> In
>   order to do this, three things:
> 
>      "#" "6" ["." uint] "(" S type S ")"
>      "#" DIGIT ["." uint]
> 
>      [uint] "*" [uint]
> 
>   must be captured by the lexer, since these production would make
>   the grammar ambiguous unless the space is not allowed.  

Right, if you insist on doing the lexer/parser split, you will have to split up the grammar to your liking.

There is an opportunity for catching more issues at the syntax level here by replacing DIGIT with NONTAGMAJOR as in

NONTAGMAJOR = %x30-35 / “7”

(Choose your preferred way to remove the cognitive dissonance the above line invariably creates.)

> I assume
>   the intent is to interpret these with "maximal munch" (mostly
>   thanks to the comma being optional).

Not sure what “these” is here — there are no commas in the above rules.

>   I also capture the repetition operation with numbers at lex time
>   to avoid additional ambiguity.

Again, if you must have a lexer, that approach does help here.

(The main remaining argument I sometimes hear for having a lexer is that it keeps noise out of the AST.
I prefer to have a parser with an AST generator that allows me to get a clean AST closer to the semantics I actually need.)

Grüße, Carsten