V-Star: Learning Visibly Pushdown Grammars from Program Inputs
<|reference_start|>V-Star: Learning Visibly Pushdown Grammars from Program Inputs: 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.<|reference_end|>
@article{jia2024v-star:,
    title={V-Star: Learning Visibly Pushdown Grammars from Program Inputs},
    author={Xiaodong Jia and Gang Tan},
    journal={arXiv preprint arXiv:2404.04201},
    year={2024},
    doi={10.1145/3656458},
    archivePrefix={arXiv},
    eprint={2404.04201},
    primaryClass={cs.PL cs.FL}
}