Fast Deterministic Black-box Context-free Grammar Inference
Proceedings of the IEEE/ACM 46th International Conference on Software Engineering(2023)
摘要
Black-box context-free grammar inference is a hard problem as in many
practical settings it only has access to a limited number of example programs.
The state-of-the-art approach Arvada heuristically generalizes grammar rules
starting from flat parse trees and is non-deterministic to explore different
generalization sequences. We observe that many of Arvada's generalization steps
violate common language concept nesting rules. We thus propose to pre-structure
input programs along these nesting rules, apply learnt rules recursively, and
make black-box context-free grammar inference deterministic. The resulting
TreeVada yielded faster runtime and higher-quality grammars in an empirical
comparison. The TreeVada source code, scripts, evaluation parameters, and
training data are open-source and publicly available
(https://doi.org/10.6084/m9.figshare.23907738).
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要