File formats specify how data is encoded for persistent storage. They cannot be formalized as context-free grammars since their specifications include context-sensitive patterns such as the random access pattern and the type-length-value pattern. We propose a new grammar mechanism called Interval Parsing Grammars IPGs) for file format specifications. An IPG attaches to every nonterminal/terminal an interval, which specifies the range of input the nonterminal/terminal consumes. By connecting intervals and attributes, the context-sensitive patterns in file formats can be well handled. In this paper, we formalize IPGs' syntax as well as its semantics, and its semantics naturally leads to a parser generator that generates a recursive-descent parser from an IPG. In general, IPGs are declarative, modular, and enable termination checking. We have used IPGs to specify a number of file formats including ZIP, ELF, GIF, PE, and part of PDF; we have also evaluated the performance of the generated parsers.

翻译：文件格式指定了数据加密的方式以用于持久化存储。它们不能被形式化为上下文自由文法，因为它们的规范包括上下文相关模式，例如随机访问模式和类型长度值模式。我们提出了一种称为区间语法分析器（IPG）的新型语法机制来处理文件格式规范。IPG会为每个非终端符/终端符附加一个区间，其中详细说明了该非终端符/终端符消耗的输入范围。通过连接区间和属性，可以很好地处理文件格式中的上下文相关模式。在本文中，我们将IPG的语法及语义形式正式化，其语义自然导致一个解析器生成器，它能够从IPG生成一个递归下降解析器。总体而言，IPG是声明式、模块化的并且能够实现终止检查。我们已经使用IPG指定了许多文件格式，包括ZIP、ELF、GIF、PE和部分PDF；我们还评估了生成的解析器的性能。