Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the
.torrent file format used by Bittorrent applications. It’s a simple encoding scheme, so I am wondering if a context-free grammar could be constructed for it. There are a couple of reasons I think it cannot:
The location of terminals depends on the ‘interpreted’ value of certain length-prefixed values.
Terminals can be present inside of non-terminal sequences, but in principal (i.e., in well-formed Bencodes) are not ever encountered by a parser except for verification maybe. In fact, entire Bencodes (in theory) could be present as values of, let’s say, a list element of a Bencode, but in such a way that they’re meant to be interpreted as “data” and not as something to be parsed or transformed by a rule. It’s ever-so-slightly more subtle than normal recursion as far as I can tell…
Update: When thinking about this I realized something odd whereby one could convert a context-dependent grammar into a context-free grammar; i.e., consider the problem of length-prefixed values such as appear in Bencode. For convenience I will use Bencode’s syntax; so let’s consider the string
5:hello. If you have a trivial function that converts the ASCII “5” into a unary value and all the other ASCII characters into a character then you have an equivalent structure.
olleh:hello; I like the idea of reversing the string because then you could easily construct another function to map the string back onto the ASCII numeral (after appropriate checks have been made that the string is in fact the length reported as to not skew semantics; I am not considering non-conforming strings, since we are talking about grammar...).
This is of course a very simple case of dependent grammar, but I wonder 1.) if anybody else has noticed this (I am sure), and 2.) if this could resolve some other context-dependent situations.