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

程 序 分 析 技 术 程 序 分 析 技 术第 一 讲 ：程 序 设 计 语 言 的 发 展 一 、 程 序 分 析 的 任 务以 程 序 为 对 象 ， 分 析 其 属 性 ， 如 ： 值 的 获 取 与 传 播 活 跃 性 3 二 、 程 序 分 析 技 术 的 应 用1. 程 序 转 换2. 程 序 理 解3. 程 序 演 化4. 程 序 逆 向 工 程 4 5 . 程 序 验 证 与 测 试6 . 程 序 优 化7 . 重 构8 . 自 动 并 行 化9 . 5 三 、 程 序 设 计 语 言 的 发 展 6 三 、 程 序 设 计 语 言 的 发 展 机 器 语 言指 令 ： 二 进 制 组 成 具 有 基 本 操 作 ， 左移 、 右 移 、 加 1缺 点 ： 可 读 性 差 （ 可 理 解性 差 ） 写 程 序 困 难 （ 不 方便 ） 问 题 ： 程 序 的 维 护 比较 困 难 扩 展 纠 错 预 防 适 应 7 三 、 程 序 设 计 语 言 的 发 展 汇 编 语 言 符 号 化 了 的 机 器语 言 功 能 没 有 扩 充 可 读 性 强 例 ： 将 (R4R5)中 的 双 字 节数 取 补 ， 结 果 送 R4R5。CMPT： MOV A， R5CPL AADD A， #1MOV R5， AMOV A， R4CPL AADDC A， #0MOV R4， A RET 8 三 、 程 序 设 计 语 言 的 发 展 高 级 程 序 设 计 语 言(1)过 程 式 语 言PASCAL,C,FORTRAN,PL1特 点 ： 命 令 为 基 础 ， 程 序 由 一 系 列 语 句 组 成 ， 语 句 的执 行 引 起 存 储 单 元 值 的 变 化 。 程 序 的 正 确 型 （ 归 纳 断 言 指 导 ） 数 学 性 质 弱 （ 副 作 用 ， 变 量 值 变 化 ） 数 据 类 型 不 够 丰 富 程 序 的 动 静 态 结 构 差 异 大 9 历 史 上 的 goto语 句 之 争1970， XPL编 译 器 只 用 了 一 个 goto1972， 操 作 系 统 只 有 五 处 用 了 标 号 和goto 难 以 理 解 ， 难 以 查 错 ， 动 静 态 差 异 大 修 改 引 起 的 副 作 用 小 ， 全 局 优 化 简 单 概 念 简 单 ， 效 率 高 1 0 三 、 程 序 设 计 语 言 的 发 展 高 级 程 序 设 计 语 言(2)函 数 式 语 言LISP,ML,HOPE,FP程 序 由 一 组 函 数 组 成 ， 通 过 调 用 执 行 程 序 。特 点 ： 数 学 性 质 好 数 据 类 型 可 自 定 义 支 持 并 行 计 算 抽 象 级 别 高 数 据 以 表 为 基 础 1 1 三 、 程 序 设 计 语 言 的 发 展 高 级 程 序 设 计 语 言(3)逻 辑 式 语 言 PROLOG 以 谓 词 为 基 础 ， 具 有 推 理 能 力 特 定 的 应 用 领 域 抽 象 的 问 题 求 解 公 式 处 理专 家 系 统 人 工 智 能 等 1 2 三 、 程 序 设 计 语 言 的 发 展 高 级 程 序 设 计 语 言(4)对 象 式 语 言SmallTalk80 特 点 ： 封 装 性 继 承 性 多 态 性 1 3 三 、 程 序 设 计 语 言 的 发 展 第 四 代 语 言特 定 领 域 的 特 殊 类 语 言高 级 语 言 的 抽 象如 ： Oracle应 用 开 发 环 境 、 Power Builder 1 4 四 、 程 序 分 析 的 一 般 方 法 静 态 分 析 方 法 动 态 分 析 方 法 1 5 五 、 静 态 的 分 析 过 程 词 法 分 析 语 法 分 析 所 需 要 的 分 析 1 6 程 序 分 析 技 术第 二 讲编 译 原 理 基 础 大 纲 基 本 概 念 正 则 表 达 式 自 动 机 理 论 文 法 概 述 语 法 分 析自 顶 向 下自 底 向 上 1 8 1 基 本 概 念 字 母 表 ： ， 元 素 的 非 空 有 穷 集 合 。 符 号 串 ： 由 字 母 表 中 的 符 号 组 成 的 任 何 有 穷 序列 。 或 者 如 下 定 义 ：1.空 符 号 串 是 上 的 符 号 串 2.若 x是 上 的 符 号 串 ,a是 的 元 素 ,则 xa是 上的 符 号 串 3.y是 上 的 符 号 串 ,当 且 仅 当 它 可 以 由 1和 2导出 1 9 符 号 串 的 连 接 ： 设 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 的 子 字 符 串 ， 简 称子 串 。 如 果 删 去 的 前 缀 和 后 缀 不 同 时 为 ,则 称该 子 串 为 真 子 串 。 2 0 符 号 串 集 合 ： 若 集 合 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 2 1 2 正 则 表 达 式 定 义 ： RE为 定 义 在 上 的 正 则 表 达 式 则 , RE若 a ， 则 a RE若 e1,e2 RE， 则 e1 e2,e1|e2,e1+ RE 语 义 函 数 （ 解 释 函 数 ） L L( )= ， 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)2 2 实 例 = a,b 2 3 正 则 表 达 式 e1. ab*2. a(a|b)* L(e)1. 上 所 有 以 a为 首 后 跟 任 意 多个 （ 包 括 0个 ） b的 字 符 串 集2. 上 所 有 以 a为 首 的 字 符 串 集 3 自 动 机 定 义 ： 一 个 DFA是 一 个 5元 组(S, , ,S0,F)， 其 中 S是 状 态 集 合 ， 是 字 符 集 ， 是 转 换 函 数 （ 转 移 函数 ） S S ， S0为 初 始 状 态 S0 S，F为 终 止 状 态 集 合 ， FS。 两 种 表 示 形 式转 换 图转 换 矩 阵 2 4 3.1 自 动 机 实 例确 定 有 限 状 态 自 动 机 M=(a, b,S, U, V, Q, f, S, Q)， 其 中 f定 义 为 ：f (S, a)=U f (V, a)=Uf (S, b)=V f (V, b)=Qf (U, a)=Q f (Q, a)=Qf (U, b)=V f (Q, b)=Q 2 5 两 种 表 示 形 式 S U V Qa U Q U Qb V V Q Q 2 6 S UQV a a aab bb b 3.2 词 法 分 析 功 能 ： 读 源 程 序 的 字 符 序 列 ， 逐 个 拼 出 单词 ， 并 构 造 相 应 的 内 部 表 示 ， 同 时 检 查 源程 序 中 的 词 法 错 误 。 单 词 ： 所 谓 单 词 是 指 语 言 中 具 有 独 立 含 义的 最 小 的 语 义 单 位 。 Token： 单 词 的 内 部 表 示 。 “ 程 序 语 言 的 操作 对 象 （ 只 能 ） 是 该 语 言 规 定 的 各 种 数据 。 ” 编 译 程 序 是 用 某 种 程 序 语 言 书 写 的程 序 ， 其 操 作 对 象 是 一 般 程 序 中 的 各 种 语法 单 位 。 2 7 单 词 的 一 种 分 类 方 法单 词 标 识 符 X1 ，classT常 量 1 0 ，LENGTH特 殊 符 号 保 留 字 while，int运 算 符 +， 界 限 符 ， ， ；格 式 符 EOF， 2 8 识 别 常 数 的 自 动 机 2 9 A B E+数 字 -数 字数 字 C 数 字D小 数 点 数 字注 ： 未 考 虑 前 导 0 的 情 形 4 文 法 概 述 文 法 能 清 晰 地 描 述 程 序 设 计 语 言 的 语 法 构成 ， 易 于 理 解 。 文 法 能 构 造 有 效 的 语 法 分 析 器 ， 检 查 源 程序 是 否 符 合 语 言 规 定 的 语 法 形 式 。 文 法 定 义 可 以 了 解 程 序 设 计 语 言 的 结 构 ，有 利 于 将 源 程 序 转 化 为 目 标 代 码 及 检 查 出语 法 错 误 。 基 于 文 法 实 现 的 语 言 易 于 扩 展 3 0 4.1 文 法 定 义文 法 G定 义 为 四 元 组 (VT,VN,S,P) VT是 有 限 的 终 极 符 集 合 VN是 有 限 的 非 终 极 符 集 合 S是 开 始 符 ， S VN P是 产 生 式 的 集 合 ， 且 具 有 下 面 的 形 式 ：， 其 中 ， (VTVN)* 3 1 4.2 文 法 分 类 O型 文 法 ： 也 称 为 短 语 文 法 ， 其 产 生 式 具 有 形 式 : ， 其 中 ,(VTVN)*， 并 且 至 少 含 一 个 非终 极 符 。 1型 文 法 ： 也 称 为 上 下 文 相 关 文 法 。 它 是 0型 文 法的 特 例 ， 要 求 | | (S 例 外 ， 但 S不 得 出现 于 产 生 式 右 部 )。 2型 文 法 ： 也 称 为 上 下 文 无 关 文 法 。 它 是 1型 文 法的 特 例 ， 即 要 求 产 生 式 左 部 是 一 个 非 终 极 符 : A 。 3型 文 法 ： 也 称 为 正 则 文 法 。 它 是 2型 文 法 的 特 例 ，即 产 生 式 的 右 部 至 多 有 两 个 符 号 ， 而 且 具 有 下 面形 式 之 一 : A a ， A a B 其 中 A,BV N ，aVT 。 3 2 4.3 上 下 文 无 关 文 法定 义 为 四 元 组 (VT,VN,S,P) VT是 有 限 的 终 极 符 集 合 VN是 有 限 的 非 终 极 符 集 合 S是 开 始 符 ， S VN P是 产 生 式 的 集 合 ， 且 具 有 下 面 的 形 式 ：AX1X2Xn 其 中 AVN， Xi(VTVN) ， 右 部 可 空 。 3 3 4.4 文 法 相 关 概 念 推 导 （ 直 接 推 导 ） ： 如 果 A是 一 个 产 生式 ， 则 有 A ,其 中 表 示 一 步 推 导(用 A )。 这 时 称 是 由 A直 接 推 导 的 。 的 含 义 是 ， 使 用 一 条 规 则 ， 代 替 左 边的 某 个 符 号 ， 产 生 右 端 的 符 号 串 。 + : 表 示 通 过 一 步 或 多 步 可 推 导 出 * : 表 示 通 过 0步 或 多 步 可 推 导 出 3 4 句 型 ： 如 果 有 S* ， 则 称 符 号 串 为 CFG的 句 型 。 我 们 用 SF(G)表 示 文 法 G的 所 有 句型 的 集 合 。 句 子 ： 如 果 只 包 含 终 极 符 ， 则 称 为 CFG的句 子 。 语 言 ： L(G)= u| S + u ,u VT* 文 法 G所 定 义 的 语 言 是 其 开 始 符 所 能 推 导 的所 有 终 极 符 号 串 (句 子 )的 集 合 。 3 5 最 左 （ 右 ） 推 导 ： 如 果 进 行 推 导 时 选 择 的是 句 型 中 的 最 左 (右 ） 非 终 极 符 ， 则 称 这 种推 导 为 最 左 (右 )推 导 ， 并 用 符 号 lm（ rm）表 示 最 左 （ 右 ） 推 导 。 左 （ 右 ） 句 型 ： 用 最 左 推 导 方 式 导 出 的 句型 ， 称 为 左 句 型 ， 而 用 最 右 推 导 方 式 导 出的 句 型 ， 称 为 右 句 型 (规 范 句 型 )。结 论 ： 每 个 句 子 都 有 相 应 的 最 右 和 最 左 推 导（ 但 对 句 型 此 结 论 不 成 立 ） 3 6 短 语 ： 设 S是 文 法 的 开 始 符 ， 是 句 型 (即有 S *） ， 如 果 满 足 条 件 ：S* A A+ VT+ 则 称 是 句 型 的 一 个 短 语 。 任 一 子 树 的树 叶 全 体 (具 有 共 同 祖 先 的 叶 节 点 符 号 串 )皆为 短 语 。 直 接 短 语 （ 简 单 短 语 ） ： 如 果 满 足 条 件 ：S* A A VT+ 则 称 是 句 型 的 一 个 简 单 短 语 。 任 一 简单 子 树 的 树 叶 全 体 (具 有 共 同 父 亲 的 叶 节 点符 号 串 )皆 为 简 单 短 语 。 句 柄 ： 一 个 句 型 可 能 有 多 个 简 单 短 语 ， 其中 最 左 的 简 单 短 语 称 之 为 句 柄 。 3 7 语 法 分 析 树 (简 称 分 析 树 )用 来 描 述 句 型 的 结 构 ，是 句 型 推 导 的 一 种 树 型 表 示 。 文 法 G=(VN,VT,S,P)， 则 称 满 足 下 面 条 件 的 树 为 G的一 棵 语 法 分 析 树 ：1. 每 个 结 点 都 有 G的 一 个 文 法 符 号 ， 并 且 根 结点 标 有 初 始 符 S， 非 叶 结 点 标 有 非 终 极 符 ，叶 结 点 标 有 终 极 符 或 非 终 极 符 或 。2. 如 果 一 个 非 叶 结 点 A有 n个 儿 子 结 点 (从 左 到右 ） 为 X1,X2,.,Xn， 则 G一 定 有 产 生 式 A X1X2 .Xn 。 3 8 线 性 推 导 ： 我 们 称 用 符 号 进 行 的 推 导 为 线 性推 导 。 树 型 推 导 与 线 性 推 导 的 不 同 ： 线 性 推 导 指 明 了推 导 的 顺 序 ， 而 树 型 推 导 则 没 有 指 明 推 导 的 顺序 。 因 此 ， 句 型 一 般 只 有 一 棵 分 析 树 (如 果 无二 义 性 )， 而 线 性 推 导 则 可 以 有 很 多 棵 分 析 树 。 二 义 性 文 法 ： 如 果 一 个 文 法 的 某 个 句 型 有 两 棵不 同 的 语 法 分 析 树 ， 则 称 该 文 法 二 义 性 为 二 义性 文 法 。例 ： 文 法 G=( +,*,i,(,), E, E, P),其 中 P为 ：E i E E + EE E * E E ( E ) 3 9 句 型 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 * Ei i i EE * EE + Ei i推 导 2 的 语 法 树i 4 0 5 语 法 分 析 分 类 自 顶 向 下 递 归 下 降 法 LL（ 1） 方 法 自 底 向 上 简 单 优 先 方 法 LR（ 0） 方 法 SLR（ 1） 方 法 LR（ 1） 方 法 LALR（ 1） 方 法 4 1 5.1 自 顶 向 下 分 析 基 本 思 想 从 文 法 开 始 符 出 发 试 图 推 导 出 所 给 的 终 极符 串 。例 Gz : 1Z aBd2 B d3 B c4 B bB Za B db Bc 4 2 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自 顶 向 下 分 析 实 例 4 3 自 下 而 上Sa A c B eA b db 5.2 自 底 向 上 语 法 分 析 思 想 ： 从 待 分 析 的 符号 串 开 始 ， 自 左 向 右进 行 扫 描 ， 自 下 而 上进 行 分 析 ， 通 过 反 复查 找 当 前 句 型 的 句 柄 ，并 使 用 产 生 式 规 则 将找 到 的 句 柄 归 约 为 相应 产 生 式 的 左 部 非 终极 符 ， 直 到 将 输 入 串归 约 为 文 法 的 开 始 符 。(移 入 -归 约 分 析 ) 1.1例 ： SaAcBe 1A b 2A Ab 3B 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 aAb 3cd4e1 ab2b3cd4e1 程 序 分 析 技 术第 三 讲 ：元 程 序 设 计 一 、 基 础 知 识词 法 分 析1. 基 本 概 念2. 描 述 工 具1) 正 则 表 达 式2) 自 动 机3. 实 现 词 法 分 析 器 注 意 的 问 题 4 7 语 法 分 析1. 形 式 语 言2. 分 析 原 来1) 自 顶 向 下 的 语 法 分 析2) 自 底 向 上 的 语 法 分 析语 法 制 导分 析 的 过 程 生 成 中 间 表 示 4 8 二 、 元 程 序 元 程 序 概 念处 理 程 序 的 程 序 元 程 序 系 统 的 组 成 ：1. 预 处 理 ： 把 源 程 序 变 成 一 种 中 间 表 示（ 经 过 词 法 分 析 ， 语 法 分 析 ）2. 元 级 操 作 ： 提 供 最 基 本 的 操 作 （ 根 据 需求 ， 用 户 可 选 择 如 何 操 作 ）3. 后 处 理 ： 有 必 要 把 中 间 表 示 转 为 源 代 码 4 9 三 、 中 间 表 示 四 元 式 : (op,a,b,t) 例 a*(b+c)+d (+,b,c,t1)， (*,a,t1,t2)， (+,t2,d,t3) 逆 波 兰 式 : 后 缀 式 上 例 abc+*d+ 树 上 例 5 0+* da +b c 四 、 规 则 分 类 和 对 应 的 结 构1.结 构 规 则 （ 构 造 规 则 ）A X1X2 Xn2.选 择 规 则A X1|X2| |Xn是 结 构 规 则 的 特 例 ， 因 为 每 次 只 能 用 一 个规 则 5 1 A X1 X2 Xn 3. 表 规 则 A E|E,A (也 可 左 递 归 )构 造 双 向 链 表 操 作 更 方 便4. 词 汇 规 则 A lex 5 2 t1 At2 E1 t3 E2 t4 E3 实 例while x0 doif y0 then x:=x+1else y:=y+1 5 3 while ifc 0 v yc 0 then else:=v x c 1+v x v x 五 、 元 级 操 作1.低 级 元 操 作1)类 型 识 别 操 作给 结 点 的 类 型判 定 结 点 是 否 为 给 定 的 类 型空 结 点 定 位2)成 份 选 择 操 作选 择 某 一 结 点 （ 满 足 条 件 ）表 元 素 的 选 择 5 4 3)构 造 操 作 按 某 一 结 构 构 造 结 点 。4)关 系 操 作 给 定 两 结 点 ， 判 断 它 们 的 关 系 。 给 定 结 点 和 关 系 ， 判 断 是 否 存 在 结 点 。5)编 辑 操 作 插 入 ， 删 除 ， 查 找 ， 修 改6)词 汇 强 制2. 高 级 元 级 操 作可 根 据 特 定 的 需 要 ， 构 造 许 多 特 殊 的 高 级 操 作 。如 ： 控 制 流 图 ， 函 数 调 用 关 系 图 等 5 5 六 、 系 统 的 自 动 生 成 利 用 语 法 制 导 的 方 法 生 成 系 统 由 两 部 分 组 成生 成 中 间 表 示 部 分元 级 操 作 部 分 （ 可 事 先 设 计 好 ） 5 6 按 照 A X1 Xn 归 约 时状 态 为Xi的 结 点 已 经 构 造 好 文 法 ， 结 点 指 针 未 填规 约 后 ， Xi结 点 指 针 添 加 ， A结 点 指 针 均 空Xi退 栈A进 栈 5 7Xn.X1d Sem栈 程 序 分 析 技 术第 四 讲 ：数 据 流 分 析 技 术 一 、 概 述数 据 流 分 析 技 术 是 对 源 程 序分 析 、 获 取 程 序 中 变 量 定 值 和传 播 的 情 况 ， 帮 助 理 解 程 序 中的 数 据 流 动 情 况 二 、 基 本 概 念定 义 一 、 基 本 块是 一 个 顺 序 执 行 的 命 令 序 列 。 进 入 一 个 基本 块 ， 必 须 从 第 一 条 命 令 进 入 ， 退 出 基本 块 ， 必 须 由 最 后 一 条 命 令 退 出 。特 点 ： 后 续 执 行 情 况 可 判 断 。 定 义 二 、 程 序 图是 一 个 有 向 图 ， 它 的 结 点 为 基 本 块 ，有 一 个 入 口 结 点 （ 无 前 驱 结 点 ） 和一 个 出 口 结 点 （ 无 后 续 结 点 ）扩 展 ： 程 序 图 有 三 种 表 示 （ 常 用 的 ） 流 程 图 N-S图 PAD图 定 义 三 、 定 值在 基 本 块 当 中 ， 若 有 d: x:=e,则 称 有 对 x的 定值 ， d: 为 x的 定 值 点 。 （ 注 ： d:为 程 序 中引 入 的 标 识 ， 对 程 序 无 影 响 ）定 义 四 、 注 销若 有 对 变 量 x的 赋 值 x:=,则 程 序 注 销 了 x的原 定 值 。 用 killB表 示 B中 被 注 销 的 所 有 变量 之 集 。 定 义 五 、 向 下 暴 露 的 定 值设 （ Bi,di） 为 x的 一 个 定 值 ， 若 从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 outB2 = 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_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_liveB=x|B中 所 有 局 部 向 上 暴 露 使 用 的 变 量 kill_liveB=x|B注 销 其 活 跃 性 的 变 量 。 定 义 十 一 、 过 程 调 用 块 把 过 程 调 用 P(e1, en)定 义 为 一 个 独 立的 基 本 块 ， 称 为 过 程 调 用 块 。定 义 十 二 、 过 程 的 返 回 块 调 用 块 的 接 续 为 返 回 块 （ 或 return的 后续 块 ） 难 点 ：1. 下 标 变 量 的 分 析2. 别 名 问 题 程 序 分 析 技 术第 五 讲 ：数 据 流 分 析 技 术 应 用 一 、 检 测 数 据 流 异 常1.数 据 流 异 常 情 况 ：1)变 量 无 定 值 而 使 用 ；2)变 量 重 复 定 值 ；3)变 量 定 值 无 使 用 。 检 测 方 法 （ a）in_dB:表 示 在 B入 口 处 所 有 定 值 的 变 量之 集 ；out_dB:表 示 B在 出 口 处 所 有 定 值 的 变量 之 集 ；def_dB:表 示 B中 所 有 定 值 的 变 量 之 集 。 数 据 流 方 程 （ a）in_dB*= B*为 入 口 块in_dB = （ 或 ） i=1,2 n(out_dBi)Bi为 B的 前 驱 块out_dB=def_dB in_dB 数 据 流 方 程 （ a）结 论 ：若 in_liveB in_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的 使 用 性 出 现 。 数 据 流 方 程 （ b）in_ddB*= B*为 入 口 块 in_ddB= （ 或 ） out_ddB out_ddB=def_dd2B(in_ddB-useB) 数 据 流 方 程 （ b）结 论 ：1.若 in_ddB def_dd1B ，则 有 变 量 重 复 定 值 ； 若 in_ddB-in_liveBi ， 则 有 变 量 定 值而 未 使 用 ， 或 重 复 定 值 。2.若 out_ddB* ， B*为 出 口 块 ,则 有 变 量 定 值 而 未 使 用 。 程 序 优 化 ： 全 局 常 表 达 式 节 省基 本 块 的 常 表 达 式 节 省问 题 ： 利 用 的 信 息 不 充 分v vvl 定 义 ： 常 量 定 值若 在 块 B中 有 x:=c， 其 中 c是 常 数 ,且 该定 值 是 向 下 暴 露 的 ， ， 则 称 x有 一 个常 量 定 值 ， 记 为 x c。 定 义 ： 注 销 常 量 定 值若 有 x:=E， 则 称 注 销 了 x的 常 量 定 值 。解 决 办 法 定 义 ： 广 义 常 量 定 值若 块 B中 有 向 下 暴 露 的 定 值 x:=E，且 E的 值 可 计 算 为 一 个 常 量 c， 则称 产 生 一 个 广 义 常 量 定 值 x c。 定 义 ： 注 销 广 义 常 量 定 值若 有 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.2in-acB2 = x.1,y.2out-acB2 = 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 程 序 优 化 ： 公 共 子 表 达 式 节 省 定 义 ： 表 达 式 定 值在 块 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_eBi-kill_eBi) in_eBi = Bj pre(Bi)out_eBj Bj为 Bi的 前 驱 需 要 注 意 的 两 个 问 题 形 式 相 同 的 表 达 式 未 必 能 节 省（ 已 解 决 ） 形 式 不 同 的 表 达 式 也 可 能 节 省（ 未 解 决 ） 定 义 ： 等 式 定 值 在 块 B中 ， 若 有 x:=y。 且 从 di+1到 B出 口 无 对 x或 y的 赋 值 ， 则 称 B有 了 一 个 等 式 定 值 。 即 x=yl 定 义 ： 注 销 等 式 定 值 若 有 对 x的 赋 值 x:= ， 则 称 注 销了 所 有 x的 等 式 定 值 。 数 据 流 方 程in_eqB0 = B0为 入 口 块out_eqBi = def_eqBi(in_eqBi-kill_eqBi)in_eqBi = Bj pre(Bi)out_eqBj 利 用 等 式 定 值 和 表 达 式 定 值 ，可 以 解 决 形 式 不 相 同 但 语 义 相 同 的表 达 式 节 省 问 题 。 例 如 ： X:=A*B 1 C:=A 2 Y:=C*B 3 由 2可 知 13等 价 程 序 分 析 技 术第 六 讲 ：一 种 信 息 流 分 析 技 术 一 、 处 理 的 语 言S- skip|V:=e|If e then s else s|If e then s |s; s|While e do s选 择 的 原 因 ： 结 果 定 理 e1S1 S2S3 S4e2 二 、 基 本 方 法1 . 结 构 图S3S4 e1S1 S2 e1S1 2.基 本 定 义定 义 ： 设 S为 一 个 语 句 ， 若 在 S中 有V:=e,一 则 称 S定 义 了 v。 用 Ds表 示 S定 义 的 所 有 变 量 之 集 。设 S为 一 个 语 句 ， 从 G(S)入 口 到 G(S)出 口 存 在 一 条 路 ， 且 在 该 路 上 无 对变 量 x的 赋 值 ， 则 称 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= 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 顺 序 语 句 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 = AB (v , v)| v use(e)，vDA DB) 简 单 条 件 语 句 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 = 公 式 计 算 三 、 应 用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)|vVo=， 则 该 语 句 可用 skip替 换 或 含 有 错 误 。 5.对 循 环 语 句 的 分 析设 有 while e do A， 定 义 一 个 G (S),点 集 为 DA， 边 集 为 A 定 义 ： 稳 定 变 量在 G (S),中 ， 如 果 任 一 环 路 上 的 变 量 都 没有 列 该 变 量 的 路 ， 则 称 该 变 量 是 关 于 S稳 定的例 ： while e doX:=y+1;Y:=z+1;Z:=k+1;K:=m+1. kx yz 若 循 环 体 为x:=y+1;y:=z+1;z:=k+1; k:=m+1定 义 ： 稳 定 变 量 的 稳 定 长 度设 v是 关 于 S稳 定 的 ， 终 止 于 v的 最 长 路 径 长 度称 为 v的 稳 定 长 度 ， 记 为 (v)。x y z k 例while e dox:=y+z;y:=z+1;z:=k+1; (x)=2 定 义 ： 稳 定 表 达 式设 e是 循 环 语 句 s中 的 一 个 表 达 式 ， 若 use(e)中 的 变 量 都 是 稳 定 的 ， 则 称 e是 稳 定 的 。x yz 定 义 ： 稳 定 表 达 式 e的 稳 定 长 度设 e是 关 于 s稳 定 的 ， 其 稳 定 长 度 用 (e)表 示 。 定 义 如 下 ：(e) =max( (v) |vuse(e) )+1。 结 论 ：任 意 一 个 稳 定 变 量 ， 当 循 环 的 次 数 到 达一 个 定 值 （ 稳 定 长 度 +1） 时 ， 其 值 不会 改 变 。任 意 一 个 稳 定 表 达 式 ， 当 循 环 的 次 数 到达 一 个 定 值 （ 稳 定 长 度 +1） 时 ， 其 值不 会 改 变 。若 while e do A中 的 e是 稳 定 的 ， 很有 可 能 出 错 （ 陷 入 死 循 环 ） 。 应 用 ：可 根 据 上 述 分 析 结 果 ， 进 行 应 用 。例 如 ：部 分 求 值 的 程 序 例 化 （ 循 环 展 开 ） 程 序 分 析 技 术第 七 讲程 序 切 片 1 引 言Weiser于 1979年 提 出一 个 程 序 片 S是 由 程序 P中 那 些 可 能 影 响在 某 一 兴 趣 点 n计 算变 量 v的 值 的 部 分 组成 的 。 简 单 例 read a;read b;read c;a=z*b;print b;print a; 二 、 基 本 概 念定 义 一 、 控 制 流 图控 制 流 图 CFG=(N,E,S,e,v)是 一 个 有 向 图 ， 其中 ，N是 结 点 集 ， 程 序 中 的 语 句 和 消 词 属 于 该 集 ，E是 边 集 ， 语 句 n,m之 间 的 控 制 关 系 用 （ n,m） E表 示 ， 记 为 n mS,e分 别 为 开 始 结 点 和 终 点 结 点V E true, false, 谓 词 输 出 边 标 true或 false， 其 它 边 标 of 定 义 二 、 CFG的 路 径 ， 路 径 可 到 达 ，可 实 现 路 径若 任 意 1 i k-1,G中 的 一 个 结 点 序 列P=. 都 满 足 ni ni+1,则 称 P为G的 一 个 路 径 。如 果 G中 存 在 一 条 路 径 则 称 p是 q的可 到 达 的 ， 记 为 q p。G中 的 一 条 路 径 是 程 序 的 一 条 可 执 行 序 列 ，则 称 是 可 实 现 的 。 实 例1 . sum=0 ;2 . mul=1 ;3 . a=1 ;4 . b=read();5 . while(a=b)6 . sum=sum+a;7 . mul=mul*a;8 . a=a+1 ;9 . write(sum); 1 0 . write(mul); 1234 5 67891 0false trueSTARTEXIT 定 义 三 、 必 经 点1.从 开 始 点 s到 n的 所 以 路 径 都 经 过 m， 则称 m为 n的 前 必 经 点 。2.从 n到 出 口 e的 所 以 路 径 都 经 过 m， 则 称m为 n的 后 必 经 点 。 定 义 四 、 控 制 依 赖如 果 结 点 n,m满 足 下 面 条 件 ， 则 称 n 控 制 依赖 m,记 为 n m1.G上 存 在 一 条 路 ， n是 mi的 后 必 经 点 1 i k.2.n不 是 m的 后 必 经 点 。3.若 m是 G的 唯 一 的 开 始 结 点 ， 则 m的 所 有 后必 经 点 都 控 制 依 赖 于 m。cd 定 义 五 、 数 据 依 赖如 果 结 点 m,n满 足 下 面 条 件 ， 则 称 n 数 据 依 赖 于 m,记 n m,1.存 在 一 个 变 量 v,有 vdef(m)ref(m)2.存 在 （ m,m1, mk,n） 且 vdef(mi) i=1, k. 定 义 六 、 程 序 依 赖 图程 序 依 赖 图 PDG=(N ,E ,S ,e )是cfg=(N,E,S,e)的 一 个 变 形 ，其 中 , N =N, S =S, e =e, E =EddEcd 定 义 七 、 传 递 依 赖如 果 m,n满 足 如 下 两 点 ， 则 称 m传 递 依 赖于 n,记 为 m n1.存 在 一 条 路 径p=,n1=n,nk=m,且 每 一ni+1都 控 制 依 赖 或 数 据 依 赖 于 ni2.p是 一 条 可 实 现 的 路 径 。*d 定 义 八 、 程 序 片PDG关 于 阶 段 n的 后 程 序 片 S(n)是 由 所有 n传 递 依 赖 结 点 m组 成 的 集 合S(n)=m|m n, n为 分 片 准 则 *d 三 、 Weiser分 片1 . 分 片 是 从 源 程 序 中 删 除 掉 0 或 多 个 语 句 ，2 . 分 片 准 则 是 一 个 二 元 组 （ n,v） ,其 中 ，n为 PDG中 的 一 个 结 点 ， v是 程 序 变 量的 一 个 子 集 ， 分 片 是 程 序 语 句 的 一 个子 集 ， 满 足 ：a. s是 一 个 有 效 的 程 序 ，b. 对 任 一 个 输 入 ， p中 断 ， s命 令 中 断 ， 且 无 论 怎么 执 行 ， v的 值 不 变 。3 . 这 种 分 片 不 唯 一 （ 最 小 ） 四 、 分 片 分 类1 . 动 态 分 片2 . 静 态 分 片3 . 条 件 分 片