一句话：提出用精化类型推断从无标注 ad hoc 解析器源码中静态推断正则输入文法，并实现 Panini 系统。
实践中大量解析器是 ad hoc 编写的：直接用字符串操作处理输入而不显式定义文法，且常与业务逻辑交织，易产生隐蔽语义错误；完整文法虽有助于理解、测试与调试，但手工编写（如正则表达式）繁琐易错。本文受类型推断启发，提出从无标注 ad hoc 解析器源码静态推断正则输入文法的通用方法：用精化类型推断合成刻画正则解析操作的逻辑与字符串约束，再通过抽象语义解释为正则表达式。作者给出核心演算、将文法推断表述为精化推断、求解字符串精化变量的抽象解释框架及多个抽象域，并实现 Panini。在 204 个 Python ad hoc 解析器上的评估显示，Panini 以 100% 精度、93% 平均召回率、约 0.82±2.85 秒耗时优于现有方法，且无需输入空间先验知识。
Parsing—the process of structuring a linear representation according to a given grammar—is a fundamental activity in software engineering. While formal language theory has provided theoretical foundations for parsing, the most common kind of parsers used in practice are written ad hoc. They use common string operations without explicitly defining an input grammar. These ad hoc parsers are often intertwined with application logic and can result in subtle semantic bugs. Grammars, which are complete formal descriptions of input languages, can enhance program comprehension, facilitate testing and debugging, and provide formal guarantees for parsing code. But writing grammars—e.g., in the form of regular expressions—can be tedious and error-prone. Inspired by the success of type inference in programming languages, we propose a general approach for static inference of regular input string grammars from unannotated ad hoc parser source code. We use refinement type inference to synthesize logical and string constraints that represent regular parsing operations, which we then interpret with an abstract semantics into regular expressions. Our contributions include a core calculus ?? Σ for representing ad hoc parsers, a formulation of (regular) grammar inference as refinement inference, an abstract interpretation framework for solving string refinement variables, and a set of abstract domains for efficiently representing the constraints encountered during regular ad hoc parsing. We implement our approach in the Panini system and evaluate its efficacy on a benchmark of 204 Python ad hoc parsers. Compared with state-of-the-art approaches, Panini produces better grammars (100 % precision, 93 % average recall) in less time (0.82 ± 2.85 s) without prior knowledge of the input space.
@article{paperbot2943,
title = {Static Inference of Regular Grammars for Ad Hoc Parsers},
author = {Michael Schröder and Jürgen Cito},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA2},
year = {2025},
doi = {10.1145/3763054}
}