目标独立的Prolog程序路径依赖分析语义_赵岭忠

计算机科学2008Vol 35 2

目标独立的Prolog程序路径依赖分析语义*

)

赵岭忠1,2 古天龙2 钱俊彦2

12

(西安电子科技大学电子工程学院 西安710071) (桂林电子科技大学计算机与控制学院 桂林541004)

摘 要 在Prolog程序分析中,考虑程序的执行路径和非逻辑的cut操作可提高程序分析的精度。当前用于Prolog程序路径依赖分析的语义因依赖于程序执行的目标而不适合目标独立的程序分析。为此,本文采用了一种携带路径信息并允许cut操作的Prolog抽象语法,在此基础上给出了Prolog的操作语义和一种目标独立的标号树(LT)语义,并证明了LT语义相对于操作语义的正确性。LT语义可作为目标独立的Prolog程序路径依赖分析的基础。关键词 程序分析,Prolog语义,目标独立,上下文信息,抽象解释

Goal independentSemanticsforPathDependentAnalysisofPrologPrograms

ZHAOLing Zhong1,2 GUTian Long2 QIANJun Yan2

(ElectronicEngineeringSchool,XidianUniversity,Xi an710071)1

(SchoolofComputerandControl,GuilinUniversityofElectronicTechnology,Guilin541004)2

Abstract ConsideringtheexecutionpathandcutoperatorsofaPrologprogramcanimprovetheprecisionofprogram

analysis.KnownsemanticsforPrologeithermakesuseoflimitedamountofpathinformationandhenceleadstolesspreciseanalysisorisgoal dependentandthereforenotsuitableforgoal independentprogramanalysis.Thispaperdealswiththeproblemsbyproposingagoal independentlabeledtreesemanticsforPrologwithcut,whichmakesitpossibletousecallstringsascontextinformationtoimprovePrologprogramanalysis.Thissemanticsisshowntobecorrectw.r.ttheoperationalsemanticspresentedinthispaper.

Keywords Programanalysis,Prologsemantics,Goal independence,Contextinformation,Abstractinterpretation

上下文信息有两种,一种是调用串(callstrings),记录过程调

用发生的轨迹;另一种是前提集(assumptionset),记录调用发生时的程序状态[20]。在逻辑程序的分析中通常使用后者,如文[8,13]中的自顶向下语义隐式地使用部分解作为程序的上下文信息。在逻辑程序中目标的部分解是在该目标的SLD 消解过程中任意中间步骤上获得的中间结果,可视为逻辑程序执行的中间状态。文[18,24]中的指称语义虽然利用了程序的调用路径信息,但信息量有限。L.Lu首次把调用串作为上下文信息用于改善逻辑程序的分析[17]。本文把利用调用串信息的程序分析称为路径依赖分析。

逻辑程序分析可分为目标独立和目标依赖两种类型。目标依赖分析用于分析与特定目标相关的程序性质,通常基于程序的操作语义;目标独立分析则用于分析对任意目标均适用的程序性质,常基于目标独立的指称语义[21]。由于目标独立分析可在一次分析中提供任意目标的分析结果,因而尤其适用于需针对多个目标对同一程序进行优化的情况。

为了在抽象解释的框架内对具有cut操作的Prolog程序进行目标独立的分析,同时采用调用串改善分析的结果,需要一种能够完整描述Prolog程序执行过程中目标消解的路径信息并具有目标独立特性的Prolog具体语义。根据现有文献,没有任何一种现有Prolog语义可同时满足以上分析要求。为此本文采用了一种新的Prolog抽象语法,其中过程定义中每一个文字(literal)的入口和出口均由数字标号标明。

1 引言

程序分析是自动分析计算机程序行为的过程,其结果可作为编译器或部分求值器(partialevaluator)的输入用于程序的优化。目前程序分析常采用基于抽象解释的方法[7]。程序P的抽象解释可视为P在非标准语义域上的一次运行,其中非标准语义域刻画了分析人员所关注的程序特性C。利用抽象解释对程序进行分析通常包括如下几个步骤:

1)构造能完整描述程序特性C的语义域D以及相应的语义S,该语义被称作具体语义。具体语义可以是操作语义也可以是指称语义,但不要求该语义对任意程序是有限可计算的。

2)建立抽象语义域D#以及基于D#的抽象语义S#,其中D#是D的近似。通常D#为有限域,以保证抽象语义的有效可计算性;否则必须为S#设计能够保证语义计算收敛的语义运算符。

3)实现基于语义S#的程序分析器。架

[1~10,13~16,19,21,22]

目前已存在多种分析Prolog程序的抽象解释框

,其中文[2,8,13,14,16,21,22]提出的语

义能够处理Prolog程序的cut操作并考虑其深度优先的搜索规则,从而提高了程序分析的精度。除此之外,考虑程序中过程调用的上下文信息也可提高程序分析的精度,该方法已广泛应用于包含过程调用的命令式语言程序的分析中。常用的

*)基金项目:国家自然科学基金(60563005,60663005)和广西青年科学基金(桂科青0728093,0542036)。赵岭忠 博士生,研究方向:软件工程,形式化技术等;古天龙 教授,博士生导师,研究方向:实时混杂系统理论,协议验证,形式化方法等;钱俊彦 副教授,研究方向:模型检验,嵌入式实时系统。

Word文档免费下载Word文档免费下载:目标独立的Prolog程序路径依赖分析语义_赵岭忠 (共8页,当前第1页)

目标独立的Prolog程序路径依赖分析语义_赵岭忠相关文档

最新文档

返回顶部