1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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$
    – Martin Berger
    Jun 12, 2015 at 8:51

Your Answer

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

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