理论计算机科学电子笔记238（2009）155-171www.elsevier.com/locate/entcsJava源代码的声明式过程内流分析埃玛·尼尔森-尼曼1Görel Hedin3 Eva Magnusson4隆德大学瑞典隆德托尔比约恩·埃克曼2Programming Tools Group牛津大学英国牛津摘要我们已经实现了Java源代码的过程内控制流和数据流分析，一种声明性的方式，使用引用属性语法，增加了循环属性和集合属性。 我们的实现是建立在JastAdd可扩展Java编译器之上的，我们已经在中型Java程序上运行了分析。 我们展示了分析如何使用小型简洁的可组合模块构建，以及它们如何为进一步的源代码分析提供可扩展的框架。初步测量表明，我们的声明式数据流分析和命令式实现之间的执行时间保留字： 声明式，数据流，分析，控制流，Java，编译器，属性语法1介绍控制流和数据流分析构成了许多源代码静态分析的基础，例如，代码优化，重构，强制编码控制，1电子邮件：emma.nilsson_nyman@cs.lth.se2电子邮件：torbjorn. comlab.ox.ac.uk3 电子邮件：gorel. cs.lth.se4 电子邮件：eva. cs.lth.se1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.09.046156E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155ventions，and metrics.这两种分析通常在规范化的中间代码表示上进行，而不是在更高级的抽象语法树（AST）表示上进行，以简化分析，不必处理完整的源语言。然而，直接在源代码表示上进行这些分析可能是有益的，因为在转换为中间代码的过程中，高级抽象不会被编译掉。这对于需要与用户进行某种交互的分析任务尤其重要，例如重构和报告违反编码约定的情况在本文中，我们展示了如何控制流和数据流分析可以直接在编译器前端使用的AST上执行，同时保持良好的性能和紧凑的规格尺寸。此外，我们的方法是完全声明性的，支持模块化和可扩展的规范。我们已经在JastAdd Extensible Java编译器[7]上实现了分析，使用了一种基于扩展属性语法的方法本文中报告的分析是术中分析，即，一个方法的局部。扩展该技术以支持过程间分析是我们正在进行的工作的一部分。我们对传统的Knuth风格的属性文法[10]进行了大量扩展，这些扩展对数据流分析非常有用。属性值可以是对远距离树节点的引用[9]，这对于在主导AST结构之上的拓扑图结构特别有用，例如， 以引用控制流程图中的前趋节点和后继节点。循环属性[8，12]允许属性方程相互依赖，只要有一个定义良好的定点。它们使我们能够声明性地指定传统的数据流属性，如在活性分析中使用的入集和出集。集合属性的概念[6，11]允许属性通过引用属性向远处树节点中的集合贡献部分值。 例如，一个名称可以将其自身贡献给其声明集合属性对于定义反向关系也非常方便。例如，可以使用单个等式从后继集合计算出前导集合。对于每个分析，我们提出了一个面向对象的框架，指定了一组AST节点如何协作计算所需的属性。使用属性语法实现这些框架使它们具有声明性，即，属性的值被定义，但不是它们被计算的顺序。因此，数据流和控制流分析可以在语法导向的fash- ion中为每种语句和表达式单独指定。控制流程分析的框架规定了如何为影响控制流程的每个语句提供一个循环结构。同-E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155157通常，对于改变特定类型的数据的流程的表达式，例如，局部变量的使用和定义，数据流分析的框架具体说明了这些表达式如何改变数据流。然后，这些方程被所提供的框架代码用于组成全局解。 不影响控制流的语句和不影响被分析数据的表达式可以重用框架提供的默认行为。这使我们能够在源代码级别指定控制流和数据流分析，即使是对于复杂的语言，如Java，具有中等的效率。如果语言发展，该框架还允许对分析进行简单扩展，例如，当添加新语句或表达式时。如果新的语言特性包含控制流或数据流，那么这些元素可以以语法导向的风格模块化地指定，如果它们对分析没有影响，那么现有的框架代码可以按原样重用为了评估我们所提出的方法的效率和可扩展性，我们实现了一个分析Java检测死分配到局部变量。控制流框架少于300行代码（JavaScript），数据流框架少于30行代码.死分配分析增加了一个额外的8位数，这使我们总共不到340位数。我们在实际的Java应用程序上运行了死分配分析，这些应用程序的大小大约为40000字节，执行时间小于9秒，包括静态语义检查，例如，名称绑定、类型检查等。初始实验表明，当将我们的数据流分析的声明式实现与使用显式定点迭代的命令式实现进行比较时，执行时间几乎没有差异。本文其余部分的结构如下。我们首先在第2节中描述了控制流分析的实施。然后，我们在第3节中介绍了数据流分析，并在第4节中展示了如何使用这两种分析来分析实际应用。我们将我们的工作与第5节中的相关方法进行比较，并在第6节中总结和概述未来的工作。2控制流分析在JastAdd中，程序被表示为AST。AST节点由具有属性的对象表示。给出这种表示，我们希望提供一个可重用和可扩展的过程内控制流程图的实现控制流通常定义在基本块上，即，具有一个入口点的程序指令的线性序列[5]。典型的定义如下：定义2.1控制流可以描述为有向图G=（B，E）其中B是n个des {b1，b2， . ，bn}，并且E是有向边的集合158E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155G--（bi，bj），（bk，bl）， .节点表示基本块，边缘表示控制-小路。每个节点都有一组直接后继者和直接前代者，它们都可以为空。直接后继集由下式给出：函数ΓG（bi）={bj|（bi，bj）∈E}. 后继函数的逆给出了直接前导函数的集合，Γ−1（bj）={bi|（bi，bj）∈E}.在AST级别，我们可以将每个语句视为代表一个基本块。控制流程图的开始和结束传统上被称为进入和退出块。在我们的例子中，每个方法都有一个入口语句和一个出口语句。为了表示方法的控制流图，我们用AST语句节点表示节点，用这些节点之间的引用表示有向边。在JastAdd中，这些引用可以使用属性和等式以声明方式定义。定义一种方法的控制流程相当于定义以下属性：Set Stmt.succ（）; //每个语句都有一组后继语句Set Stmt.pred（）;//每个语句都有一组前导语句Stmt MethodDecl.entry（）; //每个方法都有一个入口语句StmtMethodDecl.exit（）;//每个方法都有一个出口语句在下面的小节中，我们将研究如何使用JastAdd定义这些属性2.1语言结构我们将使用图1中的代码作为一个运行示例来解释如何将控制流图叠加在现有AST之上。目标是使用属性将图2所示的后继边添加到图1关于这些边缘，有几件事值得注意。某些语句在决定将控制权转移到何处时是主动的。例如，IfStmt将控制转移到它的Then分支，在本例中，该分支以ExprStmt开始。有些语句完成时并不显式地将控制权转移到另一个语句，而是根据上下文隐式地转移控制权。例如，IfStmt中包含的ExprStmt与 IfStmt 后 面 的 语 句 继 续 ， 而 ExprStmt 包 含返 回 并 重 新 计 算WhileStmt。我们首先介绍AST结构，然后继续为后继节点、前趋节点以及最终的入口节点和出口节点定义属性方程。语言结构由图3中的抽象语法定义。 我们将简要地通过结构，因为我们所有的属性和方程都将根据这个语法定义。有Stmt和Expr，它们是抽象实体。Block是Stmt的子类，它包含一个Stmt列表，E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155159条目块IfStmtWhileStmt出ExprStmtExprStmtpublicvoidrun（）{x =y;而（d）D return（）;}图1.一、示例方法体及其抽象语法树。图二、图1中示例的控制流程图。它的孩子。IfStmt有一个条件Expr、一个Then分支和一个可选的Else分支。WhileStmt有一个条件Expr和一个Stmt，它在循环中的每次迭代中执行。某些Exprs可以充当Stmts，因此我们引入一个ExprStmt，将表达式转换为语句。AssignExpr的值是它的RValue，LValue被赋予该 值 作 为 边 值 。 VarAccess 引 用 一 个 变 量 ， 可 以 作 为 LValue 和RValue。MethodAccess是一个带有参数列表的方法调用对抽象语法定义的更全面介绍见[2]。abstract Stmt;Block： Stmt：：= Stmt*;IfStmt： Stmt：：= Expr Then：Stmt [Else：Stmt];WhileStmt： Stmt：：= Expr Stmt;ExprStmt： Stmt：：= Expr;抽象表达式;AssignExpr： Expr：：= LValue：Expr RValue：Expr; VarAccess： Expr：：= Name：String>;MethodAccess： Expr：：= Name：String> Arg：Expr*;图3.第三章。图1中的语言的抽象语法。块IfStmtWhileStmtVarAccess cExprStmtVarAccess dExprStmtAssignExprAssignExprVarAccess xVarAccess yVarAccess d方法Access m160E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）1552.2接班人我们使用一个名为Stmt.succ（）的合成5属性来定义直接后继函数ΓG，如定义2.1所述。默认行为是语句正常完成并继续以下状态。 因此，我们为succ属性引入了一个默认等式，使用继承的6helper属性，表示当前上下文中的下一个语句。这种行为对于不中断该流程的语句是可取的，例如继续下一个状态的ExprStmt。 但是，IfStmt、WhileStmt和Block等语句需要单独处理syn Set Stmt.succ（）= following（）; inh Set Stmt.following（）;同时具有Then分支和Else分支的IfStmt将控制转移到任一语句，但仅具有Then分支的IfStmt将跳转到Then语句或下一个语句。我们可以用下面的公式来捕捉这种行为。集合的形成是从空集开始，然后使用联合运算符添加其他成员。集合是不可变的，每个操作都返回一个新的集合。等式IfStmt.succ（）= hasElse（）？empty（）.union（getThen（））.union（getElse（））getThen（）;WhileStmt的后继语句在条件为true时是其包含语句因此，下面的等式将后继者定义为下面的集合和所包含的语句的并集。与IfStmt相比，所包含的语句的处理方式略有不同。如果包含的语句正常完成，则下面的语句将返回以再次评估条件。因此，WhileStmt需要定义其子对象的following集合应该包括WhileStmt本身，而不是当前的following集合。因此，我们需要两个等式，一个用于WhileStmt的后继者，另一个用于重新定义上下文，即，以下属性，用于包含的语句：EQWhileStmt.succ（）int n = following（）.union（）;EQWhileStmt.getStmt（）.following（）return（）;5 AST节点的合成属性由同一节点中的等式定义。6AST节点的继承属性由祖先节点中的等式定义E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155161BlockStmt的后继语句是第一个包含的语句，或者如果块为空，则是后面的集合BlockStmt的作用就像一个中介器，允许每个包含的语句按顺序执行。 如果语句i在块中完成，那么后继语句是语句i+1，除非i是最后一个语句，在这种情况下，块完成并将控制权交给下一个集合。eq Block.succ（）= getNumStmt（）！= 0？public intfindDuplicate（）. getDuplicate（）;eq Block.getStmt（int i）.following（）=i！getNumStmt（）-1？int getStmt（i+1）：following（）;因此，一些节点需要定义后继属性，另一些节点同时定义后继属性和后继属性，而另一些节点可以重用默认行为。为了推广给出的例子，我们定义了三个角色，可以用来描述一个陈述，以确定需要提供哪些方程explicit jump执行并在本地定义其后继语句。这个类别中的语句需要给出succ属性的等式。语句的典型示例包括IfStmt，还有BreakStmt和ThrowStmt等语句。call subroutine临时将控制权交给另一条语句执行，然后通过定义该语句的后继语句来收回控制权的语句。这类语句需要同时给出succ和following属性的等式。语句的典型示例是Block和WhileStmt。通常完整的语句，其下一个要执行的语句由当前上下文给出，例如，语句在块中的位置与该块的ExprStmt是这一类别中的典型示例。只有前两类中的语句需要为控制流分析提供方程，而第三类中的语句，例如ExprStmt，可以按原样重用框架。前两个角色也构成了分析的扩展框架。如果我们添加一种新的语句，我们只需要确定它是否扮演上述角色。如果是这样，那么我们需要提供一个或两个方程来扩展控制流分析，否则可以按原样重复使用。2.3前任到目前为止所介绍的属性只涉及后继者的集合，但在许多分析中，也需要有前导者的集合。定义162E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155G直接前趋函数r-1使用集合属性pred，该集合属性被定义为直接后继函数的逆，使用以下两个规则。coll Set Stmt.pred（）[empty（）] with add;Stmt为每个succ（）将其贡献给Stmt.pred（）;第一条规则为Stmt节点声明一个名为pred的集合属性（coll）。它的值是Set类型的，定义为对empty的调用（Set上的一个方法）与一些贡献的组合，每个贡献都由对add的调用（也是Set上的一个方法）添加。(The集合属性的贡献方法，在这种情况下是add，必须是这样的，添加贡献的顺序无关紧要。第二条规则定义了贡献（contributes... 去... 对于每一个）。该规则表示Stmt将其自身（this）贡献给其每个后继（succ）的前驱集（Stmt.pred）集合属性及其在JastAdd中的评估的更详细的介绍可以在[11]中找到2.4入口和出口节点从流程分析的角度来看，在控制流程图中有明确的入口和出口节点通常是方便的。由于AST可能没有唯一的入口和出口节点，我们使用非终结符属性（也称为高阶属性）将它们附加到AST [15]。像其他属性一样，它们使用等式定义，但被认为是高阶的，因为它们也充当AST中的节点，并且本身可以具有属性。对于每个MethodDecl，我们定义了两个非终结符属性：entry和exit。然后我们将方法块添加到入口节点的后面，并将出口节点添加到下面是方法块。这有效地将入口节点附加在块之前，如果块完成，则它绑定到出口节点。我们还提供了一个等式，它将对出口节点的引用传播到方法块。 That way语句希望将控制转移到方法的末尾，例如，aReturnStmt，只是将退出引用添加到其后继集。syn nta Stmt MethodDecl.entry（）= new EmptyStmt（）;syn nta Stmt MethodDecl.exit（）= new EmptyStmt（）;eq MethodDecl.entry（）.following（）=getBlock（）; eq MethodDecl.getBlock（）.following（）= exit（）;EQMethodDecl.getBlock（）.exit（）return（）;E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）1551632.5高级语言结构当为Java等语言构造控制流图时，需要处理异常和语言结构，如try-catch-finally和throw。特别是try-catch语句的finally块，它会中断与break、continue和return相关的控制流程。在定义控制流程图的属性所需的大约300个参数中，大约240个参数与这些语言结构直接相关。我们使用合成属性在AST中向上传播信息。例如，可以通过为所有Stmt类型的节点定义的名为uncaughtThrows的属性来获取不匹配的throw语句集。信息，例如，封闭的TryStmt在AST中使用继承的属性（例如，RestransingTryStmt）向下广播。这些合成和继承的属性相互匹配。例如，由uncaughtThrows属性给出的集合与由RollingTryStmt属性给出的最近的封闭try语句中的catch子句匹配。如果没有找到匹配项，则将控制流定向到封闭的TryStmt的finally块，如果存在这样的块，则将其传递到下一个封闭的TryStmt，依此类推。类似的技术也用于处理break、continue和return语句。例如，在执行break语句之后，break语句和其封闭目标语句之间的所有封闭finally块while语句，需要在目标语句之前执行。return语句的控制流只是这种情况的一个特例，出口节点作为常量目标语句。3数据流分析我们想在上一节定义的控制流图上分析数据流一种典型的数据流分析方法是活性分析.基于[4]中的定义，我们使用以下活性定义定义3.1设in（b）是块之前的变量集b和letout（b）是紧接在块b之后的变量的集合。设def（b）是b中赋值变量的集合，use（b）是中使用变量的集合，B. def（b）和use（b）以如下方式与in（b）和out（b）集合相关：in（b）=use（b）（out（b）\def（b））out（b）=x∈succ（b）在（x）164E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155如果一个变量的赋值将被控制流程图中的后继者使用，则该变量是活的。如果变量在旧值被使用之前被赋予新值，则旧的赋值可以被认为是不必要的。由于我们的控制流分析是在语句而不是块上进行的，所以我们需要定义每个语句所使用的变量集，以及每个语句所分配的变量集。这些集合与后继集合相结合，使我们能够纯粹按照陈述来表达入集合和出集合。因此，为每个语句定义这些属性将使活性分析对所有类型的语句都有效。我们还注意到，内集和外集是使用相互依赖的递归方程定义的。这类方程通常通过迭代求解，直到达到一个定点，如果所有中间值都可以组织在一个有限高度的格子中，并且所有运算在该格子上都是单调的，则可以保证这一点3.1使用集合和定义集合计算访问变量集的主要挑战是支持源语言中的所有类型的语句及其所包含的表达式像Java这样的复杂语言有20多条语句和50多个表达式.幸运的是，事实证明，在JastAddExtensibleJavaTooler中支持所有这些结构是非常容易的，我们现在将对此进行解释。所有访问局部变量的表达式都封装了一个执行实际绑定的VarAccess节点。此外，每个VarAccess节点都有两个布尔属性isDest和isSource，用于确定访问是作为LValue还是RValue。有些节点实际上两者都起作用。例如，作为后增量运算符'++'的子级的VarAccess使用集可以通过收集所有VarAccess节点来计算，这些节点充当由特定语句包围的RValue。这可以非常方便地使用集合属性来完成，如下所示。如果每个VarAccess充当RValue，则将其相应的声明贡献给封闭语句def集合使用相同的策略计算。从表达式到其封闭语句的绑定是使用继承的属性计算的。每个语句都为它的所有子语句提供一个等式，声明它是封闭语句。这个单一的等式将绑定向下传播到任意深度的表达式，因为JastAdd中的继承属性的等式对于子树中的所有节点都有效，而不仅仅是直接子节点。coll Set Stmt.use（）[empty（）] with add;VarAccess contributes decl（）当isSource（）&&decl（）.isLocalVariableE. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155165to Stmt.use（）for stampingStmt（）;coll Set Stmt.def（）[empty（）] with add;VarAccess contributes decl（）whenisDest（）decl（）.isLocalVariable（）to Stmt.def（）for restransingStmt（）;inh Stmt Expr. stmt（）;EQStmt.getChild（）. getSingStmt（）= this;这三个属性有效地计算了Java中所有语句的使用集和定义集例如，考虑一个具有图3所示结构的MethodAccess。它的参数很可能包含用法和定义，因为两者都是Java中的表达式然而，我们不需要为该语言结构提供任何额外的等式，因为每个VarAccess的贡献都是自动收集的，并且继承的属性对所有后代都有效，而不仅仅是直接的孩子。这些对树结构进行抽象的方法是三个等式足以处理Java等复杂语言中所有类型表达式的原因。从扩展的角度来看，这一点也很重要。如果我们添加了一个新的语言结构来修改一个局部变量，我们只需要确保它封装了一个VarAccess，并为继承的属性isDest（）和isSource（）提供等式，这在前端的其他地方都是需要的，并且useset和defset属性仍然有效。在第2节中，我们展示了如何通过添加几个方程来扩展控制流分析以支持新的语句。这意味着，无论我们是否添加新语句或表达式，扩展控制流和数据流分析都需要几个等式，以使它们支持语言扩展3.2在集和出集定义3.1中的入组和出组方程是相互依赖的。如前所述，只要值形成有限高度的格子并且所有函数都是单调的，这样的方程就可以通过迭代来求解。这显然是我们的方程的情况下，因为幂集的一组局部变量有序的包含形式的一个格与空集作为底部和工会是单调的。因此，如果我们从底部值开始，迭代地应用方程作为赋值，直到值没有变化，那么就会达到一个固定点JastAdd通过循环属性显式支持这种迭代，如[12]所述如果我们将一个属性声明为循环并提供一个底值，那么属性计算器将自动执行定点这使我们能够使用以下两个循环，以非常接近其正式定义的方式指定输入集和输出166E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155属性：7syn Set Stmt.in（）circular [empty（）] =Stmt.in（）= use（）.union（out（）.compl（def（）;syn Set.out（）circular [empty（）]{ Set set = empty（）;for（Iterator iter = succ（）.iterator（）; iter.hasNext（）;）{Stmt stmt=（Stmt）iter.next（）;设置= set.union（stmt.in（））;}return set;}在我们的实际实现中，我们通过将其定义为集合属性来使用更简洁的outset规范，从而反转计算方向：coll Set Stmt.out（）circular [empty（）] with add;Stmt contributes in（）to Stmt.out（）for eachpred（）;使用循环属性的另一种方法是手动实现定点计算。为了比较，我们实现了[4]中给出的命令式活性分析算法这种解决方案需要手动记账来跟踪更改，这大大增加了实现的规模，并且算法的本质与记账代码纠缠在一起。此外，有必要静态地近似循环中涉及的函数以进行转换，或者手动动态地跟踪这种依赖关系。在使用循环属性时，属性计算引擎会自动处理这些问题。在第4节中，我们在大小和速度方面对两种实现进行了更定量的比较。4应用为了评估我们的方法的效率和可扩展性，我们对Java进行了一个简单的分析，它可以检测局部变量的死赋值，即，程序中以后不使用的变量的赋值。这种分析可以很容易地作为前一节中描述的活性分析的扩展添加。我们使用以下定义来检测无效分配：7out的等式使用了一个赋值和一个for循环，这可能令人惊讶，因为我们的方法是声明式的。然而，因为我们使用Java方法体语法来定义属性值，所以在这里使用命令式代码是很自然的。这与声明式方法完全一致，只要该代码没有网络端影响，即，只有局部变量被修改。E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155167表1控制流分析（CFA）的大小没有为命令式分析给出，因为它使用声明性实现中的属性。另外两列显示数据的大小--数据流分析（DFA）和死亡分配分析（DAA）的大小执行CFA（非洲金融共同体）DFA（二）DAA（单位）声明性300308势在必行-1908定义4.1如果一个变量在语句中定义，但在语句之后没有立即存活，则该语句被认为是死的，因为赋值是不必要的。也就是说，语句s在以下情况下是死的：未定义输出这个定义检测不必要的分配。死赋值可能仍然有需要计算以保留程序行为的右侧表达式。在JastAdd中，定义如下所示syn boolean Stmt.isDead（）=！public int findDuplicate（）;为了收集一个编译单元中的所有死赋值，我们将一个集合属性deadCode（）添加到编译单元AST节点。死赋值使用contributes子句将其自身贡献给其编译单元的集合。对编译单元的引用使用一个名为configuringconfigurationUnit的继承属性传播到语句节点。coll HashSet parametationUnit.deadCode（）[new HashSet（）] with add root parametationUnit;Stmt在isDead（）到configureationUnit.deadCode（）的时候为configureationUnit（）贡献这个;INHSystem. out. println（）;EQSystem.out.println（int i）（i）. browsing（）= this;总的来说，从活性分析到死赋值分析的完整声明性扩展加起来只有8个字节。作为比较，我们从上一节扩展了活性的命令式实现，以包括对死赋值的搜索。 这个扩展的大小是相同的：八尺。这些数字总结在表1中。这两种实现都依赖于声明性控件流实现.声明式控件的分析覆盖了Java1.4的所有部分，加起来只有300个字节，考虑到语言的复杂性，这是一个很小的数字不同的活性实现的大小相差约六倍，而死分配实现的大小相同。168E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155表2代码行数（CRC）、没有任何额外分析的编译时间（CT）、使用命令式死代码分析的编译时间（CT + IA）、使用声明式死代码分析的编译时间（CT + DA）以及发现的死语句数（DS）项目LOCCT（s）CT + IA（s）CT + DA（s）DS（#）ANTLR膨胀4200039000八、73八、3710.7010.9010.90十一岁179611为了测试我们的实现和测量执行时间，我们选择在以下Java项目中寻找死赋值• 安特尔（v. 二、第七章7）-一个解析器和翻译器生成器[1]。• 膨胀，膨胀1 .一、0）-字节码级优化和分析工具[3]。表2总结了两种实现的执行时间（有分析和没有分析）以及发现的无效分配数。这两种实现几乎同时运行。我们发现96名死者死于鹿角，11名死于肿胀。在bloat中，一半的死赋值是null赋值，而在antlr中只有少数死null赋值。antlr中三分之二的死赋值是由于一个频繁但未使用的变量。5相关工作Silver是一个最近的属性语法（AG）系统，与JastAdd有许多相似之处，但它不支持循环属性。Silver也被应用于声明性流程分析[16]，但使用的方法与我们的方法不同。在Silver方法中，规范语言本身被扩展以支持控制流和数据流分析的规范。实际的数据流分析不是由属性文法系统进行的，而是由外部的模型检查工具进行的。这种方法的动机是在同一程序表示上声明性地指定数据流分析的困难，例如，类型分析。并无就该方法呈报表现数据。相比之下，我们已经展示了如何控制数据流和数据 可以直接使用JastAdd的一般AG特性以简洁的方式指定Cashow，特别是依赖于引用属性，循环属性和集合属性的组合。Morgenthaler [13]为源到源工具开发了静态分析技术。为了降低成本，提出了有效的需求驱动分析技术，而不是传统的穷举方法。这些技术直接在AST上操作，AST是E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155169一个源到源的工具架构。不构建显式控制流程表示。相反，一个所谓的虚拟控制流是由所有可能的控制后继者和前驱者的需求驱动计算构造的。用C++实现的C语言实现这个方案的函数需要大约1000行代码。这种方法和我们的方法之间的一个主要区别是，在使用JastAdd时，需求驱动的求值器是从简洁的声明性语法规范自动构建的。Soot是一个用于优化、分析和注释Java字节码的框架该框架提供了一组程序内和整个程序的优化，其范围比本文中提出的分析更广。Soot基于几种中间代码表示，例如，类型的三地址代码，并提供不同表示之间的无缝转换Java源代码首先被翻译成这些表示之一Soot中的控制流和数据流框架确实非常强大，而且API也相当小.与我们的方法相比，一个主要的区别是Soot方法不是声明性的，因此在组合分析或添加新的分析作为框架的6结论控制流和数据流分析对于复杂语言（如Java）的源代码级分析来说通常是很麻烦的。主要原因是实现支持当今主流语言中此外，由于语言不断发展，因此需要相应地更新分析我们已经展示了如何引用属性文法增加了循环属性和集合属性提供了一个很好的基础，声明指定控制流和数据流分析。规范是简洁的，接近教科书的定义，但生成的分析器对于实际应用是足够有效的。规范也是可扩展的，因为当新功能添加到语言中时，可以模块化地扩展分析。这些是本文的主要贡献：• 我们提出了如何简明地指定控制流和数据流分析声明使用属性语法扩展引用属性，循环属性，和集合属性。• 我们为控制流和数据流分析提供了声明性的框架.这些框架提供了默认行为，因此只需要相等的170E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155用于语句的实例，对象控制语句流和操作所需数据类型的表达式这些方程以语法导向的方式指定，并且可以模块化地扩展以用于新的语言构造。• 我们已经实现了所描述的框架和分析的JastAdd可扩展Java插件的顶部，并评估了现实世界中的应用程序的约40000行代码的实现。有几种有趣的方法可以继续这项工作。本文中提出的设计思想和框架是通用的，看看它们如何扩展到更高级的分析，例如，面向对象的调用图构造和过程间指向分析。我们已经在这个方向上做了一些有前途的工作，例如简单的整个程序去虚拟化分析[11]。我们还想为其他传统的后端分析设计和实现声明性框架，例如转换为SSA-表单。另一个有趣的领域是将同样的技术应用于进行特定领域的源代码级别分析，例如，强制执行框架约定。引用[1] Antlr，2007年。 http://www.antlr.org/。[2] JastAdd，2007年。 http://jastadd.org。[3] 普渡大学膨胀，2007年。http://sourceforge.net/projects/javabloat/。[4] Alfred V. Aho，Ravi Sethi，and Je Escherey D.厄尔曼制造原则、技术和工具。Addison-Wesley，1986年。[5] 弗朗西斯·E·艾伦 控制流程分析。 SIGPLAN不。，5（7）：1[6] 约翰·唐·博兰。远程属性语法。J.ACM，52（4）：627[7] 托比约恩·埃克曼和格瑞尔·赫定。JastAdd可扩展Java插件。在OOPSLA[8] 罗德尼·法罗。为循环但定义良好的属性文法自动生成固定点查找赋值器。在CC'86的会议记录ACM Press，1986.[9] 格瑞尔·赫定引用属性语法。 Informatica（斯洛文尼亚），24（3），第301- 317页，2000年[10] Donald E.高德纳上下文无关语言的语义。Mathematical Systems Theory，2（2）：127-145，June 1968.更正：数学系统理论5，1，pp。95-96（1971年3月）。[11] 伊娃·马格努森，托比约恩·埃克曼，和格瑞尔·赫定。用集合属性扩充属性文法--求值与应用。第七届IEEE源代码分析和操纵集，2007年9月[12] 伊 娃 · 马 格 努 森 和 格 瑞 尔 · 赫 丁 循 环 引 用 属 性 文 法 的 评 价 与 应 用 。 Science of ComputerProgramming，68（1）：21E. 尼尔森-尼曼等人/理论计算机科学电子笔记238（2009）155171[13] 摩根塔勒。软件转换工具的静态分析。博士毕业论文，加州圣地亚哥大学，1997年。[14] Raja Vallée-Rai，Laurie Henrique，Vijay Sundaresan，Patrick Lam，Etienne Gagnon，andPhong Co. Soot - a Java Optimization Framework.在CASCON 1999的Proceedings，第125-135页，1999年。[15] H. H. 沃格特， S. D. 斯维尔斯特拉， 和 M. F. 柯伊伯更高 秩序 属性 语法在Proceedings PLDIACM Press，1989.[16] Eric Van Wyk，Lijesh Krishnan，August Schwerdfeger，and Derek Bodin.基于属性语法的Java语言扩展在ECOOP'07的诉讼中Springer，2007年。
我的内容管理
展开
