6
$\begingroup$

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive.

What would a context-sensitve grammar for a simple binary format look like?

For example, let's consider a length-prefixed array with the following layout:

64 bits | [size * 8] bits
size    | data

I suppose the language that corresponds to this format would be:

$$n b^n \\ n \in [0, 2^{64}[ \\ b \in [0, 2^8[$$

Left-context-sensitive grammars have the following structure:

$$\alpha A \rightarrow \alpha \gamma$$

I don't understand how this formalism could generate or be used to parse a language which contains part of the grammar itself in it. Does the following grammar make any sense?

\begin{align} Bit & \rightarrow 0 \\ Bit & \rightarrow 1 \\ Octet & \rightarrow Bit^8 \\ Size & \rightarrow Octet^8 \\ Size \; Data & \rightarrow Size \; Octet^{Size} \\ Array_s & \rightarrow Size \; Data \\ \end{align}

I reason that the grammar above matches the structure of left-context-sensitive grammars. It seems clear to me that the next-to-last line of the grammar directly corresponds to the definition above:

\begin{align} \alpha & = Size \\ A & = Data \\ \gamma & = Octet^{Size} \\ \end{align}

The trickiest non-terminal seems to be $Size$. It is not clear to me exactly how it influences the grammar's semantics. It is simultaneously part of the input and the grammar, serving as the number of repetitions for $Octet$.

I have seen many grammar-based approaches to parsing binary file formats. They include formalisms such as attribute grammars,[1][2] adaptive grammars, the recently introduced data-dependent grammars,[1][2] parser combinators [1][2][3][4][5] and even scattered context grammars.[1]

All these tools go beyond the definition above, so I keep wondering about the nature of binary file formats. If it is not possible to describe their language with a context-sensitive grammar, does that mean they are more powerful in the Chomsky hierarchy?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ In practice, you probably wouldn't want to use the formalism of context-sensitive grammars to specify such situations -- that'll probably be too clumsy/awkward, and ill-suited for this task. Instead, it'll probably be more effective to define a custom language that makes it easy to express the idioms that typically arise in binary file formats (e.g., length fields, checksums). For instance, fuzzers (such as Sulley) have developed ways to express these kinds of file formats. Not sure whether you're asking about practical solutions or the theoretical properties. $\endgroup$ – D.W.♦ Jul 18 '16 at 21:57
  • $\begingroup$ You might want to look through some IETF standards. For example, section 11.3 of RFC4880 gives the message syntax of OpenPGP. tools.ietf.org/html/rfc4880 $\endgroup$ – Pseudonym Jul 19 '16 at 8:51
  • $\begingroup$ @D.W. I'm asking about theory. Many descriptions of binary file formats state that their syntax is context-sensitive but I've never actually seen an actual formal context-sensitive grammar for any format. I edited my question and added citations of some specialized models I had researched prior to asking. $\endgroup$ – Matheus Moreira Jul 19 '16 at 11:19
  • $\begingroup$ I think you want to simulate a TM (or LBA, rather) parsing the language, i.e. count down length fields while consuming further symbols. $\endgroup$ – Raphael♦ Jul 19 '16 at 11:49
  • $\begingroup$ @Raphael would that work with the example language and grammar I used in my question? Please explain in more detail. $\endgroup$ – Matheus Moreira Jul 21 '16 at 18:01
3
$\begingroup$

  1. The Chomsky hierarchy is a hierarchy of grammars described by a given formalism. The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they are outside the Chomsky hierarchy (and if I'm not mistaken are able to recognize some languages of higher level in the hierarchy while being unable to recognize other languages at a lower level).

  2. Context-sensitive grammars are not at the top of the Chomsky hierarchy, unrestricted grammars are.

  3. Context-sensitive grammars can generate what you are asking for, but it's painful to write. Here is a grammar which generate a s followed by a binary number, followed by as many p as determined by the binary number.

\begin{align} S & \rightarrow \text{s} \; C \\ \text{s} \; C & \rightarrow A \\ \text{s} \; C & \rightarrow \text{s} \; B \; \text{p} \\ \text{s} \; C & \rightarrow \text{s} \; B \; C \; \text{p} \\ A \; C & \rightarrow A \; D \\ A \; D & \rightarrow B \; D \\ B \; D & \rightarrow B \; \text{p} \\ B \; D & \rightarrow B \; C \; \text{p} \\ B \; C & \rightarrow B \; E \\ B \; E & \rightarrow X \; E \\ X \; E & \rightarrow X \; \text{p} \\ X \; E & \rightarrow X \; C \; \text{p} \\ A \; X & \rightarrow A \; F \\ A \; F & \rightarrow B \; F \\ B \; F & \rightarrow B \; A \\ B \; X & \rightarrow B \; G \\ B \; G & \rightarrow X \; G \\ X \; G & \rightarrow X \; A \\ \text{s} \; X & \rightarrow \text{s} \; B \; A \\ A & \rightarrow 0 \\ B & \rightarrow 1 \\ \end{align}

Yes that's a lot of rules (I may have missed some shortcuts, but on the other hand I may have missed some cases where unwanted strings are generated which could be avoided only with a more complex grammar). Some explanations:

  • I'm using $A$ and $B$ for temporary place holder for $0$ and $1$ because context sensitive rules do not allow to modify terminals. The last two rules replace them by the terminals they were acting for.

  • the first three rules are pretty obvious.

  • the fourth is starting the count

  • the next four are transforming a count ending by a $0$ in a count ending by a $1$ and a $\text{p}$

  • the next four are transforming a count ending by a $1$ in a count ending by a $X$ (meaning a carry to be propagated) and a $\text{p}$

  • the last seven rules are doing the carry propagation.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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