用XML实现ANSI C程序切片的灵活数据交换格式

30理论计算机科学电子笔记65 No.3（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html20页用XML川岛隼人2部信息科学，日本科学技术高等研究所（JAIST），1-1 AsahidaiTatsunokuchi Nomi Ishikawa，923-1292，JAPAN摘要在本文中，我们考虑ANSI C程序切片使用XML（可扩展标记语言）。我们的目标是为CASE工具建立一个灵活、有用和统一的数据交换格式，这是一个关键问题，使它更容易开发CASE工具，如程序切片器。尽管XML在这种数据交换格式上有很大的潜力，但我们首先指出仍然有许多具有挑战性的问题需要解决。然后，作为我们的目标的第一步，我们介绍ACML（ANSIC标记语言），它描述了ANSI C代码的语法结构和静态语义。在我们的初步实验中，我们有一个很好的结果，它只花了0.5人月，以实现韦瑟1介绍程序切片[22]是由M.Weiser [24]，这有助于降低软件开发和维护的成本，特别是调试，测试和程序理解。然而，不幸的是，软件切片工具尚未在软件开发领域得到广泛使用，尽管有几个程序切片工具[23][14]可用。原因之一是因为开发软件切片器的成本非常高。软件切片器之类的CASE工具往往有单独的解析器和分析器，这些解析器和分析器可以在CASE工具之间共享像Bison [17]这样的 LALR（1）解析器生成器降低了开发解析器的成本本文的目的是表明我们应用XML的方法[3]（可扩展标记语言）到软件切片的应用是有用的，因为1电子邮件地址：gondow@jaist.ac.jp2电子邮件地址：hayato-k@jaist.ac.jp·c2002年由ElsevierScienceB出版。 诉 操作访问根据C CB Y-NC-N D许可证进行。贡多31为ANSI C和XML技术（包括DOM [26]和XML解析器[9]）精心设计的DTD（文档类型定义）可以大大降低开发程序切片器的成本我们的目标是为CASE工具建立一个灵活、有用和统一的数据交换格式，这是一个关键问题，使它更容易开发CASE工具，如程序切片器。由于XML兼有纯文本和结构化格式的优点，因此XML在这种数据交换格式方面具有很大的潜力此外，XMI [16]（XML元数据交换格式）允许我们将UML图作为XML文档处理，因此XML可以弥合软件开发的上游和下游部分之间的巨大差距要实现这一目标，还有许多具有挑战性的问题需要解决。例如，选择最好的底层语法，确定抽象程度或表示的粒度，以及决定如何处理各种派生数据，这些都不是小事此外，定义程序语义的正确表示可能非常困难，包括系统调用和内联汇编代码，不完整（错误）程序以及程序员的意图。作为实现这一目标的第一步，我们引入了ACML（ANSI C标记语言），它描述了ANSI C代码的语法结构和静态语义在我们的初步实验中，用0.5人月的时间实现了Weiser的基于ACML的切片器，而用2人月的时间实现了ANSI C解析器和XCI（Experimental C解释器）的因此，粗略地说，我们在实现Weiser本文的组织结构如下。第2节描述了为软件切片器解压缩DTD的问题，尽管XML在CASE工具的数据交换格式中具有很大的潜力。第三节介绍了ACML（ANSIC Markup Language），它的目的是为了方便开发ANSIC的静态切片器ACML包括有关语法结构和静态语义的信息，如类型、符号和语言构造之间的第4节描述了我们的XCI（实验ANSI C解释器），它也可以作为从ANSI C源代码到ACML标记文档的转换器。第五节给出了我们的初步实验。第6节介绍了相关工作。最后，第七部分给出了结论和未来的工作.2为什么XML用于程序切片？2.1XML在CASE交换中的优势开发CASE工具（如程序切片器）的成本非常高。一个原因是因为CASE工具中的内部数据通常不可用于其他工具，尽管这些数据可以在CASE工具之间共享因此，大多数CASE工具都有自己的解析器和分析器，贡多32可维护性低这是一个关键的问题，找到或开发一些技术，以促进数据共享，或交换的CASE工具在一个优雅的和成本效益的方式。CASE工具的通用格式的想法并不新鲜。例如，已经提出了CDIF [6]（CASE数据交换格式）和PCTE [5]（便携式通用工具环境）。但是，不幸的是，这些技术还没有在CASE工具中得到广泛的应用因此，对理想格式的追求仍在继续。XML已经成为各种类型数据的标准格式，特别是Web文档。XML可以成为实现我们目标的有效工具，因为XML具有以下积极特性。• XML兼有纯文本和结构化数据的优点。XML文档是人类可读的，没有任何XML特定的应用程序。传统的文本处理工具，如sed、grep和perl也可以应用于XML文档。• 在不同的平台之间交换XML文档相对容易，因为文本数据很容易交换，没有任何数据转换（如字节排序）的问题• 程序结构可以表示为XML标记的自然嵌套程序之间的关系可以表示为ID/IDREF链接。• 程序结构和关系可能很复杂，但XML• 各种XML工具，如XML解析器[9]、DOM [27]和DOM [26]，都可以灵活地处理XML文档。• XML标签是可扩展的，可以更好地描述特定于应用程序的数据。• 即使不完整的数据也可以存储为XML文档，只要数据表示为纯文本，尽管XML文档可能无效。2.2什么是挑战？尽管XML具有2.1节中提到的巨大潜力，但XML并不是开发CASE工具的DTD提供了一种定义标签的方法，但不是具体的标签本身。定义灵活、有用和统一的标签来描述各种各样的软件对象和它们之间的复杂关系仍然具有挑战性因此，研究XML并将其应用到CASE工具中具有重要意义在本节中，我们列举了在为ANSI C开发DTD时遇到的挑战性问题虽然在第3节中介绍的ACML只试图解决前3个问题，但我们相信ACML是实现我们解决所有问题的目标的一个很好的步骤ACML是ANSI C语言的DTD，包括抽象语法树、类型、符号等信息。贡多33• 选择最好的ANSI C语法。GCC [18]中使用的语法可能不合适，因为它很复杂，因为它是非标准的扩展，如asm-syntax用于内联as-sort代码，或符号名称，如notype-declarator，它不会出现在标准语法[12]中标准符号名称（即，非终结符和终结符名称）对于可理解性是重要的，但是即使是标准语法[12]也不合适，因为，例如，有18种表达式，如主表达式和加法表达式，只是为了引入运算符的优先级和结合性可以使用DTD中可用的EBNF简化语法，同时保留基本信息，但基本信息取决于应用程序。此外，Badros在[2]中认为，他的Java标记语言（JavaML）使用用于解析的底层语法是不合适的，Badros的目标之一另一方面，底层语法中需要细粒度的信息，例如，对于基于XML的程序转换。因此，选择最好的语法并不是一件小事。• 表示具有相同含义的不同代码ANSI C中的一些代码片段具有不同的AST，但在语义上是等效的。例如，下面的8个类型说明符列表都是合法的，并且表示相同的类型：unsigned long int，unsignedlongint，unsigned longint，longintunsigned，intunsigned long，intlong unsigned，unsigned long，long unsigned为它们引入唯一的（规范的）XML表示是否更好？答案取决于情况。例如，一个唯一的表示形式便于检查类型等价性，但不能区分 我们几乎总是用for- mer，但从不用后者。当需要考虑编码风格时，这种差异可能至关重要。这表明我们需要同时处理抽象和具体语法树• 处理派生数据时的大小/时间权衡。程序片是一种典型的从原始程序中导出的数据。程序切片的计算通常需要花费大量的时间，因此切片的结果需要以XML文档的形式存储然而，容易重新计算的导出数据（例如，标识符的长度）不值得存储为XML文档。XML文档很可能很大，因为有很多标签和属性，所以文件大小也很重要。现在，我们如何确定是否应该存储给定的派生数据显然，在处理派生数据时，文件大小和计算时间之间存在• 要存储的各种信息贡多34extern intx = 999;/* 合法声明 */存在许多待存储的程序信息的候选者，诸如静态语义（例如，类型，符号），人类活动（例如，为测试和调试做了什么），动态语义（例如，可变值的历史以及与其它进程或OS的通信），词汇信息（例如，缩进、大括号放置、注释），并为它们分析我们应该如何为它们设计DTD ？ 特别 是， 很 难为动态语义设计紧凑、灵活、有用和统一的DTD[20])，因为原始轨迹往往过于庞大且过于非结构化。此外，DTD应该可用于不同的编程语言和不同的动态分析工具。• 表示程序员下面的代码片段是ANSI C中合法的外部声明一个外部声明3带有一个初始化器，如虽然这段代码是相当合法的，但其他程序员或审查-因为这段代码不寻常，所以ers可以感觉到这段代码有问题。实际上，ANSI C程序员有时会故意做一些不寻常的事情那么，我们如何表达程序员的意图呢？例如，在Lint[11]中，特定于lint的注释/*NOTREACHED*/会抑制有未到达代码的警告因此，一个简单的意图可以通过引入一些指令来表示，如/* NOTREACHED */。但复杂的意图又如何呢？例如，描述什么样的UNIX命令应该被设置为命令man的环境变量PAGER是不容易的，因为使手册看起来更好的意图是模糊的。• 程序中约束的表示程序中有两种约束对动态语义的约束。例如，对变量值的约束（如x>0）是典型的它们通常可以使用assert宏来表示（例如，return（x>0）;）. 其他约束包括编码风格（例如，命名约定），代码-分组规则（例如，禁止隐式强制转换），以及设计策略（例如，一些设计模式的使用），这与上述“程序员的意图”有关，并且可能难以以机器可处理的• 表示有错误的程序。即使给定的程序有错误，也应该将程序存储为XML文档，因为它可以为调试或测试提供有价值的信息。因此，DTD应该被设计为接受3函数外部的声明称为外部声明。··贡多35错误.现在的问题是如何将语法错误、静态错误（例如，使用但未声明的变量）和动态错误（例如，内存泄漏）。编译错误可以通过程序员的注释或编译器的错误恢复信息来隔离并简单地用XML标记（如）来表示为XML• 软件开发上下游的合作XMI（XML元数据交换格式）[16]包括UML的DTD这意味着上下游部分之间的巨大差距可以通过XML技术来弥合为了使其成为现实，我们需要找到一种方法将ACML与XMI巧妙地联系起来• C语言的扩展和方言典型的C扩展和方言（例如，asm-语法，标识符中的美元符号）可能值得存储为XML文档，因为许多程序都使用它们。• 库函数和系统调用。表示C库函数和系统调用的语义是相当困难的例如，一个C标准库函数信号决定了如何处理后续信号。一旦使用两个参数调用signal：一个信号号和一个函数指针，当指定的信号出现时，函数被显然，信号可以改变程序的控制流程。因此，在对包含信号调用的程序进行切片时，应考虑信号。但怎么做呢？信号可以出现在程序中的任何位置。我们如何构造控制流程图？如何将信号的语义表示为XML文档？这种讨论几乎适用于其他系统调用，如fork或execve。3ANSI C标记语言ACML是我们开发的ANSI C标记语言。ACML的整个DTD是400行，可以在XCI主页上找到[7]。ACML标记的程序具有抽象语法树和静态语义的信息，如类型、符号、控制流以及声明和引用之间的关系ACML旨在对静态分析程序（如静态切片器、交叉引用器和静态测试用例生成器）的CASE工具有用。实际上，我们发现ACML在Weiser切片器的实验实现中是有用的我们对ACML采取了细粒度的方法;不仅函数和状态，而且包括文字和变量在内的所有语言结构都使用ACML标记。这是因为大多数先进的切片器需要语法的细节。 作为细粒度方法的结果，ACML标记的程序往往非常大。如表1所示，即使对于带有#include stdio.h>的<贡多36源代码ACML标记码HelloWorld（不包含#include stdio.h>）85字节19，571字节HelloWorld（带有#include stdio.h>）71字节547，617字节XCI中的xml. c54，375字节3，581，613字节GNU Global中的global.c[28]27，908字节3，202，088字节表1源代码和ACML标记代码超过500K字节，因为头文件stdio. h引入了大量的声明，类型（通常是结构定义和类型定义名称）和符号。在本节中，我们首先展示ACML特性的概述，然后解释ACML标记如何描述ANSI C程序。3.1ACML特性• ACML可以标记任何ANSI C程序。我们选择ANSI C是为了获得实践经验，所以如果我们只支持ANSI C的一个子集是没有意义的。• ACML标记在标准ANSI C语法中以非终结符命名[12].ANSI C语法非常复杂;语法[12]包括183个结果和65个非终结符，大多数程序员都不熟悉（例如，direct-abstract-declarator）。 如果ACML从标准语法中定义不同的标记名，情况会更糟，因为理解非终结符代表什么会更困难。这就是为什么GCC语法很难理解的• ACML标记的代码具有关于原始代码的AST及其细粒度静态语义的信息。尽管我们在2.2节中提到有各种各样的信息要存储，但我们决定将当前ACML的内容限制在AST和静态语义上，因为将所有信息都合并到ACML中过于雄心勃勃细粒度是必需的，因为大多数程序切片技术使用一些语法细节。• ACML标记的代码可以不解析为原始的ANSI C代码。这是显示ACML标记的代码是否具有足够信息的标准之一。我们已经为ACML实现了一个解解析器#include）和词汇信息（例如，评论）没有恢复。贡多37intn（intm， intn）{}returnm +n;3.2句法结构虽然ACML的语法结构元素的嵌套• 使用EBNF符号，如'？’ (optional), ‘• 将表达式的18个不同的非终结符联合起来（例如， primary-expression）到"expression“标签，• 引入属性同时保留静态CASE工具，特别是静态程序切片所需的信息。ACML有45个产生式和17个非终结符，而标准文法有183个产生式和65个非终结符。例如，下面的函数声明，被XCI转换为下面的ACML标记文档4(XCI将在第4节中描述。）<函数定义><联系我们<声明符rhs=“pointer_null”><声明符rhs=“func_new”><声明符rhs=“id”>plus/>/><参数声明rhs=“dec”><联系我们<声明符rhs=“pointer_null”><声明符rhs=“id”>m/>/><联系我们<参数声明rhs=“dec”><联系我们<声明符rhs=“pointer_null”><声明符rhs=“id”>n/>/><联系我们/><声明rhs=“复合”><语句rhs=“return”><表达式rhs=“add”>4为了表示，除了'rhs'之外的所有属性。完整结果见[7]。贡多38unsigned long x;int long unsigned;<型><联系我们<联系我们struct list{int数据;structlist *next;}的情况;<表达式rhs=“identifier”>m/>/><表达式rhs=“identifier”>n/>/><联系我们/>3.3类型在2.2节中，我们讨论了如何表示相同的含义，但不同的代码，其中的问题是是否引入一个唯一的表示更好我们通过提供两种在ACML中表示类型的方法来解决这个问题。例如，以下两个声明，在ACML的AST部分转换如下， long/><！-- 对于x--> long/> unsigned/>！对于y-->并转换为相同的类型表示。因此，我们有两个类型说明符的唯一表示“is long”和“is short”都存在的原因是因为我们甚至希望在ACML中表示非法声明，通常，类型信息需要使用ID/IDREF属性表示的图结构。例如，下面的列表结构是一种典型的递归数据类型，转换如下（见图）。1），<类型ID=“X2618d70”><！-- ID--> t_int> t_int/> t_pointer>！--联系我们贡多39<符号名称=“x”类型_ref=“X2618 c70”ast_ref=“X25f8190”命名空间=“正常”命名级别=“文件”/>产品编号：X2618d70type_ref=“X2618d70”图1.一、结构列表的图形结构3.4符号和链接符号的信息简单地作为一个序列的<符号>元素放置在<翻译单元>外部符号的后面，<语句rhs=“compound”>用于本地。例如，对于外部声明'intx'，符号'x'在ACML中表示如下5：属 性 type ref 引 用 相 应 的 元 素 ， ast ref 引 用 AST 部 分 中 < 的declarator>。ANSI C有4个互不干扰的命名空间;namespace表示' x '所属的命名空间属性namelevel指示' x '是否如上所述，ID/IDREF属性为ACML元素之间的关系建立了几个链接除了这些链接之外，还使用ID/IDREF表示两种类型的链接• 控制流的链接。例如，标签语句<声明rhs=“label”id=“X25f84b8”> foo/><声明rhs=“goto”goto_ref=“X25f84b8”> foo<联系我们/>其中goto语句的目的地（即， goto ref）是ID值为X25f84b8的标签语句。属性case ref、default ref、continue ref和break ref扮演类似的 角色。• 从引用到定义。例如，下面的代码片段5由于空间不足，这里省略了10个属性贡多40整数x;/* 声明 */return x; /* statement */转换如下。<声明><联系我们！--ID--><声明符id=“X25f80b8”>x/><语句rhs=“return”>！-- IDREF -->x/>其中X25f8100的ID值将' x '的引用连接点火。3.5讨论我们已经发现了几个改进ACML的问题首先，正如你在[7]中看到的，ACML的内容模型是不确定的。确定性内容模型的要求是不规范的，因此ACML是否被拒绝取决于XML解析器。实际上，ACML可以与XML4J 3.1.1[9]一起工作，但不能与JAXP 1.1.3 [21]一起工作。在使用JAXP 1.1.3时，我们无法进行有效性检查我们希望在定义DTD时不受这种限制的困扰因此，在下一个版本的ACML中使用其他模式（如RELAX [10]）可能是值得考虑的其次，我们在ACML中没有使用XML缓存[25]。我们应该为ACML使用XML命名空间，以便与其他标记语言（如XMI）更具互操作性。最后，当前XCI使用XCI的AST中的指针值生成ID值虽然这保证了每个元素都有一个唯一的ID值，但同一文件的不同版本并不共享相同的ID值，这使得基于XML的版本控制更加复杂。4实验C解释器我们已经开发了XCI [7]（Experimental C Interpreter），当使用' --xml '选项调用时，它可以将任何ANSI C程序转换为ACML标记的文档如果没有图图2显示了XCI的功能XCI由大约14，000行ANSI C代码组成，目前在Windows 2000和Solaris上的Cygwin 1.3.6下运行8.实施XCI的第一个版本花了大约三个人月的时间。下面是一个执行C代码arg.c的XCI会话示例，它只是打印贡多41%xci.exe arg.c --args 10 20argv [0]=arg.c[1] = 10argv [2] = 20%ANSI C源文件AST，静态信息解释的选项公司简介堆叠程序计数器ACML标记文档图二、XCI执行概述命令行参数。在开发的早期阶段，XCI被设计为具有API 允许程序员直接访问XCI中的内部AST数据结构。这是一个类似于在Sapid [15]中使用的方法。但我们认为，很可能这样的API对于程序员来说要花很多钱来学习，而且API依赖于XCI的内部实现。为了解决这些问题，引入了ACML，并将XCI更改为在使用“--xml”选项调用时输出带有ACML标记的我们认为，是正确的，因为XML在“关注点分离”中扮演了重要角色使用XCI和ACML的Weiser切片器的实验实现4.1AST遍历XCI的显著特征之一是通过AST遍历进行解释。XCI不使用任何中间代码，如GCC中使用的Java字节码或RTLXCI会遍历AST进行解释。这个特性对于开发CASE工具来说是最好的，因为运行状态和AST之间的对应关系很清楚，而中间代码往往太低级而无法将它们联系起来。变量vm.pc是XCI中的程序计数器，其类型为结构PC：intmain（）函数{<联系我们...结构PC{structAST *ast;/* 执行中的AST节点 */int nth; /*从哪里来*/}pc;贡多42#defineGO_PANTION（）（vm.pc.nth=vm.pc.ast->第n+1，vm.pc.ast = vm.pc.ast->parent）#define GO_CHILD（i）（vm.pc.nth = 0，vm.pc.ast= vm.pc.ast->u.child[（i）]）\\fieldast指向正在执行的AST节点。字段nth保存访问当前节点之前的最后一个节点的信息：0表示父节点，i（i> 0）表示第i个 子节点（child[i-1]）。下面的宏是为AST遍历定义的：GO PANEL（）用于返回到父对象，GOCHILD（i）用于访问子对象[i]。下面的代码片段是XCI中eval block. c文件的一部分，它解释while语句。public void run（vm.pc.ast->ast_type）{...caseAST_iteration_statement_while：public void run（vm.nth）{case 0：/* from the parent */例2：/* 从子[1]*/eval_exp（vm.pc.ast->u.child[0]）;if（vm.pop_i（））returngetName（）;破碎;case 1：/* falling through*/ default：assert破碎;...}}控件中的内部语句（child[1]）语句（参见图3），只要表达式（child[0]）的评估值非零。如果内部语句有更多的内部状态，则可以将控制传递给它们。当child[0]的结果值变为零时，控制传递给父节点。这只是while语句的语义。5初步实验-使用ACML实现Weiser为了展示ACML对于软件切片的有用性，我们实现了Weiser的静态程序切片器，Weiser贡多43--儿童[0]母情况0：情况2：儿童[1]表达声明图3.第三章。while语句中的AST遍历在本节中，我们将详细解释实验，然后讨论在实验中获得的一些经验。5.1Weiser程序片是M.Weiser [24]，是程序的一部分，（潜在地）对在某个感兴趣的点计算的值进行切片，称为切片标准。切片准则是（n，V），一对行号和感兴趣的变量。无论何时执行语句n，Slice都会像原始程序一样计算V中变量的值程序切片已被证明有助于调试、测试、软件理解和影响分析等。因此，已经针对具有过程调用、任意控制流、复合数据库、指针和进程间通信（例如，[22]中的[23]在我们的实验中，为了简单起见，我们基于Weiser的切片算法实现了一个简单的切片器• 没有过程调用（只有主函数）• 没有复合数据集，没有指针（只有int）• 除了if-else和while之外，没有控制流语句• 没有系统调用，除了fgec6和printf之外没有库函数图4显示了一个切片的例子，其中省略了声明以节省空间。原始程序（图）4（a））对来自标准输入的文本的行数（nl）、单词数（nw）和字符数（nc）进行图图4（b）示出了标准（18，n1）上的节目切片。不检查nl切片计算变量nl的值与原始程序相同。6在当前的实现中，ACML不能处理带有预处理的像#include或#define这样的指令;所有程序在用gcc-E命令预处理后都用ACML标记。所以我们不能在这里使用像getchar这样的C宏库，因为它们在用ACML标记之前就被扩展了。语句（while）贡多44→→/→/→1 iw =0; /*一句话*/25689161718nl= 0;c= fgec（stdin）;while（c！= ）{if（c==Cintn（int n）;}printf（“%d\n”）;2 nl= 0;3 return0;4 nc =0;5 Cintn（int n）;6 while（c！ ）{7nc = nc +18if（c=='\n'）9nl= nl+ 1;10public void run（）{11return0;12}elseif（iw== 0）{13int sum =1;14nw = nw +1;15}16Cintn（int n）;17 }18 printf（“%d\n”）;19 printf（“%d\n”）;20 printf（“%d\n”，nc）;(a) 原始程序(b) 切片标准（18，{nl}）图四、切片的例子在Weiser非正式地，数据流和控制流依赖性定义如下。[24][22] [23][24][25][26][27][28][29• 数据流依赖语句j是依赖于语句i的数据流，在本文中用idj表示，如果存在变量v，使得v在i处被赋值，并且在j处被引用，而没有对v的中间赋值。1 x = 10;2 y = 20;3x = 0;4a = b;5z = y;例如，在上面的程序中，3→d 5（这意味着语句5是数据流依赖于3），1d 3，但4d 5和2d 5。声明5不是依赖于2的数据流，因为赋值语句3到y介于2和5之间换句话说，在2处分配给y的值20贡多45→→→12345i=0;while（i> 0）{x =1;i= i-1;}不会达到5。• 控制流依赖语句j是依赖于i的控制流，本文用icj表示，如果i可以选择执行j或不执行j。if（i）{2（3）x = 10;例如，在上面的程序中，语句2与控制流程相关一号线。 （1 →c2.）使用数据流（d）和控制流（c）依赖性，程序片S对于标准（n，V），定义如下：S=S∞{n}S0={i|（VDef（i）i→dn）i→cn}S k+1={i| <$j∈S k，i→dj<$i→cj}<$S k其中Def（i）表示在语句i中被赋值或修改的变量集合。直观地说，切片S通过逆向追踪两个关系→d和→c，在语句n处收集与变量V相关的所有语句。计算S在获得定点时终止，也就是说，当某个ks. t。Sk+1=K找到了。现在假设下面的代码。有以下6种依赖关系：2 →c3，2 →c4，1 →d2，1 →d4，4 →d2，4 →d4标准（3，{x}）上的切片是{1，2，3，4}，通过如下计算S0，S1和S2获得S0={ 2}，S1 ={ 1，2， 4}，S2 ={ 1，2， 4}，S =S2{ 3} ={ 1，2， 3， 4}5.2结果和讨论我们在5.1节描述的Java Weiser的切片器中进行了实验性的实现为了简洁地获取和处理抽象语法树，我们使用了JAXP [21]（Java API for XML Parsing）以及我们的XCI和ACML。执行大多是直接完成的。包括图4在内的几个示例工作完成。实现Weiser的切片器只花了0.5个人月，产生了2000行Java代码，而实现XCI的解析器和静态分析器却花了2.0个人月。通过使用XCI和ACML，我们不必重新实现ANSI C解析器和静态分析器，因此，粗略地说，贡多46ACML节省了2.0个人工月。实际上，我们发现我们的系统（XCI和ACML）和XML技术（如DOM）大大降低了开发切片器的成本。我们通过这次试验获得了宝贵的经验首先，我们再次认识到，我们需要通过开发许多应用程序（如Weiser的切片器的实现）来例如，我们发现ACML缺少一个属性上下文，它告诉节点之前有多少个兄弟节点，这对于树遍历非常方便，特别是对于树的上升。其次，我们发现需要为CASE工具构建可常用的类库，其中包括• 提取具有给定标识符的所有语句• 找到包含给定标识符的最内层语句DOM和DOM非常有用，但它们不能直接处理这些6相关作品• GraX [4]-GraX是一种基于图形的交换格式，用于交换软件再工程相关数据。GraX的具体表示法使用XML定义为grax.dtd。GraX的目的是为各种各样的软件对象提供一种通用格式。因此，GraX并不像ACML那样为ANSI C提供• SmartTools[1]和The Synthesizer Generator [8]-它们都是软件开发环境生成器。SmartTools与我们的工作更相关，因为SmartTools自动从DTD生成结构编辑环境，即SmartTools利用XML技术。与这些工作不同，我们专注于使用XML技术的ANSI C程序切片，以获得实际经验，如typedef名称问题。• 可移植的基于XML的源代码表示[29]-这项工作似乎只关注于AST的基于XML的源代码表示。与此不同，ACML也有静态语义信息。• 威斯康星程序切片工具[23]和解开程序切片工具[14]- 它们都是用C编写的用于切片ANSI C程序的工具。它们不使用XML技术。• 将语义添加到XML [19] -本文提出应用属性语法以声明的方式检查XML文档之间的语义一致性，例如，检查ACML中使用但未声明的变量。• Sapid [15]-对于给定的ANSI C源代码，Sapid将语法结构和静态语义的信息存储到文件中，格式为贡多47模特Sapid不使用XML，尽管Sapid正在尝试合并基于XML的特性。• JavaML（Java Markup Language，Java标记语言）试图独立于Java特定语法来建模Java编程语言这种抽象可以将各种面向对象的程序设计语言集成到一个统一的格式中。与JavaML不同，ACML紧密依赖于ANSI C语法，以最大限度地发挥ACML对ANSI C程序进行切片的能力。我们已经在2.2节中讨论了为编程语言设计标记语言JavaML和ACML之间的这种差异暗示了另一个困难：语法依赖的程度• GCC-XML [13]-GCC-XML从GCC的内部表示生成C或C++程序的XML描述不幸的是，GCC-XML的输出是粗粒度的，因此GCC-XML不适合我们的目的。7总结7.1结论在本文中，我们考虑了基于XML的ANSI C程序切片为了研究XML在程序切片中的作用，我们首先定义了ACML（ANSI C Markup Language），它可以描述抽象语法树和静态语义，如类型、符号等。在此基础上，我们实验性地实现了Weiser7.2未来的作品正如2.2节中所讨论的，有很多类型的信息要存储为XML文档。我们将扩展ACML以支持此类信息。特别是，我们计划研究以下内容：• 为动态程序切片器扩展ACML• 扩展ACML以支持其他类似的语言，如C++或Java，这是由GNU Global支持C，C++，Java和Yacc的事实所激励的。• 使用ACML开发其他CASE工具，如交叉引用器、程序浏览器（导航器）、测试用例生成器等。• 为了扩展ACML来描述预处理器指令，词法信息（例如，注释、编码样式）、系统调用和内联汇编代码。• 将ACML和XMI联系起来，以连接软件开发中的上游和下游• 减少ACML标记代码的大小以提高效率。贡多48确认作者要感谢片山拓哉，是他深深地启发了我们开始这项工作。作者还要感谢匿名的参考者，他们的宝贵意见改进了这篇论文。引用[1] Isabelle Attali ， Carine Courbis ， Pascal Degenne ， Alexandre Fau ， JoelFillon ， Didier Parigot ， Claude Pasquier ， and Claudio Sacerdoti Coen.SmartTools：一个基于XML技术的开发环境生成器 在proc XML技术和软件工程（XSE2001）（2001）。[2] 格雷格·J巴德罗斯JavaML：Java源代码的标记语言WWW9[10]计算机网络，33（1-6）（2000），159-177。http://www.cs.washington.edu/homes/gjb/JavaML/。[3] Tim Bray，Jean Paoli，C. M.斯珀伯格-麦奎因和伊芙·马勒可扩展标记语言（XML）1.0（第二版）。万维网联盟. http://www.w3.org/TR/REC-xml网站。[4] 尤尔根·埃伯特、伯恩特·库尔巴赫和安德烈亚斯·温特。GraX：一种再工程工具的交换格式。在Proc.6th Working Conf. on Reverse Engineering（WCRE[5] ECMA（欧洲计算机制造商协会）。便携式通用工具环境（PCTE）-抽象规范（1997）。ftp://ftp.ecma.ch/ecma-st/Ecma-149.pdf。[6] 电子工业协会CDIF技术委员会。CDIF CASE数据交换格式-概述，EIA/IS-106（1994）。 http://www.eigroup.org/cdif/。[7] K. Gondow和H. 川岛 XCI（Experimental ANSI CInterpreter） 日本高等科学技术研究所（JAIST）。http://www.jaist.ac.jp/~gondow/xci/。[8] GrammaTech，Inc.Ithaca，NY.合成器生成器，一个用于构建基于数据库的环境的系统。http://www.grammatech.com/products/sg/index.html。[9] IBM.XMLParserforJava（XML4J）.http://www.alphaworks.ibm.com/tech/xml4j.[10] XML SWG.RELAX（Regular Language Description for XML）http://www.xml.gr.jp/relax/。[1