《程序分析技术》PPT课件

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

2、R4R5。 CMPT：MOV A，R5 CPL A ADD A，#1 MOV R5，A MOV A，R4 CPL A ADDC A，#0 MOV R4，A RET,8,三、程序设计语言的发展高级程序设计语言,(1)过程式语言 PASCAL,C,FORTRAN,PL1 特点： 命令为基础，程序由一系列语句组成，语句的执行引起存储单元值的变化。 程序的正确型（归纳断言指导） 数学性质弱（副作用，变量值变化） 数据类型不够丰富 程序的动静态结构差异大,9,历史上的goto语句之争,1970，XPL编译器只用了一个goto 1972，操作系统只有五处用了标号和goto 难以理解，难以查错，动静态差异大

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

4、的特殊类语言 高级语言的抽象 如：Oracle应用开发环境、Power Builder,14,四、程序分析的一般方法,静态分析方法 动态分析方法,15,五、静态的分析过程,词法分析 语法分析 所需要的分析,16,程序分析技术,第二讲 编译原理基础,大 纲,基本概念 正则表达式 自动机理论 文法概述 语法分析 自顶向下 自底向上,18,1 基本概念,字母表： ，元素的非空有穷集合。 符号串：由字母表中的符号组成的任何有穷序列。或者如下定义： 空符号串是上的符号串 若x是上的符号串,a是的元素,则xa是上的符号串 y是上的符号串,当且仅当它可以由1和2导出,19,符号串的连接：设x和y均是字母表上

5、的符号串，它们的连接是把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,符号串集合：若集合A中的所有元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 符号串集合的乘积：设

6、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,2 正则表达式,定义：RE为定义在上的正则表达式则 ,RE 若a，则aRE 若e1,e2RE，则e1e2,e1|e2,e1+RE 语义函数（解释函数）L L()=，L()= 若a 则L(a)=a 若e1,e2RE则L(e1e2)= L(e1)L(e2) L(e1|e2)=

7、 L(e1)L(e2) L(e1+)= L+(e1),22,实例,= a,b ,23,3 自动机,定义：一个DFA是一个5元组(S,S0,F)，其中S是状态集合，是字符集，是转换函数（转移函数）SS ，S0为初始状态S0S，F为终止状态集合，FS。 两种表示形式 转换图 转换矩阵,24,3.1 自动机实例,确定有限状态自动机 M=(a, b, S, U, V, Q, f, S, Q)，其中f定义为： f (S, a)=Uf (V, a)=U f (S, b)=Vf (V, b)=Q f (U, a)=Qf (Q, a)=Q f (U, b)=Vf (Q, b)=Q,25,两种表示形式,26,S

8、,U,Q,V,a,a,a,a,b,b,b,b,3.2 词法分析,功能：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示，同时检查源程序中的词法错误。 单词：所谓单词是指语言中具有独立含义的最小的语义单位。 Token：单词的内部表示。“程序语言的操作对象（只能）是该语言规定的各种数据。”编译程序是用某种程序语言书写的程序，其操作对象是一般程序中的各种语法单位。,27,单词的一种分类方法,28,识别常数的自动机,29,A,B,+,数字,-,数字,数字,数字,D,小数点,数字,注：未考虑前导0的情形,4 文法概述,文法能清晰地描述程序设计语言的语法构成，易于理解。 文法能构造有效的语法分析器

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

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

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

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

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

14、+,*,i,(,), E, E, P),其中P为： E iE E + E E E * EE ( E ),39,句型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,40,5 语法分析,分类 自顶向下 递归下降法 LL（1）方法 自底向上 简单优先方法 LR（0）方法 SLR（1）方法 LR（1）方法 LALR（1）方法,41,5.1 自顶向下分析基本思想,从文法开始符出发试图推导出所给的终极符串。 例 Gz : 1Z

15、 aBd 2 B d 3 B c 4 B bB,42,aBd # abcd # Match Bd # bcd # Derivation bBd # bcd # Match Bd # cd # Derivation cd # cd # Match d # d # Match # # Success,自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】 Z # abcd # Derivation,自顶向下分析实例,43,自下而上,S a A c B e A bd b,5.2 自底向上语法分析,思想：从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的

16、句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符，直到将输入串归约为文法的开始符。(移入-归约分析),1.1例：SaAcBe 1 A b 2 A Ab 3 B d 4 输入流：abbcde。 规范推导过程为：,逆过程:(符号栈，输入流) (-, abbcde) (a,bbcde) (ab,bcde) (aA,bcde) (aAb,cde) (aA,cde) (aAc,de) (aAcd,e) (aAcB,e) (aAcBe,-) (S,-),S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1,程序分析技术,第三讲： 元 程 序 设 计,一、基础知识,词法

17、分析 基本概念 描述工具 正则表达式 自动机 实现词法分析器注意的问题,47,语法分析 形式语言 分析原来 自顶向下的语法分析 自底向上的语法分析 语法制导 分析的过程生成中间表示,48,二、元程序,元程序概念 处理程序的程序 元程序系统的组成： 预处理：把源程序变成一种中间表示（经过词法分析，语法分析） 元级操作：提供最基本的操作（根据需求，用户可选择如何操作） 后处理：有必要把中间表示转为源代码,49,三、中间表示,四元式: (op,a,b,t) 例 a*(b+c)+d (+,b,c,t1)，(*,a,t1,t2)，(+,t2,d,t3) 逆波兰式: 后缀式 上例 abc+*d+ 树 上例

18、,50,四、规则分类和对应的结构,结构规则（构造规则） A X1X2Xn 选择规则 A X1|X2|Xn 是结构规则的特例，因为每次只能用一个规则,51,X1X2Xn,表规则 A E|E,A(也可左递归) 构造双向链表操作更方便 词汇规则 A lex,52,实例,while x0 do if y0 then x:=x+1 else y:=y+1,53,五、元级操作,低级元操作 类型识别操作 给结点的类型 判定结点是否为给定的类型 空结点定位 成份选择操作 选择某一结点（满足条件） 表元素的选择,54,构造操作 按某一结构构造结点。 关系操作 给定两结点，判断它们的关系。 给定结点和关系，判断是

19、否存在结点。 编辑操作 插入，删除，查找，修改 词汇强制 高级元级操作 可根据特定的需要，构造许多特殊的高级操作。 如：控制流图，函数调用关系图等,55,六、系统的自动生成,利用语法制导的方法生成 系统由两部分组成 生成中间表示部分 元级操作部分（可事先设计好）,56,按照 AX1Xn 归约时 状态为 Xi的结点已经构造好文法，结点指针未填 规约后，Xi结点指针添加，A结点指针均空 Xi退栈 A进栈,57,d ,Sem栈,程序分析技术,第四讲： 数据流分析技术,一、概述,数据流分析技术是对源程序分析、获取程序中变量定值和传播的情况，帮助理解程序中的数据流动情况,二、基本概念,定义一、基本块 是

20、一个顺序执行的命令序列。进入一个基本块，必须从第一条命令进入，退出基本块，必须由最后一条命令退出。 特点：后续执行情况可判断。,定义二、程序图 是一个有向图，它的结点为基本块，有一个入口结点（无前驱结点）和一个出口结点（无后续结点） 扩展：程序图有三种表示（常用的） 流程图 N-S图 PAD图,定义三、定值 在基本块当中，若有d: x:=e,则称有对x的定值，d: 为 x的定值点。（注：d:为程序中引入的标识，对程序无影响） 定义四、注销 若有对变量x的赋值x:=,则程序注销了x的原定值。用killB表示B中被注销的所有变量之集。,定义五、向下暴露的定值 设（Bi,di） 为x的一个定值，若从

21、di+1到Bi的出口再无对x的定值，则称x的di的定值为向下暴露的定值，并用defBi表示Bi中的所有向下暴露定值的变量之集。,定义六、可能到达的定值 说在（Bi,di）点x定值可能到达 （Bj,dj）点 ，若从（Bi,di）存在一条路，且在该路上无x的定值。,可到达的定值数据流方程 inB*=，B*为入口块。； outB=defB (in(B)-kill(B) ) inB = (outBi) i=1,2,n；Bi为B的前驱结点 其中 inB表示在B入口处有定值的变量之集 outB表示定值可到达B出口处的变量定值之集,inB1 = outB1 = d2，d3 inB2 = d2,d3,d7 o

22、utB2 = d2,d4,d5,d7 inB3 = d2,d4,d5,d7 outB3 = d2,d4,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,定义七、定义性出现，使用性出现 称第一次出现在赋值命令左部的变量出现（即x:=第一次出现）为变量（x）的定义性出现，而称其他部位中的变量出现为其使用性出现,定义八、向上暴露的使用 在(Bi,di)有x的使用性出现，若从Bi的入口到di-1点无对x的赋值。则称x在(Bi,di)点的出现为向上暴露的使用，用use

23、_liveB表示B中所有向上暴露的使用,定义九、变量的活跃性 说变量x在（Bi,di）点活跃，若： 1.存在一点（Bj,dj）有x的使用性出现。 2.从（Bi,di)到（Bj,dj)存在一条通路，且在该路上无对x的定值。 定义十、注销活跃性 若在某一点（Bk,dk) 有X:=，则称注销X的活跃性,活跃变量的数据流方程 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_li

24、veB=x|B中所有局部向上暴露使用的变量 kill_liveB=x|B注销其活跃性的变量。,定义十一、过程调用块 把过程调用P(e1,en)定义为一个独立的基本块，称为过程调用块 。 定义十二、过程的返回块 调用块的接续为返回块（或return的后续块）难点： 下标变量的分析 别名问题,程序分析技术,第五讲： 数据流分析技术应用,一、检测数据流异常,数据流异常情况： 变量无定值而使用； 变量重复定值； 变量定值无使用。,检测方法（a）,in_dB:表示在B入口处所有定值的变量之集； out_dB:表示B在出口处所有定值的变量之集； def_dB:表示B中所有定值的变量之集。,数据流方程（a）

25、,in_dB*= B*为入口块 in_dB=（或）i=1,2n(out_dBi) Bi为B的前驱块 out_dB=def_dBin_dB,数据流方程（a）,结论： 若in_liveBin_dB，则必有变量无定值而使用; 特例：若in_liveB*，则必有变量无定值而使用.,检测方法（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的

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

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

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

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

30、不相同但语义相同的表达式节省问题。 例如： X:=A*B1 C:=A2 Y:=C*B3 由2可知13等价,程序分析技术,第六讲： 一种信息流分析技术,一、处理的语言,S-skip |V:=e |If e then s else s |If e then s |s; s |While e do s 选择的原因：结果定理,e1,S1,S2,S3,S4,e2,二、基本方法,结构图,S3,S4,e1,S1,S2,e1,S1,基本定义 定义：设S为一个语句，若在S中有V:=e,一则称S定义了v。用Ds表示S定义的所有变量之集。 设S为一个语句，从G(S)入口到G(S)出口存在一条路，且在该路上无对变量x

31、的赋值，则称S保护了x。用Ps表示S保护的所有变量之集。,定义：变量与表达式的关系 若变量v在G(S)入口处值，直接或间接参与了表达式e的计算，则说v和e具有关系，记为vS e或者(v, e) S。 定义：表达式与变量的关系 若表达式e直接或间接参加变量v在G(S)出口处值的计算，则称e和v具有关系，记为eS v或者(e, v) S。,定义：变量与变量的关系 S = SS (v, v) | vPS 解释，v1Sv2，v在G(S)的入口值参与v2在G(S2)出口值的计算。 v1Sv2，v1在G(S)的入口值可？ G(S)的出口,3.计算方法 空语句 S：skip; Ds = , ps= V s

32、=,s = ps =(v, v) | vps 赋值语句S：v := e; DS =v,PS= V- v S = (v, e) | vV (e), S = (e, v) S = (v, v) | vuse (e) (v, v)| v PS,顺序语句S：A;B DS= DA DB, PS= PA PB S = A AB, S = ABB S = AB 条件语句S：if e then A else B DS= DA DB,PS= PA PB S = (v, e)| v use(e) A B S = AB (e, v)| v (DA DB) S = AB (v, v)| v use(e)，vDA DB

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

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

35、x,y,z,k,例 while e do x:=y+z; y:=z+1; z:=k+1; (x)=2 定义：稳定表达式 设e是循环语句s中的一个表达式，若use(e)中的变量都是稳定的，则称e是稳定的。,x,y,z,定义：稳定表达式e的稳定长度 设e是关于s稳定的，其稳定长度用(e)表示。定义如下： (e) =max(v) |vuse(e)+1。,结论： 任意一个稳定变量，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。 任意一个稳定表达式，当循环的次数到达一个定值（稳定长度+1）时，其值不会改变。 若while e do A中的e是稳定的，很有可能出错（陷入死循环）。,应用： 可根据上述分析结果，进行应用。 例如： 部分求值的程序例化（循环展开）,程序分析技术,第七讲 程序切片,1引言,Weiser于1979年提出 一个程序片S是由程序P中那些可能