一句话：提出 V-Star，用可见下推自动机主动学习，从样本输入推断程序输入文法的嵌套结构，并学习 S-表达式、JSON、XML。
准确描述程序输入语言是程序语言领域的重要挑战。现有主动学习可精确学习正则语言，但难以直接处理嵌套结构。本文提出 V-Star，基于可见下推自动机（VPA）的主动学习进行文法推断。其核心是一种基于嵌套模式的新推断机制，能从样本输入中识别 token 边界并推导嵌套结构，将 XML 等语言转换为 visibly pushdown languages（VPL）。作者进一步将 Angluin 的 L-Star 精确学习算法适配到 VPA 学习，以提高推断精度。评估表明，V-Star 能有效且高效地学习 S-表达式、JSON、XML 等多种实用文法，并优于其他先进工具。
Accurate description of program inputs remains a critical challenge in the field of programming languages. Active learning, as a well-established field, achieves exact learning for regular languages. We offer an innovative grammar inference tool, V-Star, based on the active learning of visibly pushdown automata. V-Star deduces nesting structures of program input languages from sample inputs, employing a novel inference mechanism based on nested patterns. This mechanism identifies token boundaries and converts languages such as XML documents into VPLs. We then adapted Angluin’s L-Star, an exact learning algorithm, for VPA learning, which improves the precision of our tool. Our evaluation demonstrates that V-Star effectively and efficiently learns a variety of practical grammars, including S-Expressions, JSON, and XML, and outperforms other state-of-the-art tools.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{JiaT24,
title = {V-Star: Learning Visibly Pushdown Grammars from Program Inputs},
author = {Xiaodong Jia and Gang Tan},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656458}
}