zhangIntervalParsingGrammars2023:
  type: article
  title: Interval {Parsing} {Grammars} for {File} {Format} {Parsing}
  author:
  - Zhang, Jialun
  - Morrisett, Greg
  - Tan, Gang
  date: 2023-06
  page-range: 1073-1095
  url:
    value: https://dl.acm.org/doi/10.1145/3591264
    date: 2024-04-29
  serial-number:
    doi: 10.1145/3591264
    issn: 2475-1421
  abstract: 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.
  parent:
    type: periodical
    title: Proceedings of the ACM on Programming Languages
    issue: PLDI
    volume: 7