一句话：提出 DSL Saggitarius 描述上下文无关文法族，并用半环解析与 MaxSAT 从示例数据推断最匹配文法。
日期、地址、电话号码和表格等常见数据类型往往有多种文本表示，SQL 等广泛使用的语言也存在多个方言，这些差异可能导致数据被误读，进而引发静默数据损坏、数据处理失败甚至安全漏洞。Saggitarius 是一个新语言与系统，旨在帮助程序员推理数据格式：它用“语法域”描述一个数据类型的多种可能表示，即一组上下文无关文法。论文通过示例介绍 Saggitarius 的设计并给出关系语义；在数据分析场景中，给定示例数据，系统采用基于半环解析与 MaxSAT 的算法推断给定语法域中最匹配该数据的文法。作者在 110 个示例问题的基准套件上评估算法，表明系统通常仅需少量示例即可在几秒内返回满意文法；论文还深入研究了用 Saggitarius 进行 CSV 方言检测，发现尽管该语言是通用的，其效果可与手工调优的专用工具相比：在 CSV 场景下 60 秒内为 84% 的基准推断出文法，准确率与定制方言检测工具相当。
Common data types like dates, addresses, phone numbers and tables can have multiple textual representations, and many heavily-used languages, such as SQL, come in several dialects. These variations can cause data to be misinterpreted, leading to silent data corruption, failure of data processing systems, or even security vulnerabilities. Saggitarius is a new language and system designed to help programmers reason about the format of data, by describing grammatical domains---that is, sets of context-free grammars that describe the many possible representations of a datatype. We describe the design of Saggitarius via example and provide a relational semantics. We show how Saggitarius may be used to analyze a data set: given example data, it uses an algorithm based on semi-ring parsing and MaxSAT to infer which grammar in a given domain best matches that data. We evaluate the effectiveness of the algorithm on a benchmark suite of 110 example problems, and we demonstrate that our system typically returns a satisfying grammar within a few seconds with only a small number of examples. We also delve deeper into a more extensive case study on using Saggitarius for CSV dialect detection. Despite being general-purpose, we find that Saggitarius offers comparable results to hand-tuned, specialized tools; in the case of CSV, it infers grammars for 84% of benchmarks within 60 seconds, and has comparable accuracy to custom-built dialect detection tools.
@article{paperbot1862,
title = {Saggitarius: A DSL for Specifying Grammatical Domains},
author = {Anders Miltner and Devon Loehr and Arnold Mong and Kathleen Fisher and David Walker},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622869}
}