《程序分析技术》

1、程序分析技术编辑ppt程序分析技术第一讲：程序设计语言的发展编辑ppt一、程序分析的任务以程序为对象，分析其属性，如： 值的获取与传播 活跃性 3编辑ppt二、程序分析技术的应用1. 程序转换2. 程序理解3. 程序演化4. 程序逆向工程4编辑ppt5. 程序验证与测试6. 程序优化7. 重构8. 自动并行化9. 5编辑ppt三、程序设计语言的发展6编辑ppt三、程序设计语言的发展机器语言指令： 二进制组成 具有基本操作，左移、右移、加1缺点： 可读性差（可理解性差） 写程序困难（不方便）问题：程序的维护比较困难 扩展 纠错 预防 适应7编辑ppt三、程序设计语言的发展汇编语言 符号化了的机器

2、语言 功能没有扩充 可读性强例：将(R4R5)中的双字节数取补，结果送R4R5。CMPT：MOV A，R5CPL AADD A，#1MOV R5，AMOV A，R4CPL AADDC A，#0MOV R4，ARET8编辑ppt三、程序设计语言的发展高级程序设计语言(1)过程式语言PASCAL,C,FORTRAN,PL1特点： 命令为基础，程序由一系列语句组成，语句的执行引起存储单元值的变化。 程序的正确型（归纳断言指导） 数学性质弱（副作用，变量值变化） 数据类型不够丰富 程序的动静态结构差异大9编辑ppt历史上的goto语句之争1970，XPL编译器只用了一个goto1972，操作系统只有五

3、处用了标号和goto 难以理解，难以查错，动静态差异大 修改引起的副作用小，全局优化简单 概念简单，效率高10编辑ppt三、程序设计语言的发展高级程序设计语言(2)函数式语言LISP,ML,HOPE,FP程序由一组函数组成，通过调用执行程序。特点： 数学性质好 数据类型可自定义 支持并行计算 抽象级别高 数据以表为基础11编辑ppt三、程序设计语言的发展高级程序设计语言(3)逻辑式语言 PROLOG 以谓词为基础，具有推理能力 特定的应用领域抽象的问题求解公式处理专家系统人工智能等12编辑ppt三、程序设计语言的发展高级程序设计语言(4)对象式语言SmallTalk80 特点： 封装性 继承性

4、 多态性13编辑ppt三、程序设计语言的发展第四代语言特定领域的特殊类语言高级语言的抽象如：Oracle应用开发环境、Power Builder14编辑ppt四、程序分析的一般方法 静态分析方法 动态分析方法15编辑ppt 五、静态的分析过程 词法分析 语法分析 所需要的分析16编辑ppt程序分析技术第二讲编译原理基础编辑ppt大 纲 基本概念 正则表达式 自动机理论 文法概述 语法分析自顶向下自底向上18编辑ppt1 基本概念 字母表： ，元素的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列。或者如下定义：1.空符号串是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符

5、号串 3.y是上的符号串,当且仅当它可以由1和2导出19编辑ppt 符号串的连接：设x和y均是字母表上的符号串，它们的连接是把y的所有符号顺序接在x的符号之后所得到的符号串。 符号串的方幂：设x是字母表上的符号串，把x自身连接n次得到的符号串z, 称作符号串x的n次幂，记作 z=xn ，特别地：x0= 前缀和后缀：设x是字母表上的符号串，x=yz ,则y是x 的前缀，z 是x的后缀，特别是当z时，y是x的真前缀；y时，z是x的真后缀。 子字符串：非空字符串 x ,删去它的前缀和后缀后所得到的字符串称为 x 的子字符串，简称子串。如果删去的前缀和后缀不同时为,则称该子串为真子串。20编辑ppt

6、符号串集合：若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 符号串集合的乘积：设A、B 是两个符号串集合，AB表示A与B的乘积，则定义AB=xy|(xA)(yB) 符号串集合的方幂：设A是符号串集合，则称Ai 是符号串集合 A的方幂，其中i 是非负整数。A0=, A1=A, A2=AA, , An=AA A 符号串集合的正闭包：A+=A1A2A3 符号串集合的星闭包：A*= A0A1A2A3 21编辑ppt2 正则表达式 定义：RE为定义在上的正则表达式则,RE若a，则aRE若e1,e2RE，则e1e2,e1|e2,e1+RE 语义函数（解释函数）L L()=，L

7、()=若a 则L(a)=a若e1,e2RE则L(e1e2)= L(e1)L(e2) L(e1|e2)= L(e1)L(e2) L(e1+)= L+(e1)22编辑ppt实例 = a,b 23正则表达式正则表达式e e1.1. abab* *2. a(a|b)2. a(a|b)* * L(e)L(e)1.1. 上所有以上所有以a a为首后跟任意多为首后跟任意多个（包括个（包括0 0个）个）b b的字符串集的字符串集2.2. 上所有以上所有以a a为首的字符串集为首的字符串集编辑ppt3 自动机 定义：一个DFA是一个5元组(S,S0,F)，其中S是状态集合，是字符集，是转换函数（转移函数）SS

8、，S0为初始状态S0S，F为终止状态集合，FS。 两种表示形式转换图转换矩阵24编辑ppt3.1 自动机实例确定有限状态自动机 M=(a, b,S, U, V, Q, f, S, Q)，其中f定义为：f (S, a)=Uf (V, a)=Uf (S, b)=Vf (V, b)=Qf (U, a)=Qf (Q, a)=Qf (U, b)=Vf (Q, b)=Q25编辑ppt两种表示形式SU V QaU Q U QbV V Q Q26SUQVaaaabbbb编辑ppt 3.2 词法分析 功能：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示，同时检查源程序中的词法错误。 单词：所谓单词是指语

9、言中具有独立含义的最小的语义单位。 Token：单词的内部表示。“程序语言的操作对象（只能）是该语言规定的各种数据。”编译程序是用某种程序语言书写的程序，其操作对象是一般程序中的各种语法单位。 27编辑ppt单词的一种分类方法单词单词标识符标识符X1，classT常量常量10，LENGTH特殊符号特殊符号保留字保留字while，int运算符运算符+，界限符界限符，；，；格式符格式符EOF， 28编辑ppt识别常数的自动机29ABE+数字数字-数字数字数字数字C数字数字D小数点小数点数字数字注：未考虑前导注：未考虑前导0的情形的情形编辑ppt4 文法概述 文法能清晰地描述程序设计语言的语法构成，

10、易于理解。 文法能构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。 文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码及检查出语法错误。 基于文法实现的语言易于扩展30编辑ppt 文法定义文法G定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式：，其中，(VTVN)*31编辑ppt 文法分类 O型文法：也称为短语文法，其产生式具有形式: ，其中,(VTVN)*，并且至少含一个非终极符 。 1型文法：也称为上下文相关文法。它是0型文法的特例，要求| | (S例外，但S不得出现于产

11、生式右部)。 2型文法：也称为上下文无关文法。它是1型文法的特例，即要求产生式左部是一个非终极符: A 。 3型文法：也称为正则文法。它是2型文法的特例，即产生式的右部至多有两个符号，而且具有下面形式之一: A a ，A a B其中A,BVN ，aVT 。 32编辑ppt 上下文无关文法定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式：AX1X2Xn 其中AVN，Xi(VTVN) ，右部可空。33编辑ppt 文法相关概念 推导（直接推导）：如果A是一个产生式，则有A ,其中表示一步推导(用A )。这时

12、称是由A直接推导的。 的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。 + : 表示通过一步或多步可推导出 * : 表示通过0步或多步可推导出 34编辑ppt 句型：如果有S* ，则称符号串为CFG的句型 。我们用SF(G)表示文法G的所有句型的集合。 句子：如果只包含终极符，则称为CFG的句子。 语言：L(G)= u| S + u ,u VT* 文法G所定义的语言是其开始符所能推导的所有终极符号串(句子)的集合。 35编辑ppt 最左（右）推导：如果进行推导时选择的是句型中的最左(右）非终极符，则称这种推导为最左(右)推导，并用符号lm（rm）表示最左（右）推导。 左（右）句型

13、：用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型(规范句型)。结论：每个句子都有相应的最右和最左推导（但对句型此结论不成立） 36编辑ppt 短语：设S是文法的开始符，是句型(即有S *），如果满足条件：S* AA+ VT+ 则称是句型的一个短语。 任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语。 直接短语（简单短语）：如果满足条件：S* AA VT+ 则称是句型的一个简单短语。 任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语。 句柄：一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。 37编辑ppt 语法分析树(简称分析树)用

14、来描述句型的结构，是句型推导的一种树型表示。文法 G=(VN,VT,S,P)，则称满足下面条件的树为G的一棵语法分析树：1. 每个结点都有G的一个文法符号，并且根结点标有初始符S，非叶结点标有非终极符，叶结点标有终极符或非终极符或。2. 如果一个非叶结点A有n个儿子结点(从左到右）为 X1,X2,.,Xn，则G一定有产生式 AX1X2 .Xn 。38编辑ppt 线性推导：我们称用符号进行的推导为线性推导 。 树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树(如果无二义性)，而线性推导则可以有很多棵分析树。 二义性文法：如果一个文法

15、的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。例：文法G=( +,*,i,(,), E, E, P),其中P为：E iE E + EE E * EE ( E )39编辑ppt句型句型i*i+i 可能的推导可能的推导:推导推导1: E E + E E * E + E i * E + E i * i + E i * i + i推导推导2: E E * E i * E i * E + E i * i + E i * i + i推导推导1的语法树的语法树E+EEE*EiiiEE*EE+Eii推导推导2的语法树的语法树i40编辑ppt5 语法分析 分类 自顶向下 递归下降法 LL（1）

16、方法 自底向上 简单优先方法 LR（0）方法 SLR（1）方法 LR（1）方法 LALR（1）方法41编辑ppt 自顶向下分析基本思想 从文法开始符出发试图推导出所给的终极符串。例 Gz :1Z aBd2 B d3 B c4 B bBZ Za aB Bd db bB Bc c42编辑ppt aBd # abcd # aBd # abcd # MatchMatch Bd # bcd # Bd # bcd # DerivationDerivation bBd # bcd # bBd # bcd # MatchMatch Bd # cd # Bd # cd # DerivationDerivatio

17、n cd # cd # cd # cd # MatchMatch d # d # d # d # MatchMatch # # Success # # Success自顶向下的语法分析过程【自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】 Z # abcd # DerivationZ # abcd # Derivation自顶向下分析实例43编辑ppt自下而上Sa A c B eA bdb 自底向上语法分析思想：从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归

18、约为文法的开始符。(移入-归约分析)编辑ppt例：SaAcBe 1A b 2A Ab 3B d 4 输入流：abbcde。 规范推导过程为： 逆过程逆过程:(:(符号栈，输入流符号栈，输入流) )(-, abbcde)(-, abbcde)(a,bbcde)(a,bbcde)(a(ab b,bcde) ,bcde) (aA,bcde)(aA,bcde)(a(aAbAb,cde),cde)(aA,cde)(aA,cde)(aAc,de)(aAc,de)(aAc(aAcd d,e),e)(aAcB,e)(aAcB,e)( (aAcBeaAcBe,-),-)(S,-)(S,-) S S aAcBea

19、AcBe11 aAc aAcd d44e e11 a aAbAb33cdcd44e e11 a ab b22b b33cdcd44e e11编辑ppt程序分析技术第三讲：元 程 序 设 计编辑ppt一、基础知识词法分析1. 基本概念2. 描述工具1) 正则表达式2) 自动机3. 实现词法分析器注意的问题47编辑ppt语法分析1. 形式语言2. 分析原来1) 自顶向下的语法分析2) 自底向上的语法分析语法制导分析的过程生成中间表示48编辑ppt二、元程序 元程序概念处理程序的程序 元程序系统的组成：1.预处理：把源程序变成一种中间表示（经过词法分析，语法分析）2.元级操作：提供最基本的操作（根据

20、需求，用户可选择如何操作）3.后处理：有必要把中间表示转为源代码49编辑ppt三、中间表示 四元式: (op,a,b,t) 例 a*(b+c)+d (+,b,c,t1)，(*,a,t1,t2)，(+,t2,d,t3) 逆波兰式: 后缀式 上例 abc+*d+ 树 上例50+ +* *d da a+ +b bc c编辑ppt四、规则分类和对应的结构1.结构规则（构造规则）A X1X2Xn2.选择规则A X1|X2|Xn是结构规则的特例，因为每次只能用一个规则51AX1X2Xn编辑ppt3. 表规则 A E|E,A(也可左递归)构造双向链表操作更方便4. 词汇规则 A lex52t1At2E1t3

21、E2t4E3编辑ppt实例while x0 doif y0 then x:=x+1else y:=y+153whileifc0vyc0thenelse:=vxc1+vxvx编辑ppt五、元级操作1.低级元操作1)类型识别操作 给结点的类型 判定结点是否为给定的类型 空结点定位2)成份选择操作 选择某一结点（满足条件） 表元素的选择54编辑ppt3)构造操作 按某一结构构造结点。4)关系操作 给定两结点，判断它们的关系。 给定结点和关系，判断是否存在结点。5)编辑操作 插入，删除，查找，修改6)词汇强制2. 高级元级操作可根据特定的需要，构造许多特殊的高级操作。如：控制流图，函数调用关系图等55

22、编辑ppt六、系统的自动生成 利用语法制导的方法生成 系统由两部分组成生成中间表示部分元级操作部分（可事先设计好）56编辑ppt按照 AX1Xn 归约时状态为Xi的结点已经构造好文法，结点指针未填规约后，Xi结点指针添加，A结点指针均空Xi退栈A进栈57Xn.X1d Sem栈编辑ppt程序分析技术第四讲：数据流分析技术编辑ppt一、概述数据流分析技术是对源程序分析、获取程序中变量定值和传播的情况，帮助理解程序中的数据流动情况编辑ppt二、基本概念定义一、基本块是一个顺序执行的命令序列。进入一个基本块，必须从第一条命令进入，退出基本块，必须由最后一条命令退出。特点：后续执行情况可判断。编辑ppt

23、定义二、程序图是一个有向图，它的结点为基本块，有一个入口结点（无前驱结点）和一个出口结点（无后续结点）扩展：程序图有三种表示（常用的） 流程图 N-S图 PAD图编辑ppt定义三、定值在基本块当中，若有d: x:=e,则称有对x的定值，d: 为 x的定值点。（注：d:为程序中引入的标识，对程序无影响）定义四、注销若有对变量x的赋值x:=,则程序注销了x的原定值。用killB表示B中被注销的所有变量之集。编辑ppt定义五、向下暴露的定值设（Bi,di） 为x的一个定值，若从di+1到Bi的出口再无对x的定值，则称x的di的定值为向下暴露的定值，并用defBi表示Bi中的所有向下暴露定值的变量之集

24、。编辑ppt定义六、可能到达的定值 说在（Bi,di）点x定值可能到达 （Bj,dj）点 ，若从（Bi,di）存在一条路，且在该路上无x的定值。编辑ppt可到达的定值数据流方程inB*=，B*为入口块。；outB=defB (in(B)-kill(B) )inB = (outBi) i=1,2,n；Bi为B的前驱结点其中inB表示在B入口处有定值的变量之集outB表示定值可到达B出口处的变量定值之集编辑ppt编辑ppt inB1 = outB1 = d2，d3 inB2 = d2,d3,d7 outB2 = d2,d4,d5,d7 inB3 = d2,d4,d5,d7 outB3 = d2,d

25、4,d5,d6,d7 inB4 = d2,d4,d5,d7 outB4 = d4,d5,d7 inB5 = d2,d4,d5,d6,d7 outB5 = d2,d4,d5,d7,d8,d9编辑ppt定义七、定义性出现，使用性出现 称第一次出现在赋值命令左部的变量出现（即x:=第一次出现）为变量（x）的定义性出现，而称其他部位中的变量出现为其使用性出现编辑ppt定义八、向上暴露的使用 在(Bi,di)有x的使用性出现，若从Bi的入口到di-1点无对x的赋值。则称x在(Bi,di)点的出现为向上暴露的使用，用use_liveB表示B中所有向上暴露的使用编辑ppt定义九、变量的活跃性说变量x在（Bi

26、,di）点活跃，若：1.存在一点（Bj,dj）有x的使用性出现。2.从（Bi,di)到（Bj,dj)存在一条通路，且在该路上无对x的定值。定义十、注销活跃性若在某一点（Bk,dk) 有X:=，则称注销X的活跃性编辑ppt活跃变量的数据流方程in_liveB=use_liveB(out_liveB- kill_liveB)out_liveB= in_liveBi Bi为B的后续out_liveB*= B*为出口块其中in_liveB=x|x在B入口处活跃out_liveB=x|x在B出口处活跃use_liveB=x|B中所有局部向上暴露使用的变量kill_liveB=x|B注销其活跃性的变量。编

27、辑ppt定义十一、过程调用块 把过程调用P(e1,en)定义为一个独立的基本块，称为过程调用块 。定义十二、过程的返回块 调用块的接续为返回块（或return的后续块）难点：1. 下标变量的分析2. 别名问题编辑ppt程序分析技术第五讲：数据流分析技术应用编辑ppt一、检测数据流异常1.数据流异常情况：1)变量无定值而使用；2)变量重复定值；3)变量定值无使用。编辑ppt检测方法（a）in_dB:表示在B入口处所有定值的变量之集；out_dB:表示B在出口处所有定值的变量之集；def_dB:表示B中所有定值的变量之集。编辑ppt数据流方程（a）in_dB*= B*为入口块in_dB =（或）i

28、=1,2n(out_dBi)Bi为B的前驱块out_dB=def_dBin_dB编辑ppt数据流方程（a）结论：若in_liveBin_dB，则必有变量无定值而使用;特例：若in_liveB*，则必有变量无定值而使用.编辑ppt检测方法（b）in_ddBi: 表示块B入口处所有定值而未使用的变 量之集；out_ddBi:表示块B出口处所有定值而未使用的变量之集；def_dd1Bi=x|x在（B,di）点定值，且从（B,d1）. （B,di）无x的使用性出现。def_dd2Bi=x|x在（B,di）点定值，且从（B,di+1）到B出口，无x的使用性出现。编辑ppt数据流方程（b）in_ddB*=

29、 B*为入口块 in_ddB=（或）out_ddB out_ddB=def_dd2B(in_ddB-useB)编辑ppt数据流方程（b）结论：1.若in_ddBdef_dd1B，则有变量重复定值；若in_ddB-in_liveBi，则有变量定值而未使用，或重复定值。2.若out_ddB*， B*为出口块,则有变量定值而未使用。编辑ppt程序优化：全局常表达式节省基本块的常表达式节省问题：利用的信息不充分vvvl编辑ppt 定义：常量定值若在块B中有x:=c，其中c是常数,且该定值是向下暴露的，则称x有一个常量定值，记为xc。 定义： 注销常量定值若有x:=E，则称注销了x的常量定值。解决办法编

30、辑ppt 定义： 广义常量定值若块B中有向下暴露的定值x:=E，且 E的值可计算为一个常量c，则称产生一个广义常量定值xc。 定义： 注销广义常量定值若有x= 则称注销了广义常量定值编辑ppt数据流方程in_acB0= B0为入口块in_acBi=j=1,2,n out_acBj,Bj为Bi的前驱out_acBi=def_acBi(in_acBi-kill_acBi)编辑ppt优化过程 建立数据流方程 求解 对每一基本块进入优化把in-ac(B)填入vvl按原方法优化编辑ppt编辑pptin-acB1 = out-acB1 = x.1,y.2in-acB2 = x.1,y.2out-acB2

31、= x.1,y.2,z.3,b.4in-acB3 = x.1,y.2 out-acB3 = x.1,y.2,z.3,b.4in-acB4 = x.1,y.2,z.3,b.4 out-acB4 = x.1,y.2,z.3,b.4,k.7,u.9,r.16 编辑ppt程序优化：公共子表达式节省 定义：表达式定值在块B中，若有d: x:=E，则称有表达式E的定值，d为定值点若从di+1到B的出口没有对表达式E中变量的赋值，则称B定值了表达式E 定义:注销表达式定值若有 x:=E,且x出现在表达式E中，注销了E的定值。编辑ppt数据流方程in_eB0 = B0为入口块out_eBi = def_eBi

32、(in_eBi-kill_eBi) in_eBi = Bj pre(Bi)out_eBj Bj为Bi的前驱编辑ppt编辑ppt需要注意的两个问题 形式相同的表达式未必能节省（已解决） 形式不同的表达式也可能节省（未解决）编辑ppt 定义：等式定值 在块B中，若有x:=y。且从di+1到B出口无对x或y的赋值，则称B有了一个等式定值。即x=yl 定义：注销等式定值 若有对x的赋值x:=，则称注销了所有x的等式定值。 编辑ppt数据流方程in_eqB0 = B0为入口块out_eqBi = def_eqBi(in_eqBi-kill_eqBi)in_eqBi = Bj pre(Bi)out_eqB

33、j 编辑ppt 利用等式定值和表达式定值，可以解决形式不相同但语义相同的表达式节省问题。 例如： X:=A*B1 C:=A2 Y:=C*B3 由2可知13等价编辑ppt程序分析技术第六讲：一种信息流分析技术编辑ppt一、处理的语言S-skip|V:=e|If e then s else s|If e then s |s; s|While e do s选择的原因：结果定理编辑ppte1S1S2S3S4e2编辑ppt二、基本方法1. 结构图S3S4e1S1S2e1S1编辑ppt2.基本定义定义：设S为一个语句，若在S中有V:=e,一则称S定义了v。用Ds表示S定义的所有变量之集。设S为一个语句，从

34、G(S)入口到G(S)出口存在一条路，且在该路上无对变量x的赋值，则称S保护了x。用Ps表示S保护的所有变量之集。编辑ppt定义：变量与表达式的关系若变量v在G(S)入口处值，直接或间接参与了表达式e的计算，则说v和e具有关系，记为vS e或者(v, e) S。定义：表达式与变量的关系若表达式e直接或间接参加变量v在G(S)出口处值的计算，则称e和v具有关系，记为eS v或者(e, v) S。编辑ppt定义：变量与变量的关系S = SS (v, v) | vPS解释，v1Sv2，v在G(S)的入口值参与v2在G(S2)出口值的计算。v1Sv2，v1在G(S)的入口值可？ G(S)的出口编辑pp

35、t3.计算方法空语句 S：skip;Ds = , ps= Vs =,s = ps = (v, v) | vps赋值语句S：v := e;DS = v,PS= V- vS = (v, e) | vV (e), S = (e, v)S = (v, v) | vuse (e) (v, v)| v PS编辑ppt顺序语句S：A;BDS= DA DB, PS= PA PBS = A AB,S = ABBS = AB条件语句S：if e then A else BDS= DA DB,PS= PA PBS = (v, e)| v use(e) A B S = AB (e, v)| v (DA DB)S =

36、AB (v, v)| v use(e)，vDA DB) 编辑ppt简单条件语句s：if e then Aelse部分为skip可用上述规则计算。循环语句S：while e do ADS= DA, PS= VS =A* (v, e)| v use (e)A)S = (e, v)| v DAA)A* S = 公式计算编辑ppt三、应用1.看某一输入变量对那些输出变量有影响设vVi，v”Vo，若(v，v” ) 成立，则v 对v ”有影响。影响集（v ，v ”）v ”Vo， (v ，v ”) 编辑ppt2.看那些输入变量对某些输出变量的影响给定vv” ，v| (v，v ”) vv” 被影响集对v ”

37、有影响编辑ppt3.无用的输入变量若输入变量影响的输出变量集为空，则该输入变量对程序的运行结果无影响。4.无效语句v:=e， (e, v)|vVo=，则该语句可用skip替换或含有错误。编辑ppt5.对循环语句的分析设有while e do A，定义一个G(S),点集为DA，边集为A编辑ppt定义：稳定变量在G(S),中，如果任一环路上的变量都没有列该变量的路，则称该变量是关于S稳定的例：while e doX:=y+1;Y:=z+1;Z:=k+1;K:=m+1.kxyz编辑ppt若循环体为x:=y+1;y:=z+1;z:=k+1; k:=m+1定义：稳定变量的稳定长度设v是关于S稳定的，终止

38、于v的最长路径长度称为v的稳定长度，记为(v)。xyzk编辑ppt例while e dox:=y+z;y:=z+1;z:=k+1; (x)=2 定义：稳定表达式设e是循环语句s中的一个表达式，若use(e)中的变量都是稳定的，则称e是稳定的。xyz编辑ppt定义：稳定表达式e的稳定长度设e是关于s稳定的，其稳定长度用(e)表示。定义如下：(e) =max(v) |vuse(e)+1。 编辑ppt结论：任意一个稳定变量，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。任意一个稳定表达式，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。若while e do A中的e是稳定的，很有可能出错（陷入死循环）。编辑ppt应用：可根据上述分析结果，进行应用。例如：部分求值的程序例化（循环展