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] bitssize    | dataI 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?
What would a formal grammar for a binary file format look like?
formal languages;formal grammars;parsers;context sensitive;information retrieval