13
$\begingroup$

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also context sensitive. This basically leads to having only one type of token, a token for byte.

Can someone explain why parsing binary data with a lexer/parser is so wrong with enough clarity for a CS student who hasn't taken a parsing class, but with a footing on theory?

$\endgroup$
  • $\begingroup$ My guess is that the lexer probably cannot find tokens that are smaller than a byte/word. If you need it, Erlang has excellent support for parsing binaries: user.it.uu.se/~pergu/papers/JFP_06.pdf $\endgroup$ – Dave Clarke Mar 30 '12 at 12:01
  • 3
    $\begingroup$ I don't think that your assumption is true. Obviously, non-context-free data poses problems (which can often be circumvente), but you can give grammars for binary words. You will probably not be able to use popular parser generators, as those assume text input. That is another issue, though. $\endgroup$ – Raphael Mar 30 '12 at 13:07
  • $\begingroup$ @GuyCoder: Many classic examples for grammars use binary alphabets, e.g. $S \to 0S \mid 10S$. $\endgroup$ – Raphael Mar 30 '12 at 13:13
  • 1
    $\begingroup$ By the way: "having only one type of token, a token for byte." -- well no, that would make $2^8$ byte tokens. $\endgroup$ – Raphael Mar 30 '12 at 20:27
  • 5
    $\begingroup$ @GuyCoder: All data that is generated by another program can be described by a grammar. It might not be a context-free one, though. $\endgroup$ – Raphael Mar 30 '12 at 20:32
10
$\begingroup$

In principle, there is nothing wrong.

In practice,

  • most non-textual data formats I know are not context-free and are therefore not suitable for common parser generators. The most common reason is that they have length fields giving the number of times a production has to be present.

    Obviously, having a non context-free language has never prevented the use of parser generators: we parse a superset of the language and then use semantic rules to reduce it to what we want. That approach could be used for non-textual formats if the result would be deterministic. The problem is to find something else than counts to synchronize on as most binary formats allow arbitrary data to be embedded; length fields tell you how much it is.

    You can then start playing tricks like having a manually writen lexer able to handle that with feedback from the parser (lex/yacc handling of C use that kind of tricks to handle typedef, for instance). But then we come to the second point.

  • most non-textual data formats are quite simple (even if they are not context-free). When the counts mentioned above are ignored, the languages are regular, LL1 at worst, and are thus well suited for manual parsing techniques. And handling counts is easy for manual parsing techniques like recursive descent.

$\endgroup$
  • $\begingroup$ "the languages are regular" If "but also context sensitive' was taken to mean the binary data is a grammar, I will clarify in the answer. That does get to part of the problem; people tend to think grammars or regular languages once you mention parser. $\endgroup$ – Guy Coder Mar 30 '12 at 17:53
7
$\begingroup$

Let's categorize data into three categories: data readable by humans (usually texts, varying from books to programs), data intended to be read by computers and other data (parsing images or sound).

For the first category, we need to process them into something a computer can use. As the languages used by humans can generally be captured relatively well by parsers, we usually use parsers for this.

An example of data in the third category would be a scanned image of a page out of a book which you want to parse into text. For this category, you almost always need very specific knowledge about your input, and therefore you need a specific program to parse it. Standard parsing technology won't get you very far here.

Your question is about the second category: if we have data that is in binary, it is almost always a product of a computer program, intended for another computer program. This immediately also means that the format the data is in is chosen by the program responsible for its creation.

Computer programs almost always produce data in a format that has a clear structure. If we parse some input, we are essentially trying to figure out the structure of the input. With binary data, this structure is generally very simple and easy to parse by computers.

In other words, it's normally a bit of a waste to figure out the structure of an input for which you already know the structure. As parsing isn't free (it takes time and adds complexity to your program), this is why using lexers/parsers on binary data is 'so wrong'.

$\endgroup$
  • 2
    $\begingroup$ This is a nice perspective, but I feel like it does not answer the question. $\endgroup$ – Raphael Apr 4 '12 at 17:33
  • $\begingroup$ LANGSEC: Language-theoretic Security offers an interesting perspective. One of the articles talks about "weird machines": ad hoc parsers of a known format forming the input handling facilities of a system. They may not actually work as intended. Due to incorrect assumptions, the defective machine will perform unanticipated state transitions given especially-crafted input, performing computation that shouldn't be possible. This creates an attack vector. Using formal grammars would yield provably correct algorithms. $\endgroup$ – Matheus Moreira Jun 6 '16 at 6:06
0
$\begingroup$

If a language needs to be parsed in some non-trivial way, it usually means that structural elements need to be matched, so the input language contains redundancy, either because multiple inputs map to the same parse tree or because some input strings are invalid. Humans like redundancy. For example, most humans find binary operators more readable than a pure prefix or suffix notation for elementary arithmetic: $a + b \times (c - d) + e$ rather than (+ a (* b (- c d)) e) or a b c d - * + e +. The usual mathematical notation has more redundancy than Lisp (which requires more parentheses, but gets variable arities for free, so requires fewer symbols to express expressions using large arities) or RPL (which never needs parentheses). Such redundancy is rarely useful to computers — and where it is, which is when there may be errors in the data, the error correction logic is usually kept separate from the functional meaning of the data, for example using error correcting codes which apply to arbitrary byte sequences regardless of what they represent.

Binary formats are usually designed to be compact, which means few simple language features such as balanced parentheses that are expressible by context-free grammars. Furthermore, it is often useful for binary representations of data to be canonical, i.e. to have a single representation of each object. This rules out sometimes-redundant features such as parentheses. Another, less commendable consequence of having less redundancy is that if every input is syntactically correct, it saves on the error checking.

Another factor against nontrivial parsers for binary data is that a lot of binary formats are designed to be parsed by low-level code that likes to operate in constant memory with little overhead. Fixed sizes are prefered when applicable to allowing arbitrary repetition of an element. A format such as TLV that allows a left-to-right parser to allocate the right amount of memory for an object first, then read the representation of the object. Parsing from left to right is an advantage because it allows the data to be processed as it comes, with no intermediate buffer.

$\endgroup$
  • $\begingroup$ What is the point of the first two paragraphs? Even if you have no redundancy you need a parser. Also, the first paragraph is wrong: there are examples where all words are allowed but you parse to obtain the structure (e.g. secondary structure prediction of RNA). $\endgroup$ – Raphael Apr 4 '12 at 17:38
  • $\begingroup$ @Raphael A non-trivial parser usually implies redundancy (yes, as you point out, there are exceptions). I hadn't considered languages that were designed neither for humans nor for computers, this is an interesting example. The first two paragraphs discuss typical differences between binary and human-readable formats (typical meaning that if you go looking for exceptions, you'll find them). $\endgroup$ – Gilles 'SO- stop being evil' Apr 4 '12 at 18:24

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.