Bencoding is the encoding scheme used by Bittorrent applications. Youre probably most familiar with bencoding via the .torrent file format used by Bittorrent applications. Its 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 interpretedvalue 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, lets say, a list element of a Bencode, but in such a way that theyre meant to be interpreted as dataand not as something to be parsed or transformed by a rule. Its ever-so-slightly more subtle than normal recursion as far as I can tellUpdate: 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 Bencodes syntax; so lets 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.Viz. 5:hello becomes 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.
Can Bencodes Be Described With a Context-Free Grammar?
fl.formal languages;context free;encoding