Available online at www.sciencedirect.com

ScienceDirect

IERI Procedia 10 (2014) 119 – 130

2014 International Conference on Future Information Engineering

Scripting Language for Java Source Code Recognition

Tomaacute;scaron; Bubliacute;k*, Miroslav Virius

Faculty of Nuclear Sciences and Physical Engineering Czech Technical University in Prague, Trojanova 13, Prague, 120 00, Czech Republic

Abstract

This paper presents general results on the Java source code snippet detection problem. We propose the tool which uses graph and subgraph isomorphism detection. A number of solutions for all of these tasks have been proposed in the literature. However, although that all these solutions are really fast, they compare just the constant static trees. Our solution offers to enter an input sample dynamically with the Scripthon language while preserving an acceptable speed. We used several optimizations to achieve very low number of comparisons during the matching algorithm.

copy; 2014 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/3.0/).

Selection and peer review under responsibility of Information Engineering Research Institute

copy; 2014. Published by Elsevier B.V.

Selection and peer review under responsibility of Information Engineering Research Institute

Keywords: AST; Java; tree matching; Scriphon; source code recognition

Introduction

It is usual that programs, consisting of a large source code, are becoming chaotic, and many times described illnesses start to appear (code duplicity, weak reusability, etc.). Maintaining a source code is a serious issue. There are a lot of tools and guides on how to approach this issue. The tool, described in this work, serves to programmable Java source code scanning. This tool is based on the Scripthon language which

was developed for these purposes in the scope of this work. A script, hich describes a source code structure

and its properties, can be written in this language. This allows defining dynamic properties of searching

* Corresponding author. Tel.: 420605155484.

E-mail address: tomas.bublik@gmail.com.

2212-6678 copy; 2014 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/3.0/).

Selection and peer review under responsibility of Information Engineering Research Institute doi:10.1016/j.ieri.2014.09.100

requirements. Next, an abstract syntax tree (hereinafter AST) is created dynamically from this script. Meanwhile, a similar tree is created from given Java source, and these two trees are matched by a graph matching algorithm. However, not only graph shapes are compared, also trees properties are considered. To obtain results faster, several graph optimizations are used during this process. And it is possible to scan higher amount of source code classes during a relatively short time. Typical usage of this approach is as follows: A user wants to find something, not easily describable, in a large program. But he or she knows that it could be there. He or she can use our tool and try to find at least the similar snippet of indented code. Therefore, a user performs a searching procedure, and specifies the input script based on the received results. By repeating this procedure, he or she filters the unintended results, and finally gets the desired code snippet. Our tool is useful not just for the fast Java sources scanning, but for example, for a better definability of search conditions. Another usage area of our tool can be a clonersquo;s detection problem. By using other clones detection tools, a material for further research can be gathered. For example, the non-ideal clones are difficult to detect and the output of such programs isnrsquo;t unequivocal in many cases. However, it can be classified by Sripthon, and a common searching script based on such output can be.

Theory

A graph is an ordered pair ，G=(V,E)where V is a finite,non-empty set of objects called vertices,and E is a (possibly empty) set of unordered pairs of distinct vertices i.e.,2-subsets of V called edges.The set V is called the vertex set of G,and E is called the edge set of G.If e={u,v}E(G),we say that vertices u and v are adjacent in G,and that e joins u and v.Wersquo;ll also say that u and v are the ends of e.The edge e is said to be incident with u(and v),and vice versa.We write uv(or vu) to denote the edge{u,v},on the understanding that no order is implied. Two graphs are equal if they have the same vertex set and the same edge set. But there are other ways in which two graphs could be regarded the same. For example, one could regard two graph as being “the same” if it is possible to rename the vertices of one and obtain the other. Such graphs are identical in every respect except for the names of the vertices. In this case, we call the graphs isomorphic.Formally, graphs G and H are isomorphic if there is a 1-1 correspondence f:V(G)-gt;V(H) such that xyE(G)lt;-gt;f(x)f(y)(H).This function f is called an isomorphismG=(V,E).

A tree is a connected graph that has no cycles (i.e., a connected acyclic graph).

The graph matching problem is actually the same as the problem of finding the isomorphism between the graphs. Moreover, matching the parts of a graph with a pattern is the same challenge as the finding the isomorphic subgraph. There are many approaches to this topic in Irniger et al., 2005.

Subgraph isomorphism is useful to find out if a given object is part of another object

剩余内容已隐藏，支付完成后下载完整资料

---

Java源代码识别的脚本语言

Tomaacute;scaron;bublik *, Miroslav Virius

布拉格捷克技术大学核科学与物理工程学院，特洛伊13，捷克共和国布拉格，12000

摘要:本文介绍了Java源代码片段检测问题的一般结果。我们提出了使用图和子图同构检测的工具。在文献中已经提出了许多用于所有这些任务的解决方案。然而，尽管所有这些解决方案都非常快，但它们只是比较常量静态树。我们的解决方案提供了使用Scripthon语言动态输入输入样本，同时保持可接受的速度。我们使用了几种优化来在匹配算法期间实现非常低的比较次数。

关键词：AST;Java;树匹配;Scriphon;源代码识别

1. 介绍

通常情况下由大量源代码组成的程序变得混乱，并且许多描述的问题开始出现

(代码重复、可重用性弱等)。维护源代码是一个困难的问题。关于如何解决这个问题，有很多工具和指南。这项工作中描述的工具用于可编程的Java源代码扫描。该工具基于脚本语言在本工作范围内为实现这些目的而开发的。描述源代码结构的脚本和属性都可以用这种语言编写。这允许定义搜索的动态属性需求。接下来，从这个脚本中动态创建一个抽象语法树(以下简称AST)。同时，从给定的Java源创建一个相似的树，这两个树通过一个图匹配算法进行匹配。但是，不仅要比较图形形状，还要考虑树的属性。为了更快地获得结果，在这个过程中使用了几个图形优化,并且可以在相对短的时间内扫描更大量的源代码类。这种方法的典型用法如下:用户想要在大型程序中找到一些不容易描述的东西。但用户知道它可能在那里，用户可以使用我们的工具，尝试找到至少相似的缩进代码片段。因此，用户执行搜索过程，并基于接收的结果指定输入脚本。通过重复这一过程，用户过滤掉不需要的结果，并最终获得所需的代码片段。我们的工具不仅对快速的Java源代码扫描有用，而且对搜索条件的更好定义也很有用。我们工具的另一个使用领域可能是克隆的检测问题。通过使用其他克隆检测工具，可以收集用于进一步研究的材料。例如，非理想克隆很难检测，而且在许多情况下，这类程序的输出也不明确。但是，它可以由Sripthon分类，基于这种输出的通用搜索脚本也可以。

1. 理论

图是有序对，G=(V,E)其中V是称为顶点的有限的、非空的对象集，而E是不同顶点的无序对(可能是空的)集，即称为边的2个V子集。集合V被称为顶点集合G，而E被称为边集合G。如果e={u，v}E(G)，我们说顶点u和v在G中是相邻的，E连接u和v。我们还会说u和v是E的端点。边e被称为与u(和v)入射，反之亦然。我们写uv(或vu)来表示边{u，v}，但前提是不隐含任何顺序。如果两个图具有相同的顶点集和相同的边集，那么它们是相等的。但是也有其他方法可以将两幅图视为相同的。例如，如果可以重命名一个图的顶点并获得另一个，那么可以认为两个图是“相同的”。除了顶点的名称之外，这些图在各个方面都是相同的。在这种情况下，我们称这些图同构。形式上，如果有1-1对应关系f:V(G)V(H)，那么图G和H是同构的，这样xyE(G)f(x)f(y)(H)。这个函数被称为同构。树是一个没有循环的连通图(即，一个连接的非循环图)。

图匹配问题实际上与寻找图之间同构的问题相同。此外，将图的各部分与模式进行匹配与寻找同构子图是同样的挑战。在Irniger等人，2005年，有许多关于这一主题的方法。

子图同构有助于发现给定对象是另一个对象的一部分，还是几个对象的集合的一部分。两个图g₁和g₂的最大公共子图是同构于g₁和g₂的子图的最大图。最大公共子图有助于测量两个对象的相似性。图同构、子图同构和最大公共子图检测的算法已经在McKay，1981中报道..

衡量两个图形相似性的一种更通用的方法是图形编辑距离。这是字符串编辑距离的推广，也称为列文斯坦距离斯蒂芬1994。

另一种测量两个图相似性的方法是基于g₁和g₂之间最大公共子图的距离测量，随着最大公共子图检测领域工作的增加，这些测量越来越流行。1998年在Bunke等人之中，引入了基于两个图的最大公共子图的图距离度量。

结果表明，最大公共子图距离这一众所周知的概念是特定编辑成本下图编辑距离的特例。因此，最初为最大公共子于编辑距离计算成本，反之亦然。此外，2001年在Fernandez等人，最大公共子图和最小公共超图的概念被组合以导出图距离度量，并且在2001年Wallis等人基于表示为图并集的最小公共超图的图距离被讨论。

从文献Sanfeliu中已知许多图形匹配算法。所有这些方法都保证能找到最优解，但需要指数时间和空间。另一方面，次优或近似方法在计算步骤的数量上是多项式的，但是可能无法找到最优解。

在2004年，通过计算图的特征向量上的Levenshtein距离来执行不精确的图匹配2005中说明的另一种方法是将邻接矩阵转换成字符串，然后使用前导特征向量对字符串进行串行排序。

然后，通过将字符串匹配技术应用于图形的字符串表示来匹配图形。卡埃利等人，2004年，卡埃利等人，2004年追求不同的想法，其中探索特征(子)空间投影和顶点聚类方法。

然而，在卡埃利等人，2004年，该方法的目标是在图的特征空间中工作，而在卡埃利等人，2004年子图是基于它们在公共子空间中定义的顶点连通性来匹配的。

1. 其他方案

有许多搜索类型可以用来检测克隆罗伊等人，2009年。文本方法属于基本方法。这些方法很容易实现，另一方面，由于源代码中包含大量过量的非程序性材料，它们会遭受各种各样的疾病。例如，通过使用文本比较，检查可变范围可能是一个非常具有挑战性的问题。

基于令牌的比较是下一组需要考虑的方法。这种方法将源代码分成相互比较的标记序列。这比文本更健壮，因为它不能处理不必要的文本材料，如空格、注释等。然而，这种方法仍然不处理变量或方法范围。

更有效的算法是基于树的。它们有两种方法:基于度量的和基于树的。基于度量的度量使用Java源生成的度量。然后将这些指标与原始来源生成的指标进行比较。基于树的方法基于抽象语法子树比较。这些方法用于我们的工作。它们实现起来有点困难，但是它们非常有效，并且提供了更多的搜索选项。相反，与其他类型的算法相比，基于这些方法的算法更耗时。

艾拉·巴克斯特是该领域的先驱，巴克斯特等人，1998年。他提出了一个解决方案，将子树散列到桶中。只有同样的桶树被比较。

Wahler等人在2004年提出了另一个解决方案。他将AST转换成了XML，并在其上应用了数据挖掘技术。剩下的问题是XML处理过程的速度。此外，Koschke等人在2006年提出了一个有趣的选择。他们序列化生成的AST，并只比较它的后缀树标记。该算法速度非常快。它能够在线性时间内检测克隆。

这些算法的缺乏是无法动态检测片段。他们假设一个恒定不变的原始模式。相反，我们的解决方案提供了基于脚本语言的动态输入的使用。这意味着输入可以被调节或迭代，并且搜索树根据搜索的树属性而改变。甚至可以使用变量。例如，用户可以声明类类型的“clazz”变量，然后将其用于名称比较:

Class clazz

Block(StmtNum=2)

if(clazz.Name=='HelloWorld')

...

else

...

这个例子意味着我们搜索包含两个语句的类，如果这个类的名字是“HelloWorld”，那么我们搜索一些东西，或者我们搜索其他东西。

1. Scripthon语言

在这项工作中，开发了一种能够实现这些功能的新的编程语言Scripthon。使用这种语言，可以描述具有属性的代码结构，甚至可以根据搜索到的段属性来改变搜索样本的属性。

Scripthon是一种动态类型化、解释性和非过程性语言。它被翻译成树的表达形式，其用法非常类似于任何其他现代脚本语言的用法。Scripthon语言语义的完整定义超出了本文的范围，可以在Bubliacute;k等人2012年的文章中找到。

因为这种语言被设计成仅仅是一种脚本语言，所以没有特殊的结构来启动脚本。这种语言既不是纯面向对象的语言。编译器的输入是带有一系列命令的文本。这个序列描述了Java源代码中的连续语句。具有可变详细程度的命令对应于可变长度代码段。细节级别不是固定的，并且在每个命令中都可以变化。一个命令可以对应一行源代码；另一个可以用Java描述整个类。Scripthon结构与其他当代动态编程语言的结构非常相似。单个命令用线隔开。脚本中没有命令分隔符。块的内部是制表符嵌套的。一个块没有任何符号定界；只使用制表器的层次结构。

寻找一个特定名称的方法？假设我们有最常见的Java代码:

public class HelloWorld{

public static void main(String[] args){
System.out.println(args);

}

}

假设我们正在寻找名为“main”的方法。很简单。用户只需启动一个文本搜索对话框(通常通过CTLF F快捷方式)并执行搜索过程。不幸的是，这将会发现许多杂七杂八的结果。使用Scripthon，我们可以只搜索方法:

Meth(Name='main')

此外，我们只想要公共的和静态的:

Meth(Name='main';Rest=[public,static])

更重要的是，主要方法最具体的搜索标准是:

Meth(Name='main';Rest=[public, static]; Ret=void;ParNum=1;ParTypes=[String[]];ParNames=['args'])

使用Scripthon，我们可以在主方法中定义一个方法调用:

Meth(Name='main'; Rest=[public, static]) MethCall(Name='System.out.println';Params=['args'])

Scripthon还支持一段代码描述。我们可以这样定义块的属性:

Class(Name='HelloWorld')

Meth(Name='main')

Block(StmtNum=1;Order=false)

同样，这个例子对应于一个给定的“你好世界”例子。主方法中有一条语句，语句的顺序无关紧要。Scripthon的另一个有趣的关键词是“任何”。这对于无限期搜索很有用。这意味着搜索到的语句可以是任何东西，也可以是空的。要描述上面的代码，我们可以编写:

Meth(Name='main')

Any()

但是期望的代码可以是这样的:

public static void main(String[] args) {

int i = 1; i ;

System.out.println(args);

}

我们可以通过以下脚本找到这一点:

Meth(Name='main')

Any()

MethCall(Name='System.out.println')

Scripthon还支持几个关键词。例如，初始化()用于变量初始化，loop()用于公共循环，等等。最后，通过给出的例子，很容易在代码中找到单例:

Class() class

Block(Order=false;Consecutive=false)

Meth(Name=class.Name;Rest=private) MethCall(Ret=class.Name;Rest=[public, static])

这里唯一没有提到的参数是“连续”参数。这意味着块内的语句不能是连续的。这些语句只需要包含在给定块的某个地方。

1. 获得优化的树木

Java编译器应用编程接口用于在第一次迭代中从给定的Java源中获取AST。这个应用程序接口是免费的，包含在Java软件开发工具包中。它提供对控制Java编译器的访问，编译输出之一是给定源的抽象语法树。只需要满足一个条件。Java源必须是可编译的。

浏览Java源代码时，会创建一个节点由四个数字增强的树。这些数字是名为左、右、水平和下水平的自然数。第一个和第二个数字(左、右)表示树前序遍历中节点的顺序索引。因此，祖先的左索引总是小于其子代的左索引，而右索引总是大于任何子代的右索引。级别号表示顶点树层次结构中的级别，数字下的级别表示当前节点下的级别数(与Yao等人2004年描述的方法相比)。

假设x和y是树中的两个节点；以下规则对这些值有效。

该节点是x的祖先，x是if y.leftlt;x.leftlt;y.right的后代。

该代码是x的父级，并且是if 1)y.leftlt;x.leftlt;y.right和2)y.level=x.level-1的子级。

该节点有((x.left-x.right)-1)个子节点。

所有这些数据都是在通过树的一次过程中获得的。获取这些信息不是一项耗时的操作，因为它是在树生产过程中完成的。另一方面，使用这些数字可以显著减少比较的次数。

图1 带索引的AST示例

图2 带有一个子节点的节点“main”

有了这些信息(图1)，我们知道当前处理节

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[19609]，资料为PDF文档或Word文档，PDF文档可免费转换为Word