一句话：提出区间解析文法 IPG，为每个文法符号附加输入区间与属性，从而声明式地刻画文件格式中的上下文相关模式并自动生成解析器。
文件格式规定了数据的持久化编码方式，其规范包含随机访问、类型-长度-值等上下文相关模式，无法用上下文无关文法直接形式化。本文提出一种新的文法机制——区间解析文法（IPG）：它为每个非终结符/终结符附加一个区间，用以刻画该符号所消费的输入范围；通过区间与属性的连接，文件格式中的上下文相关模式得以自然处理。作者形式化了 IPG 的语法与语义，其语义直接导出一个可从 IPG 生成递归下降解析器的解析器生成器，并具备声明式、模块化与可终止性检查等特性。作者用 IPG 描述了 ZIP、ELF、GIF、PE 以及部分 PDF 等多种文件格式，并对生成解析器的性能进行了评估。
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.
@article{paperbot1955,
title = {Interval Parsing Grammars for File Format Parsing},
author = {Jialun Zhang and Greg Morrisett and Gang Tan},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {PLDI},
year = {2023},
doi = {10.1145/3591264}
}