Learning Highly Recursive Input Grammars
Learning Highly Recursive Input Grammars
复制标题
学习高度递归输入语法
DOI：
10.1109/ase51524.2021.9678879
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Koushik Sen
中科院分区：
文献类型：
--
作者：
Neil Kulkarni;Caroline Lemieux;Koushik Sen
本文介绍了 Arvada，一种从一组正例和布尔值预言中学习上下文无关语法的算法。 Arvada 通过从正例中构建解析树来学习上下文无关语法。从最初的扁平树开始，Arvada 通过一个关键操作为这些树构建结构：它将树中的兄弟节点序列冒泡到一个新节点中，从而向树添加一个间接层。冒泡操作可以在学习的语法中实现递归泛化。我们将 Arvada 与 GLADE 进行比较，发现它的召回率平均提高了 4.98 倍，F1 分数平均提高了 3.13 倍，而速度仅降低了 1.27 倍，并且只需要 0.87 倍的预言机调用次数。 Arvada 在具有高度递归结构的语法（如编程语言的语法）上比 GLADE 有特别显着的改进。
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.