What is the grammar of network protocols and file formats?

Question

For network protocols and/or file formats with fixed length fields, the grammar is fairly simple, and can be explained with a regular expression.

However, for protocols with varying data lenghts, there is almost always a fixed-length field preceding the data that gives the length of that data.

Without going into details of protocol/format specifications, we can talk about its equivalents in grammar notation. For example, consider the following production rule:

A -> anb^n

where 'a' is some fixed-length symbol, 'n' is a non-negative integer, and b^n is b repeated n times.

I'm having trouble understanding how such a rule can capture the fact that the value of 'n' is somehow related to how many b's are present in the sentence.

Where in the Chomsky hierarchy do such grammars lie? Also is it possible to automatically generate parsers for such grammars?

Answer 1

There is an international agreed notation for describing protocols and format specifications (well actually there are several), which is ASN.1. It is a form of Context_free grammar notation.

I used to teach formal notations for networking at one time, but these things have dropped out of the curriculum in favour of security ; which is interesting when a better understanding of the formalism might help enhance security.

It is possible to generate code for handling protocols; and some is done that way. Using state machines for the protocol and notations like ASN.1 for the packet descriptions much can be automated, and has been in the past.