一句话：提出 Kedavra，通过分段示例字符串并增量推断，提升黑盒上下文无关文法推断的质量、速度与可读性。
黑盒上下文无关文法推断在只能访问少量示例程序的场景中十分困难。现有 Arvada 与 Treevada 从扁平解析树出发，用启发式搜索泛化序列，但需处理完整示例字符串，导致复杂、缓慢且生成的文法质量与可读性不佳。本文提出 Kedavra：先将示例字符串切分为较小单元，再增量地推断文法规则，以降低处理复杂度并逐步泛化。实证比较表明，该方法在文法质量（精确率与召回率）、运行速度和文法可读性上均优于现有方法。
Black-box context-free grammar inference presents a significant challenge in many practical settings due to limited access to example programs. The state-of-the-art methods, Arvada and Treevada, employ heuristic approaches to generalize grammar rules, initiating from flat parse trees and exploring diverse generalization sequences. We have observed that these approaches suffer from low quality and readability, primarily because they process entire example strings, adding to the complexity and substantially slowing down computations. To overcome these limitations, we propose a novel method that segments example strings into smaller units and incrementally infers the grammar. Our approach, named Kedavra, has demonstrated superior grammar quality (enhanced precision and recall), faster runtime, and improved readability through empirical comparison.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{Li0X0C0H24,
title = {Incremental Context-free Grammar Inference in Black Box Settings},
author = {Feifei Li and Xiao Chen and Xi Xiao and Xiaoyu Sun and Chuan Chen and Shaohua Wang and Jitao Han},
booktitle = {ASE},
year = {2024},
doi = {10.1145/3691620.3695494}
}