Subject: [Suit] Parsing CDDL

From: David Brown <[email-masked]>
Date: Tue, 31 Jul 2018 17:01:18 -0600

(I posted this to the IETF CBOR mailing list, and replies related to
CBOR/CDDL should be there.  I am posting this to the SUIT mailing list
because of our interest in CDDL, and that we discovered one of the
ambiguities in the CDDL draft)

----- Forwarded message from David Brown <[email-masked]> -----

Date: Tue, 31 Jul 2018 16:58:54 -0600
From: David Brown <[email-masked]>
To: [email-masked]
Subject: Parsing CDDL

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.

 - 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.  I found this much easier to handle by consuming spaces
   in the lexer and not making them part of the grammar at all.  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.  I assume
   the intent is to interpret these with "maximal munch" (mostly
   thanks to the comma being optional).

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

 - The ABNF grammar references code points such as %x5D-10FFFD.  Is
   it intentional to include the invalid range D800-DFFF, which are
   reserved for surrogate pairs in UTF-16?  They are not considered
   valid codepoints for UTF-8, and depending on the tools/language
   used, may be rejected before codepoints are given to the parser.

 - The text of the draft states that hexidecimal numbers "... are
   case insensitive", however the ABNF grammar only accepts
   hexidecimal digits in uppercase.

 - There are productions allowed by the grammar whose meaning is not
   described by the text of the draft.  For example:

      item = [ int => bstr ]

   is valid with the grammar, but it is unclear what this means.
   Perhaps this could describe an ordered map, or an array of pairs
   of items.  Related are arrays that contain more than a single
   item:

      item = [ int, bstr, 5 ]

 - What is the intended interpretation of:

      groupname = (a b // c d)

   My parser interprets this as ((a b) // (c d)), however
   (a (b // c) d) is also a valid interpretation, an probably what is
   intended, especially if commas are used  (a, b // c, d).

 - Related to the above, the grammar allows things like like

      grp = (// //)

   is this intentional?

With some work, I believe it would be possible to transform this
grammar into something LALR(1) (my grammar is part way there), but it
would make some of the productions difficult to read.  However, it may
be a useful exercise because it would force any other ambiguities in
the grammar.

I wrote this starting with a LALR(1) parser, and wrote as much as I
could without any shift/reduce conflicts, and reverted to a general
backtracking parser near the end.  The LALR(1) parser is significantly
easier to debug, and tends to produce better error messages.

David Brown

----- End forwarded message -----