一句话：提出 Arvada，通过冒泡兄弟节点从正例与布尔预言机中学习能泛化高度递归结构的上下文无关文法。
从正例和布尔预言机中学习上下文无关文法是程序语言输入建模与语法推断中的基础问题，但已有方法（如 GLADE）难以泛化出高度递归结构。本文提出 Arvada：从正例出发构建扁平的解析树，并通过反复将树中兄弟节点序列“冒泡”成新节点来引入间接层，从而在文法中递归地概括结构。该操作使学习到的文法能够捕捉编程语言等高度递归输入。作者在多个文法上与 GLADE 对比，平均召回率提升 4.98 倍、F1 提升 3.13 倍，且仅带来 1.27 倍减速，预言机调用次数为 GLADE 的 0.87 倍；在高度递归文法上优势尤其明显。
This paper presents Arvada, an algorithm for learning context-free grammars from a set of positive examples and a Boolean-valued oracle. Arvada learns a context-free grammar by building parse trees from the positive examples. Starting from initially flat trees, Arvada builds structure to these trees with a key operation: it bubbles sequences of sibling nodes in the trees into a new node, adding a layer of indirection to the tree. Bubbling operations enable recursive generalization in the learned grammar. We evaluate Arvada against GLADE and find it achieves on average increases of 4.98× in recall and 3.13× in F1 score, while incurring only a 1.27× slowdown and requiring only 0.87× as many calls to the oracle. Arvada has a particularly marked improvement over GLADE on grammars with highly recursive structure, like those of programming languages.
DOI 原文 ·
@inproceedings{paperbot6613,
title = {Learning Highly Recursive Input Grammars},
author = {Neil Kulkarni and Caroline Lemieux and Koushik Sen},
booktitle = {ASE},
year = {2021},
doi = {10.1109/ase51524.2021.9678879}
}