Leg*_*end 3 language-agnostic compiler-construction algorithm parsing abstract-syntax-tree
我一直在阅读这篇题为" 使用抽象语法树进行克隆检测"的文章,由Ira D. Baxter等人撰写.我在下面转载的论文中有一段:
原则上,查找子树克隆很容易:将每个子树与每个其他子树进行比较以获得相等性.在实践中,出现了几个问题:接近错过克隆检测,亚克隆和规模....
当找到接近未命中的克隆时,完整子树上的散列会精确失败,因为良好的散列函数包括树的所有元素,因此将轻微的差异排序到不同的桶中.我们通过选择人为错误的哈希函数来解决这个问题 .必须以这样的方式表征该函数,即保留想要在近未命中克隆上找到的主要属性.接近未命中克隆通常通过复制和粘贴程序创建,然后进行少量修改.这些修改通常会对与复制的代码段相关联的树的形状进行小的更改.因此,我们认为这种近乎未命中的克隆通常只有一些不同的小子树.基于这种观察,忽略小子树的散列函数是一个很好的选择.在这里给出的实验中,我们使用了一个哈希函数,它只忽略标识符名称(树中的叶子).因此,我们的散列函数将具有相似模数标识符的树放入相同的散列区中以进行比较.
我正在尝试实现本文中讨论的技术,但我仍然试图理解这一段(不幸的是在论文的开头).我理解段落的内容,但作者没有提到要选择的哈希函数或如何实际哈希AST.有人可以从实施的角度用一个简单的例子解释一下吗？
作者自己应该回答的阴影.StackOverflow不是很棒: - ？
哈希函数的关键在于您选择哪一个无关紧要,只要它在大量存储桶中均匀分配输入值即可.您需要一个可以应用于整个树的哈希函数; 通常的技术是以任何可能的方式序列化树(例如,通过有序树访问),然后将哈希函数应用于它产生的值流(树节点).(这个想法来自关于检测常见子表达式的编译器文献,这是原始CloneDR的灵感).如果不清楚,您需要花费更多的精力来理解哈希函数如何应用于复杂的数据结构.关于哈希的维基百科是一个很好的起点; 如果这还不够,你需要找一本关于算法和研究的书.
您向哈希函数提供的内容取决于您.我在论文中提出的观点是,您可以计算忽略AST的标识符叶的散列函数,这将导致具有相同结构但不同标识符的树散列到同一个桶.因此,类似模数标识符的树很容易匹配,因为它们出现在相同的散列桶中.
当然,只有匹配树模数标识符的整个克隆检测算法还有很多.您需要担心匹配参数化序列(这是本文中的重点),报告结果,当然,您需要一个高质量的语言解析器,用于您应用的任何语言.
您可以看到许多不同语言的CloneDR结果.