Subject: Re: [Suit] Parsing CDDL

From: Hannes Tschofenig <[email-masked]>
Date: Sat, 4 Aug 2018 17:50:40 +0000

Hi David,

Out of curiosity why did you write a CDDL parser? I would have expected that you would instead work on a small CBOR parser for use with bootloader.

Ciao
Hannes

-----Original Message-----
From: Suit [mailto:[email-masked]] On Behalf Of David Brown
Sent: 31 July 2018 16:01
To: [email-masked]
Subject: [Suit] Parsing CDDL

(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 -----

_______________________________________________
Suit mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/suit
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 4 Aug 2018 20:37:37 +0200

Hi Hannes, 

A generic CBOR parser is a useful component for a bootloader. However, might also translate CDDL into code that directly (maybe via a few library routines) consumes the binary CBOR.

Sent from mobile

> On 4. Aug 2018, at 19:50, Hannes Tschofenig <[email-masked]> wrote:
> 
> Hi David,
>

---

From: Michael Richardson <[email-masked]>
Date: Sat, 04 Aug 2018 14:37:45 -0400

Hannes Tschofenig <[email-masked]> wrote:
    > Out of curiosity why did you write a CDDL parser? I would have expected
    > that you would instead work on a small CBOR parser for use with
    > bootloader.

I think that David just wanted to validate the CDDL.
I took it to be more about about CDDL (as applied in the real world, such as
SUIT), than it is about SUIT itself.

    > ------- Forwarded Message

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Rønningstad, Øyvind <[email-masked]>
Date: Thu, 16 Aug 2018 14:20:07 +0000

This is great, David, though I’m not at all familiar with Racket, so I can’t really comment.

I’m hoping manifest parsing can be solved by a having a parser-generator generate, directly from CDDL, code that parses and validates CBOR data. The workflow I envision is: There is a canonical CDDL (the RFC) that is parsed to produce code that plugs into the rest of the SUIT implementation. The user can choose to edit the CDDL (preferably to represent a subset of the original), as a simple way to restrict their feature-set. I’m hopeful that the interface between the generated code and the code that uses it can be made flexible to such changes in the CDDL.

Øyvind

From: Suit [mailto:[email-masked]] On Behalf Of Carsten Bormann
Sent: 4. august 2018 20:38
To: Hannes Tschofenig <[email-masked]>
Cc: David Brown <[email-masked]>; [email-masked]
Subject: Re: [Suit] Parsing CDDL

Hi Hannes,

On 4. Aug 2018, at 19:50, Hannes Tschofenig <[email-masked]<mailto:[email-masked]>> wrote:
Hi David,

Ciao
Hannes

-----Original Message-----
From: Suit [mailto:[email-masked]] On Behalf Of David Brown
Sent: 31 July 2018 16:01
To: [email-masked]<mailto:[email-masked]>
Subject: [Suit] Parsing CDDL

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

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

  simply commenting out the first alternate..  I would gather that a

     "(" type ")"

     [uint] "*" [uint]

     item = [ int => bstr ]

     item = [ int, bstr, 5 ]

     groupname = (a b // c d)

     grp = (// //)

  is this intentional?

David Brown

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

_______________________________________________
Suit mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/suit
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

_______________________________________________
Suit mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/suit

---

From: David Brown <[email-masked]>
Date: Fri, 17 Aug 2018 15:10:38 -0600

>This is great, David, though I’m not at all familiar with Racket, so I can’t

I basically chose Racket for this because the language is fairly
oriented around extending itself with other grammars, and as such
includes numerous parsing tools.

>I’m hoping manifest parsing can be solved by a having a parser-generator
>generate, directly from CDDL, code that parses and validates CBOR data. The
>workflow I envision is: There is a canonical CDDL (the RFC) that is parsed to
>produce code that plugs into the rest of the SUIT implementation. The user can
>choose to edit the CDDL (preferably to represent a subset of the original), as
>a simple way to restrict their feature-set. I’m hopeful that the interface
>between the generated code and the code that uses it can be made flexible to
>such changes in the CDDL.

My goals are something along these lines.  My primary goal was just to
make sure I understood everything.  But, ideally, it would be nice to
have something that would read a CDDL description, and generate (using
a small library) code to parse or process that structure.

David