BFF: A grammar for Binary File Formats

With a growing number of binary formats that are being used, there is a need for specifying these formats in a well-defined way. Context free grammars have been used to specify the syntax of programming langauges. To use a grammar for binary file formats seems to be a logical choice.

In this page such a grammar, named BFF, is described. It has several construct that are not traditionally found in context free grammars for programming language. Due to the nature of binary file formats, it is important to be able to reference information that has been read before. For example, a string of characters might be preceded by a number that indicates the lengt of the string.

The terminal symbols of the grammar consist of a number of bytes, representing one of the basic data types, such as: char, short int, long int, float and double. Differences in byte ordering for integers, and the different formats for floating point numbers should be taken into account.

Due to the nature of binary formats, it is not too restrictive to use only recursive descent grammars, e.i., grammars that can be parsed top-down, and belong to the LL(1) class.

The BFF is tested for the DWG file format. As we start with this file format, BFF will naturally first focus on the requirements based on this format, and because of this it will be slightly biased.

To specify the grammar of BFF we will use a form of extended BNF.

Tool support for BFF

The first tool I am thinking about is a program that can read the grammar and apply this to a given binary file, resulting in an annotated output.

This tool should also support the reverse engineering of binary file formats.

In a later state, a tool could be made that generates a parser and the needed data structures for reading a binary file into memory according to the grammar. As it is not always required (nor possible) to read the whole file into memory, it should be possible to generate procedures to read the file interactively.

I never found the time (nor the need) for developing this tool. For a good professional alternative have a look at 010 Editor - Hex Editor, which makes use of a template language which has similar features as proposed here. Another professional alternative have a look at Hexinator, which has a build in grammar editor and a broad collection of grammars stored in an XML format.

The form of the BFF grammar

A grammar that describes a Binary File Format consists of the specification of the elementary units of data, and the rules by which these should be grouped together.

The elementary units

We assume that a Binary File can be viewed as a stream of bytes (as this is the most commonly used unit of data). Usually a number of bytes are grouped together to form data values that cannot be represented by a single byte. To specify a word value consisting of two bytes, for example, we propose the following defintion style:

type  word :=
    byte : first,
    byte : second
    return ((word)first | ((word)second << 8)).

A word representation where the lower order byte comes before the higher order is usually used by small Endian processors. The expression used on will be based on C. We assume that the following types have been defined on top of the default types of C:

typedef unsigned char       byte;
typedef unsigned short int  word;
typedef unsigned long int   longword;

This leeds us to the definition of the basic types that will be supported:

C_data_types :=
    "char"  | "byte" |
    "short" | "word" |
    "long"  | "longword" |
    "float" | "double" .

(We assume for the moment that float and double represent floating numbers of 4, respectively 10 bytes.) The grammar of the rule used for defining types is:

type_def_rule :=
     "typedef" C_data_type basic_type_name ":="
     ("byte" ":" byte_name) LIST
     "return" expr "." .

Here expr stands for C-like expression using the byte_names as they are used in the rule. The basic_type_names should not be confused with the C_type_names. It is possible that the same name is both used as a basic_type_name and a C_type_name.

The rules

The grammar that specifies in which order elementary units are taken from a binary file, makes use of non-terminal symbols and rules for each non-terminal symbol. There will be one non-terminal symbol that will parse the whole binary file, which will be called the root non-terminal symbol. For each non-terminal symbol there has to be a rule describing the elements it consists of, where each element is either an elementary elements or a non-terminal symbols. The rule of the root non-terminal symbol comes as the first rule, and is preceded with the word `root'. The whole BFF grammar follows the following grammar:

BFF_grammar :=
     type_def_rule SEQ
     "root" rule
     rule SEQ.

Each rule has a non-terminal symbol on the left-hand side, and a list of elements on the right-hand side. Each element is either a elementary element, a non-terminal symbol, or a grouping of elements. Because BFF assumes a top-down parsing method, it is possible to give each non-terminal symbol a number of parameters. This leads to the following grammar for the rules:

rule :=
      non_term_name  ( "(" param LIST ")" )OPT
      ":=" elem LIST ".".

Each element consist of the following parts:

An (optional) range, which specifies the range of the file that element may read.
A data type, which can either be a elementary unit, a non-terminal symbol, or a list of elements enclosed by brackets.
An (optional) times expression, to indicate that the element can be repeated, either for a given number of times or for an unknown number of times.
An (optional) identifying name, which can be used later to reference the value found.
An (optional) equivalence expression, which can be used for checking.

The following grammar describes an element:

elem := range OPT
        data_type
        ( "[" expr "]"
        | "*" )
        ( ":" elem_name )OPT
        ( "=" C_expr )OPT.

range := "[" file_pos (":" file_pos)OPT "]".

file_pos := "begin" | "end" | "cur" | expr.

data_type := "(" elem LIST ")"
           | basic_type_name
           | non_term_name  ( "(" expr LIST ")" )OPT.

home and email | How to crack a Binary File Format | DWG12 format description