4 ms·

Hi all! While developing a text and binary data format (https://concise-encoding.org/ https://concise-encoding.org/), I ran into trouble building a formal desc

Hi all! While developing a text and binary data format (https://concise-encoding.org/ https://concise-encoding.org/), I ran into trouble building a formal description for them. Many formats use EBNF or ABNF, or just embed their own BNF-style metalanguage in the spec itself (I started taking cues from the XML spec). But describing a binary format is deceptively complex, and eventually I had to split out the metalanguage. KBNF is the result. I want it to be useful for other people, so I've decided to release it standalone here: https://github.com/kstenerud/kbnf/blob/master/kbnf_v1.md https://github.com/kstenerud/kbnf/blob/master/kbnf_v1.md I'd really appreciate some proofreading, as right now the only way I'm able to effectively find issues is to let it sit for a couple of weeks so that I can look at it from a fresh viewpoint, and even then I'm not confident that I'm discovering as much as multiple eyes could. Cheers!

unwind 4y ago
This looks really interesting, thanks for doing all that work and sharing. Two minor points of feedback: - The name is "strange", since "Backus-Naur" is already labelling the form as being theirs, adding a possessive to the front kind of clashes, for me. - There's a tiny typo in the Non-Greedy example, "terminaor" is missing a "t". :) Good luck with the project(s), of course!
- robertlagrant 4y ago
  Yes, I came to say the same. Is Backus okay with you naming a metasyntax after him?
  - omnicognate 4y ago
    He's probably indifferent, having died 16 years ago.
- kstenerud 4y ago
  Yes, TBH I'm a little stuck coming up with a name. I want it to be evident that this follows in the footsteps of the Backus-Naur form (for familiarity's sake), but I don't want to do something crass like call it "Ultimate Backus-Naur form" or something. We already have "Advanced Backus-Naur Form" and "Extended Backus-Naur form" and will eventually run out of superlatives...
  - jononor 4y ago
    Do some something that sounds similar but writes differently? Like a rhyme. Knacknus Saur, Binackus Naurackus, ?
aardvark179 4y ago
When you give an example of things being non-greedy by default why does azzzbzzzczzz represent a document with 3 records rather than 3 documents? We intuitively understand why, but without defining document as special, making it consume records eagerly, or defining anchors for the start and end of the data, I think the example may be incorrect.
- kstenerud 4y ago
  Whoops you're quite correct! It needs an end anchor or something.
mkl 4y ago
What can you do with it? Do you have a parser generator or grammar validator? Is the & really necessary? It seems to me like they could be removed without losing anything (but it is late at night here so I may be missing something). Related to the previous question, if & is necessary are there typos in "byte(type) byte(bind(length, ~)) & byte(~){length};" and "'(' & TOKEN_SEP item TOKEN_SEP & ')';", which are missing some?
- kstenerud 4y ago
  There's no parser generator; its primary purpose is to document how a format looks and works (similar to what ABNF and EBNF do). I am trying to make it consistent enough that tools could be made for it, however. The & is something I added later, and I thought I'd updated all of the examples but I must have missed some. Using whitespace as an operator was just causing too much trouble and making the more complex grammars harder for a human to follow, which is why I opted to make every operation require an actual symbol, and leave whitespace without semantic value.
  - UncleEntity 4y ago
    > Using whitespace as an operator was just causing too much trouble and making the more complex grammars harder for a human to follow… Something (it’s late and I don’t quite remember) I’ve been playing with lately defines a rule named ‘_’ as the whitespace token so the grammars are both easily read and clear. Be like: _ = [ \t]+ a = b _ (c | d) _ e
anentropic 4y ago
Have you seen this? https://kaitai.io/ https://kaitai.io/ (Disclaimer: I've never needed or used it, but stumbled upon it a while back and just filed it away for future reference)
teddyh 4y ago
Isn’t specifying binary formats exactly what ASN.1 is made for?

unwind 4y ago

This looks really interesting, thanks for doing all that work and sharing. Two minor points of feedback: - The name is "strange", since "Backus-Naur" is already labelling the form as being theirs, adding a possessive to the front kind of clashes, for me. - There's a tiny typo in the Non-Greedy example, "terminaor" is missing a "t". :) Good luck with the project(s), of course!

robertlagrant 4y ago
Yes, I came to say the same. Is Backus okay with you naming a metasyntax after him?
- omnicognate 4y ago
  He's probably indifferent, having died 16 years ago.
kstenerud 4y ago
Yes, TBH I'm a little stuck coming up with a name. I want it to be evident that this follows in the footsteps of the Backus-Naur form (for familiarity's sake), but I don't want to do something crass like call it "Ultimate Backus-Naur form" or something. We already have "Advanced Backus-Naur Form" and "Extended Backus-Naur form" and will eventually run out of superlatives...
- jononor 4y ago
  Do some something that sounds similar but writes differently? Like a rhyme. Knacknus Saur, Binackus Naurackus, ?

aardvark179 4y ago

When you give an example of things being non-greedy by default why does azzzbzzzczzz represent a document with 3 records rather than 3 documents? We intuitively understand why, but without defining document as special, making it consume records eagerly, or defining anchors for the start and end of the data, I think the example may be incorrect.

kstenerud 4y ago
Whoops you're quite correct! It needs an end anchor or something.

mkl 4y ago

What can you do with it? Do you have a parser generator or grammar validator? Is the & really necessary? It seems to me like they could be removed without losing anything (but it is late at night here so I may be missing something). Related to the previous question, if & is necessary are there typos in "byte(type) byte(bind(length, ~)) & byte(~){length};" and "'(' & TOKEN_SEP item TOKEN_SEP & ')';", which are missing some?

kstenerud 4y ago
There's no parser generator; its primary purpose is to document how a format looks and works (similar to what ABNF and EBNF do). I am trying to make it consistent enough that tools could be made for it, however. The & is something I added later, and I thought I'd updated all of the examples but I must have missed some. Using whitespace as an operator was just causing too much trouble and making the more complex grammars harder for a human to follow, which is why I opted to make every operation require an actual symbol, and leave whitespace without semantic value.
- UncleEntity 4y ago
  > Using whitespace as an operator was just causing too much trouble and making the more complex grammars harder for a human to follow… Something (it’s late and I don’t quite remember) I’ve been playing with lately defines a rule named ‘_’ as the whitespace token so the grammars are both easily read and clear. Be like: _ = [ \t]+ a = b _ (c | d) _ e

anentropic 4y ago

Have you seen this? https://kaitai.io/ https://kaitai.io/ (Disclaimer: I've never needed or used it, but stumbled upon it a while back and just filed it away for future reference)

teddyh 4y ago

Isn’t specifying binary formats exactly what ASN.1 is made for?