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?


1 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.

  • 2
    $\begingroup$ The description of networking protocols is typically given by RFCs, and RFCs are written in a way such that you can automatically extract the relevant ASN.1 grammars and generate parsers for them. $\endgroup$ Jun 12, 2015 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.