《程序分析技术》PPT课件.pptx

程序分析技术 程序分析技术 第一讲 程序设计语言的发展 一 程序分析的任务 以程序为对象 分析其属性 如 值的获取与传播活跃性 3 二 程序分析技术的应用 程序转换程序理解程序演化程序逆向工程 4 程序验证与测试程序优化重构自动并行化 5 三 程序设计语言的发展 6 三 程序设计语言的发展 机器语言 指令 二进制组成具有基本操作 左移 右移 加1缺点 可读性差 可理解性差 写程序困难 不方便 问题 程序的维护比较困难扩展纠错预防适应 7 三 程序设计语言的发展 汇编语言 符号化了的机器语言功能没有扩充可读性强 例 将 R4R5 中的双字节数取补 结果送R4R5 CMPT MOVA R5CPLAADDA 1MOVR5 AMOVA R4CPLAADDCA 0MOVR4 ARET 8 三 程序设计语言的发展 高级程序设计语言 1 过程式语言PASCAL C FORTRAN PL1特点 命令为基础 程序由一系列语句组成 语句的执行引起存储单元值的变化 程序的正确型 归纳断言指导 数学性质弱 副作用 变量值变化 数据类型不够丰富程序的动静态结构差异大 9 历史上的goto语句之争 1970 XPL编译器只用了一个goto1972 操作系统只有五处用了标号和goto难以理解 难以查错 动静态差异大修改引起的副作用小 全局优化简单概念简单 效率高 10 三 程序设计语言的发展 高级程序设计语言 2 函数式语言LISP ML HOPE FP 程序由一组函数组成 通过调用执行程序 特点 数学性质好数据类型可自定义支持并行计算抽象级别高数据以表为基础 11 三 程序设计语言的发展 高级程序设计语言 3 逻辑式语言PROLOG以谓词为基础 具有推理能力特定的应用领域抽象的问题求解公式处理专家系统人工智能等 12 三 程序设计语言的发展 高级程序设计语言 4 对象式语言SmallTalk80特点 封装性继承性多态性 13 三 程序设计语言的发展 第四代语言 特定领域的特殊类语言高级语言的抽象如 Oracle应用开发环境 PowerBuilder 14 四 程序分析的一般方法 静态分析方法动态分析方法 15 五 静态的分析过程 词法分析语法分析所需要的分析 16 程序分析技术 第二讲编译原理基础 大纲 基本概念正则表达式自动机理论文法概述语法分析自顶向下自底向上 18 1基本概念 字母表 元素的非空有穷集合 符号串 由字母表中的符号组成的任何有穷序列 或者如下定义 空符号串 是 上的符号串若x是 上的符号串 a是 的元素 则xa是 上的符号串y是 上的符号串 当且仅当它可以由1和2导出 19 符号串的连接 设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 符号串集合 若集合A中的所有元素都是某字母表上的符号串 则称A为该字母表上的符号串集合 符号串集合的乘积 设A B是两个符号串集合 AB表示A与B的乘积 则定义AB xy x A y B 符号串集合的方幂 设A是符号串集合 则称Ai是符号串集合A的方幂 其中i是非负整数 A0 A1 A A2 AA An AA A符号串集合的正闭包 A A1 A2 A3 符号串集合的星闭包 A A0 A1 A2 A3 21 2正则表达式 定义 RE为定义在 上的正则表达式则 RE若a 则a RE若e1 e2 RE 则e1 e2 e1 e2 e1 RE语义函数 解释函数 LL L 若a 则L a a 若e1 e2 RE则L e1 e2 L e1 L e2 L e1 e2 L e1 L e2 L e1 L e1 22 实例 a b 23 3自动机 定义 一个DFA是一个5元组 S S0 F 其中S是状态集合 是字符集 是转换函数 转移函数 S S S0为初始状态S0 S F为终止状态集合 F S 两种表示形式转换图转换矩阵 24 3 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 Q 25 两种表示形式 26 S U Q V a a a a b b b b 3 2词法分析 功能 读源程序的字符序列 逐个拼出单词 并构造相应的内部表示 同时检查源程序中的词法错误 单词 所谓单词是指语言中具有独立含义的最小的语义单位 Token 单词的内部表示 程序语言的操作对象 只能 是该语言规定的各种数据 编译程序是用某种程序语言书写的程序 其操作对象是一般程序中的各种语法单位 27 单词的一种分类方法 28 识别常数的自动机 29 A B 数字 数字 数字 数字 D 小数点 数字 注 未考虑前导0的情形 4文法概述 文法能清晰地描述程序设计语言的语法构成 易于理解 文法能构造有效的语法分析器 检查源程序是否符合语言规定的语法形式 文法定义可以了解程序设计语言的结构 有利于将源程序转化为目标代码及检查出语法错误 基于文法实现的语言易于扩展 30 4 1文法定义 文法G定义为四元组 VT VN S P VT是有限的终极符集合VN是有限的非终极符集合S是开始符 S VNP是产生式的集合 且具有下面的形式 其中 VT VN 31 4 2文法分类 O型文法 也称为短语文法 其产生式具有形式 其中 VT VN 并且 至少含一个非终极符 1型文法 也称为上下文相关文法 它是0型文法的特例 要求 S 例外 但S不得出现于产生式右部 2型文法 也称为上下文无关文法 它是1型文法的特例 即要求产生式左部是一个非终极符 A 3型文法 也称为正则文法 它是2型文法的特例 即产生式的右部至多有两个符号 而且具有下面形式之一 A a A aB其中A B VN a VT 32 4 3上下文无关文法 定义为四元组 VT VN S P VT是有限的终极符集合VN是有限的非终极符集合S是开始符 S VNP是产生式的集合 且具有下面的形式 A X1X2 Xn其中A VN Xi VT VN 右部可空 33 4 4文法相关概念 推导 直接推导 如果A 是一个产生式 则有 A 其中 表示一步推导 用A 这时称 是由 A 直接推导的 的含义是 使用一条规则 代替 左边的某个符号 产生 右端的符号串 表示 通过一步或多步可推导出 表示 通过0步或多步可推导出 34 句型 如果有S 则称符号串 为CFG的句型 我们用SF G 表示文法G的所有句型的集合 句子 如果 只包含终极符 则称 为CFG的句子 语言 L G u S u u VT 文法G所定义的语言是其开始符所能推导的所有终极符号串 句子 的集合 35 最左 右 推导 如果进行推导时选择的是句型中的最左 右 非终极符 则称这种推导为最左 右 推导 并用符号 lm rm 表示最左 右 推导 左 右 句型 用最左推导方式导出的句型 称为左句型 而用最右推导方式导出的句型 称为右句型 规范句型 结论 每个句子都有相应的最右和最左推导 但对句型此结论不成立 36 短语 设S是文法的开始符 是句型 即有S 如果满足条件 S A A VT 则称 是句型 的一个短语 任一子树的树叶全体 具有共同祖先的叶节点符号串 皆为短语 直接短语 简单短语 如果满足条件 S A A VT 则称 是句型 的一个简单短语 任一简单子树的树叶全体 具有共同父亲的叶节点符号串 皆为简单短语 句柄 一个句型可能有多个简单短语 其中最左的简单短语称之为句柄 37 语法分析树 简称分析树 用来描述句型的结构 是句型推导的一种树型表示 文法G VN VT S P 则称满足下面条件的树为G的一棵语法分析树 每个结点都有G的一个文法符号 并且根结点标有初始符S 非叶结点标有非终极符 叶结点标有终极符或非终极符或 如果一个非叶结点A有n个儿子结点 从左到右 为X1 X2 Xn 则G一定有产生式A X1X2 Xn 38 线性推导 我们称用 符号进行的推导为线性推导 树型推导与线性推导的不同 线性推导指明了推导的顺序 而树型推导则没有指明推导的顺序 因此 句型一般只有一棵分析树 如果无二义性 而线性推导则可以有很多棵分析树 二义性文法 如果一个文法的某个句型有两棵不同的语法分析树 则称该文法二义性为二义性文法 例 文法G i E E P 其中P为 E iE E EE 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自顶向下分析基本思想 从文法开始符出发试图推导出所给的终极符串 例G z 1 Z aBd 2 B d 3 B c 4 B bB 42 aBd abcd MatchBd bcd DerivationbBd bcd MatchBd cd Derivationcd cd Matchd d Match Success 自顶向下的语法分析过程 Sf Rest Action D M S E Z abcd Derivation 自顶向下分析实例 43 自下而上 SaAcBeAbdb 5 2自底向上语法分析 思想 从待分析的符号串开始 自左向右进行扫描 自下而上进行分析 通过反复查找当前句型的句柄 并使用产生式规则将找到的句柄归约为相应产生式的左部非终极符 直到将输入串归约为文法的开始符 移入 归约分析 1 1例 S aAcBe 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 aAcBe 1 aAcd 4 e 1 aAb 3 cd 4 e 1 ab 2 b 3 cd 4 e 1 程序分析技术 第三讲 元程序设计 一 基础知识 词法分析基本概念描述工具正则表达式自动机实现词法分析器注意的问题 47 语法分析形式语言分析原来自顶向下的语法分析自底向上的语法分析语法制导分析的过程生成中间表示 48 二 元程序 元程序概念处理程序的程序元程序系统的组成 预处理 把源程序变成一种中间表示 经过词法分析 语法分析 元级操作 提供最基本的操作 根据需求 用户可选择如何操作 后处理 有必要把中间表示转为源代码 49 三 中间表示 四元式 op a b t 例a b c d b c t1 a t1 t2 t2 d t3 逆波兰式 后缀式上例abc d 树上例 50 四 规则分类和对应的结构 结构规则 构造规则 A X1X2 Xn选择规则A X1 X2 Xn是结构规则的特例 因为每次只能用一个规则 51 X1X2Xn 表规则A E E A 也可左递归 构造双向链表操作更方便词汇规则A lex 52 实例 whilex 0doify 0thenx x 1elsey y 1 53 五 元级操作 低级元操作类型识别操作给结点的类型判定结点是否为给定的类型空结点定位成份选择操作选择某一结点 满足条件 表元素的选择 54 构造操作按某一结构构造结点 关系操作给定两结点 判断它们的关系 给定结点和关系 判断是否存在结点 编辑操作插入 删除 查找 修改词汇强制高级元级操作可根据特定的需要 构造许多特殊的高级操作 如 控制流图 函数调用关系图等 55 六 系统的自动生成 利用语法制导的方法生成系统由两部分组成生成中间表示部分元级操作部分 可事先设计好 56 按照A X1 Xn归约时状态为Xi的结点已经构造好文法 结点指针未填规约后 Xi结点指针添加 A结点指针均空Xi退栈A进栈 57 d Sem栈 程序分析技术 第四讲 数据流分析技术 一 概述 数据流分析技术是对源程序分析 获取程序中变量定值和传播的情况 帮助理解程序中的数据流动情况 二 基本概念 定义一 基本块是一个顺序执行的命令序列 进入一个基本块 必须从第一条命令进入 退出基本块 必须由最后一条命令退出 特点 后续执行情况可判断 定义二 程序图是一个有向图 它的结点为基本块 有一个入口结点 无前驱结点 和一个出口结点 无后续结点 扩展 程序图有三种表示 常用的 流程图N S图PAD图 定义三 定值在基本块当中 若有d x e 则称有对x的定值 d 为x的定值点 注 d 为程序中引入的标识 对程序无影响 定义四 注销若有对变量x的赋值x 则程序注销了x的原定值 用kill B 表示B中被注销的所有变量之集 定义五 向下暴露的定值设 Bi di 为x的一个定值 若从di 1到Bi的出口再无对x的定值 则称x的di的定值为向下暴露的定值 并用def Bi 表示Bi中的所有向下暴露定值的变量之集 定义六 可能到达的定值说在 Bi di 点x定值可能到达 Bj dj 点 若从 Bi di 存在一条路 且在该路上无x的定值 可到达的定值数据流方程in B B 为入口块 out B def B in B kill B in B out Bi i 1 2 n Bi为B的前驱结点其中in B 表示在B入口处有定值的变量之集out B 表示定值可到达B出口处的变量定值之集 in B1 out B1 d2 d3 in B2 d2 d3 d7 out B2 d2 d4 d5 d7 in B3 d2 d4 d5 d7 out B3 d2 d4 d5 d6 d7 in B4 d2 d4 d5 d7 out B4 d4 d5 d7 in B5 d2 d4 d5 d6 d7 out B5 d2 d4 d5 d7 d8 d9 定义七 定义性出现 使用性出现称第一次出现在赋值命令左部的变量出现 即x 第一次出现 为变量 x 的定义性出现 而称其他部位中的变量出现为其使用性出现 定义八 向上暴露的使用在 Bi di 有x的使用性出现 若从Bi的入口到di 1点无对x的赋值 则称x在 Bi di 点的出现为向上暴露的使用 用use live B 表示B中所有向上暴露的使用 定义九 变量的活跃性说变量x在 Bi di 点活跃 若 1 存在一点 Bj dj 有x的使用性出现 2 从 Bi di 到 Bj dj 存在一条通路 且在该路上无对x的定值 定义十 注销活跃性若在某一点 Bk dk 有X 则称注销X的活跃性 活跃变量的数据流方程in live B use live B out live B kill live B out live B in live Bi Bi为B的后续out live B B 为出口块其中in live B x x在B入口处活跃 out live B x x在B出口处活跃 use live B x B中所有局部向上暴露使用的变量 kill live B x B注销其活跃性的变量 定义十一 过程调用块把过程调用P e1 en 定义为一个独立的基本块 称为过程调用块 定义十二 过程的返回块调用块的接续为返回块 或return的后续块 难点 下标变量的分析别名问题 程序分析技术 第五讲 数据流分析技术应用 一 检测数据流异常 数据流异常情况 变量无定值而使用 变量重复定值 变量定值无使用 检测方法 a in d B 表示在B入口处所有定值的变量之集 out d B 表示B在出口处所有定值的变量之集 def d B 表示B中所有定值的变量之集 数据流方程 a in d B B 为入口块in d B 或 i 1 2 n out d Bi Bi为B的前驱块out d B def d B in d B 数据流方程 a 结论 若in live B in d B 则必有变量无定值而使用 特例 若in live B 则必有变量无定值而使用 检测方法 b in dd Bi 表示块B入口处所有定值而未使用的变量之集 out dd Bi 表示块B出口处所有定值而未使用的变量之集 def dd1 Bi x x在 B di 点定值 且从 B d1 B di 无x的使用性出现 def dd2 Bi x x在 B di 点定值 且从 B di 1 到B出口 无x的使用性出现 数据流方程 b in dd B B 为入口块in dd B 或 out dd B out dd B def dd2 B in dd B use B 数据流方程 b 结论 若in dd B def dd1 B 则有变量重复定值 若in dd B in live Bi 则有变量定值而未使用 或重复定值 若out dd B B 为出口块 则有变量定值而未使用 程序优化 全局常表达式节省 基本块的常表达式节省问题 利用的信息不充分 定义 常量定值若在块B中有x c 其中c是常数 且该定值是向下暴露的 则称x有一个常量定值 记为x c 定义 注销常量定值若有x E 则称注销了x的常量定值 解决办法 定义 广义常量定值若块B中有向下暴露的定值x E 且E的值可计算为一个常量c 则称产生一个广义常量定值x c 定义 注销广义常量定值若有x 则称注销了广义常量定值 数据流方程 in ac B0 B0为入口块in ac Bi j 1 2 nout ac Bj Bj为Bi的前驱out ac Bi def ac Bi in ac Bi kill ac Bi 优化过程 建立数据流方程求解对每一基本块进入优化把in ac B 填入vvl按原方法优化 in ac B1 out ac B1 x 1 y 2 in ac B2 x 1 y 2 out ac B2 x 1 y 2 z 3 b 4 in ac B3 x 1 y 2 out ac B3 x 1 y 2 z 3 b 4 in ac B4 x 1 y 2 z 3 b 4 out ac B4 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 e B0 B0为入口块out e Bi def e Bi in e Bi kill e Bi in e Bi Bj pre Bi out e Bj Bj为Bi的前驱 需要注意的两个问题 形式相同的表达式未必能节省 已解决 形式不同的表达式也可能节省 未解决 定义 等式定值在块B中 若有x y 且从di 1到B出口无对x或y的赋值 则称B有了一个等式定值 即x y定义 注销等式定值若有对x的赋值x 则称注销了所有x的等式定值 数据流方程in eq B0 B0为入口块out eq Bi def eq Bi in e qBi kill eq Bi in eq Bi Bj pre Bi out eq Bj 利用等式定值和表达式定值 可以解决形式不相同但语义相同的表达式节省问题 例如 X A B 1 C A 2 Y C B 3 由 2 可知 1 3 等价 程序分析技术 第六讲 一种信息流分析技术 一 处理的语言 S skip V e Ifethenselses Ifethens s s Whileedos选择的原因 结果定理 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的赋值 则称S保护了x 用Ps表示S保护的所有变量之集 定义 变量与表达式的关系若变量v在G S 入口处值 直接或间接参与了表达式e的计算 则说v和e具有关系 记为v Se或者 v e S 定义 表达式与变量的关系若表达式e直接或间接参加变量v在G S 出口处值的计算 则称e和v具有关系 记为e Sv或者 e v S 定义 变量与变量的关系 S S S v v v PS 解释 v1 Sv2 v在G S 的入口值参与v2在G S2 出口值的计算 v1 Sv2 v1在G S 的入口值可 G S 的出口 3 计算方法空语句S skip Ds ps V s s ps v v v ps 赋值语句S v e DS v PS V v S v e v V e S e v S v v v use e v v v PS 顺序语句S A BDS DA DB PS PA PB S A A B S A B B S A B条件语句S ifethenAelseBDS DA DB PS PA PB S v e v use e A B S A B e v v DA DB S A B v v v use e v DA DB 简单条件语句s ifethenAelse部分为skip可用上述规则计算 循环语句S whileedoADS DA PS V S A v e v use e A S e v v DA A A S 公式计算 三 应用 1 看某一输入变量对那些输出变量有影响设v Vi v Vo 若 v v 成立 则v 对v 有影响 影响集 v v v Vo v v 2 看那些输入变量对某些输出变量的影响给定v v v v v v v 被影响集对v 有影响 3 无用的输入变量若输入变量影响的输出变量集为空 则该输入变量对程序的运行结果无影响 4 无效语句v e e v v Vo 则该语句可用skip替换或含有错误 5 对循环语句的分析设有whileedoA 定义一个G S 点集为DA 边集为 A 定义 稳定变量在G S 中 如果任一环路上的变量都没有列该变量的路 则称该变量是关于S稳定的例 whileedoX 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 x y z k 例whileedox 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 v use e 1 结论 任意一个稳定变量 当循环的次数到达一个定值 稳定长度 1 时 其值不会改变 任意一个稳定表达式 当循环的次数到达一个定值 稳定长度 1 时 其值不会改变 若whileedoA中的e是稳定的 很有可能出错 陷入死循环 应用 可根据上述分析结果 进行应用 例如 部分求值的程序例化 循环展开 程序分析技术 第七讲程序切片 1引言 Weiser于1979年提出一个程序片S是由程序P中那些可能影响在某一兴趣点n计算