一句话：提出 Crucio，通过分解森林与分布矩阵从黑盒样本中为 C/C++/Java 等复杂语言高效推断上下文无关文法。
现有文法推断方法难以在实用时间内扩展到复杂编程语言：Arvada、Treevada、Kedavra 均无法在 48 小时内推断 C、C++、Java 文法。Arvada/Treevada 直接在完整长输入上推断，对大文件效率低；Kedavra 虽做数据分解生成短示例，但词法分析仍依赖原始输入，且严格不过度泛化约束限制复杂文法构造。本文提出 Crucio，构建分解森林提取短示例，并通过分布矩阵同时进行词法与文法推断。实验显示，Crucio 是唯一能在合理时间内成功推断复杂语言文法的方法，非终结符数量最高为此前基准的 23 倍；在简单基准上，其平均召回率为 Treevada/Kedavra 的 1.37/1.19 倍，F1 为 1.21/1.13 倍。
Grammar inference for complex programming languages remains a significant challenge, as existing approaches fail to scale to real-world datasets within practical time constraints. In our experiments, none of the state-of-the-art tools, including Arvada, Treevada and Kedavra were able to infer grammars for complex languages such as C, C++, and Java within 48 hours. Arvada and Treevada perform grammar inference directly on full-length input examples, which proves inefficient for large files commonly found in such languages. While Kedavra introduces data decomposition to create shorter examples for grammar inference, its lexical analysis still relies on the original inputs. Additionally, its strict no-overgeneralization constraint limits the construction of complex grammars. To overcome these limitations, we propose Crucio, which builds a decomposition forest to extract short examples for lexical and grammar inference via a distributional matrix. Experimental results show that Crucio is the only method capable of successfully inferring grammars for complex programming languages (where the number of nonterminals is up to 23 × greater than in prior benchmarks) within reasonable time limits. On the prior simple benchmark, Crucio achieves an average recall improvement of 1.37 × and 1.19 × over Treevada and Kedavra, respectively, and improves F1 scores by 1.21 × and 1.13 ×.
@inproceedings{abs-2601-12385,
title = {Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings},
author = {Feifei Li and Xiao Chen and Xiaoyu Sun and Xi Xiao and Shaohua Wang and Yong Ding and Sheng Wen and Qing Li},
booktitle = {ICSE},
year = {2026},
doi = {10.1145/3744916.3773147}
}