CSC4001 Software Engineering

模块一：测试基础、生命周期与需求 (PPT P7-15, P45-47)

这部分考点非常死，主要是概念的对应关系，闭卷考最容易出选择题。

1. 核心概念：什么是测试？

• 学术定义： 评估和验证软件是否完成了预期目标 。

• “说人话” (必记)： 找到尽可能多的 bug (Find as many bugs as possible) 。

• Testing 与 Analysis 的二维分类矩阵 (极易考)：

  • 经验主义 (Empirical)： 跑起来测。分为人工操作的 Manual testing (手动测试) 和机器执行的 Automated testing (自动测试)。
  • 分析主义 (Analytical)： 静态分析代码。人工看代码叫 Inspection (审查)，机器分析叫 Program analysis (程序分析)。

2. V 模型：测试与开发的严格对应 (PPT 核心图)

在瀑布模型 (Waterfall) 中，测试是呈 V 字形与开发阶段一一对应的。你必须把哪种测试对应哪种设计文档死死记住 ：

• 单元测试 (Unit Test)：

  • 对应开发阶段： 详细设计 (Detailed Design Model) 。

  • 目标： 确认独立单元代码逻辑正确 。

  • 测试脚手架的两个核心组件 (必背)：

    • Test Driver (测试驱动)： 主动调起被测模块，传入数据，并负责测试环境的初始化与清理 (setup & clean-up) 。

    • Test Stub (测试桩)： 被动等待调用。因为其他模块还没写好，用它来充当一个临时的替代品，直接返回假数据 (Mock/fake data) 。

• 集成测试 (Integration Test)：

  • 对应开发阶段： 软件架构 (Software Architecture) 。

  • 目标： 不看具体代码细节，专门测试子系统之间的接口 (interfaces) 。

• 系统测试 (System Test)：

  • 对应开发阶段： 需求规格说明 (Requirements Specification) 。

  • 目标： 验证整个系统是否满足了所有的功能性和非功能性需求 。

3. 测试的四大步骤 (PPT P15)

这四个步骤是有严格先后顺序的 ：

1. Select what will be tested：决定测系统的哪些部分 。

2. Select test strategy：决定测试策略（怎么搞出测试数据） 。

3. Define test cases：明确具体的测试用例和步骤 。

4. Create test oracle (创建测试预言)：明确预期结果是什么。注意，预期结果必须在执行测试之前就定义好 。

4. 需求分析的边界 (PPT P45-47)

闭卷考最喜欢在这给你挖坑，让你判断什么属于需求，什么不属于。

• 最高原则： 需求只描述用户视角的“做什么 (what)”，坚决不涉及代码视角的“怎么做 (how)” 。

• 属于需求的 (Part of)： 功能性、用户交互、错误处理、环境条件与接口 。

• 绝对不属于需求的 (Not part of)： 系统结构、实现技术、系统设计、开发方法学 。

• 需求的分类：

  • 功能性 (Functional)： 软件到底该做啥 。

  • 非功能性 (Nonfunctional)： 外部接口、性能指标 (速度、响应时间)、质量属性 (正确性、可移植性、可维护性等)、设计约束 (标准、运行环境) 。

模块二：控制流图 (CFG) 与编译器 (PPT P17-P33)

1. 核心基石：什么是基本块 (Basic Block, BB)？

你要画控制流图，第一步就是把代码切分成一个个“基本块”。闭卷考特别喜欢考基本块的定义和切分规则。

• 死记定义： 只有一个入口点（One entry point）和一个出口点（One exit point）的连续代码序列 。

• 核心特征： 只要基本块的第一条指令执行了，里面的剩下所有指令都必定会被执行 。

• 怎么找基本块？（三步找 Leader 法则，画图大题必用）： 你必须先找出所有基本块的“头头”（Leader），一个 Leader 带着它后面的小弟，直到遇到下一个 Leader，这就组成了一个基本块 。

  • 法则 1： 整个程序的第一条指令必定是 Leader 。

  • 法则 2： 任何一个“跳转目标”（被别人 goto 或 if 指向的指令）必定是 Leader 。

  • 法则 3： 紧跟在“跳转指令”（如 if、goto、return、break）后面的那条指令，必定是 Leader 。

2. 画出控制流图 (Control Flow Graph, CFG)

找出基本块后，把它们连起来就是 CFG。

• 节点 (Nodes)： 刚才切分出来的每一个基本块 (BB) 就是一个节点 。

• 连线 (Edges)： 怎么连箭头？

  • 如果有跳转指令（如 goto B），就从当前块画个箭头指向 B 。

  • 如果代码是按顺序往下挨着写的，并且当前块没有无条件跳转（比如没有 goto 强行跳走），那就顺势画个箭头指向紧挨着的下一个块 。

• 送分细节： 考试画图时，千万别忘了自己加上 Entry 和 Exit 两个节点 。从 Entry 指向第一个 BB，从所有可能结束的 BB 指向 Exit。

3. 测试覆盖率 (Test Coverage)

看着 CFG，我们需要衡量测试用例到底跑得多彻底。记住这四个公式：

• 语句覆盖 (Statement Coverage)： 执行过的语句数 / 总语句数 。

• 分支覆盖 (Branch Coverage)： 执行过的分支数 / 总分支数 。（注意：包含 if 的 True 和 False 两条路都要走一遍）。

• 路径覆盖 (Path Coverage)： 执行过的路径数 / 总路径数 。（最严格的覆盖，如果有循环，路径可能是无限的，所以极难达到 100%）。

• 循环覆盖 (Loop Coverage)： 针对循环，要求分别执行 0次、1次、大于1次，公式是：执行过的循环状态 / (总循环数 * 3) 。

4. 编译器的流水线 (The Compiler Pipeline)

选择题经常会考各个阶段的对应关系，你只需要记住这个“一一对应”的匹配表 ：

• Scanner (扫描器) $\rightarrow$ Lexical Analysis (词法分析) $\rightarrow$ 输出 Tokens (词法单元)

  • 底层依赖： 正则表达式 (Regular Expression) 。
  • 查什么错： 查有没有拼写错误（图例："You $\rightarrow$ goouojd"） 。

• Parser (解析器) $\rightarrow$ Syntax Analysis (语法分析) $\rightarrow$ 输出 AST (抽象语法树)

  • 底层依赖： 上下文无关文法 (Context-Free Grammar) 。
  • 查什么错： 查语法结构对不对（图例："Like your hair I"，单词都对，但连起来不像句英语） 。

• Type Checker (类型检查器) $\rightarrow$ Semantic Analysis (语义分析) $\rightarrow$ 输出 Decorated AST (带标注的抽象语法树)

  • 底层依赖： 属性文法 (Attribute Grammar) 。
  • 查什么错： 查逻辑和类型匹配不匹配（图例："Apples eat you"，语法是对的，但语义逻辑是错的） 。

• Translator (翻译器) $\rightarrow$ 输出 IR (中间表示) 。

• Code Generator (代码生成器) $\rightarrow$ 输出 Machine Code (机器码)

• 重点考点： 我们学的静态分析 (Static Analysis) 和代码优化，就是插在生成 Machine Code 之前的这一步，并且是完全基于 IR 进行的 。

5. AST vs. IR 的终极对决 (核心考点)

这张图下半部分列出了 AST 和 IR 的区别，这是闭卷考非常容易出判断题/选择题的地方。把下面这几个对比死死记住 ：

AST (Abstract Syntax Tree / 抽象语法树)：

• 层级： High-level (高级)，非常接近你写的源代码语法结构 。

• 依赖性： Usually language dependent (通常依赖于具体的编程语言)。比如 Java 的 AST 和 Python 的 AST 长得完全不一样 。

• 强项： 适合做快速的类型检查 (fast type checking) 。

• 致命弱点 (必考)： Lack of control flow information (缺乏控制流信息) 。它只是一棵静态的语法树，你很难直观看出程序是怎么“跳转”的。 IR (Intermediate Representation / 中间表示)：

• 层级： Low-level (低级)，非常接近底层的机器码 。

• 依赖性： Usually language independent (通常独立于具体的编程语言)。不管是 C++ 还是 Java，最后都可以翻译成统一风格的 IR 。

• 结构： Compact and uniform (紧凑且统一) 。最常见的形式就是图里展示的 "3-address" form (三地址码)，即一行代码最多只有三个变量参与运算，比如 t1 = a [ i ] 。

• 最强优势 (必考)： Contains control flow information (包含控制流信息) 。因为 IR 里有大量的 goto 和 if goto 语句（比如图里的 if t1 < v goto 1），程序的跳转逻辑一目了然 。

• 终极结论： 因为 IR 有明确的跳转信息，所以 IR 通常被认为是进行静态分析的基础 (the basis for static analysis) 。你画控制流图 (CFG)、切分基本块 (Basic Blocks)，全都是基于 IR 来做的。

总结一下： 看到 AST 就联想“树形结构、方便查类型、没法看跳转”；看到 IR（尤其是三地址码）就联想“一行行代码、带有 goto 跳转、是静态分析和画 CFG 的地基”。

模块三：不同测试类型

这五种测试方法中，Mutation Testing (变异测试) 是用来评估测试用例质量的，而后面四种（Differential, Metamorphic, Intramorphic, Retromorphic）全都是为了解决同一个痛点：Test Oracle 问题（即当你不知道绝对正确的输出应该是什么时，如何判断程序算得对不对）。

下面为你详细拆解这五种测试的核心逻辑和区别：

1. Mutation Testing (变异测试)

• 核心目标： 评估你写的测试用例集（Test Suite）到底有多强、够不够彻底 。它的目标不是找代码的 Bug，而是找“测试用例的漏洞”。
• 怎么做：
  1. 在原程序 (Original Program) 中故意引入一个微小的错误（Fault Introduction），生成一个变异体 (Mutant Program) 。
  2. 把你的测试用例同时跑在原程序和变异体上 。
  3. 如果测试用例在这两个程序上跑出的结果不一样（即测试用例报错了），说明测试用例成功杀死 (KILLED) 了这个变异体 。
• 核心假设 (Coupling Effect)： 如果一个测试用例极其敏锐，能发现那些非常简单的错误，那么它也一定能发现由这些简单错误组合而成的复杂大 Bug 。
• 强弱之分：
  • 弱杀死 (Weakly killing)： 测试用例跑完变异的那行代码后，程序的内部状态和原版不一样了（满足 Reachability 和 Infection） 。
  • 强杀死 (Strongly killing)： 这个错误的内部状态必须一路传播下去，导致最终的输出结果和原版不一样（即 $P(t) != m(t)$） 。

2. Differential Testing (差异测试)

• 应用场景： 当你不知道正确答案是什么，但你手头有好几个功能相同的不同软件/不同实现版本时。
• 怎么做： 给这些可以互相替换的程序（比如 $P_1, P_2, P_3$）喂入完全相同的输入 $I$ 。
• 怎么判断对错： 观察它们的输出（$O_1, O_2, O_3$） 。如果大家都输出一样的结果，大概率是对的；如果其中一个输出与众不同，那这个程序大概率有 Bug。它们互为对方的裁判 (Oracle for each other) 。
• 例子： 测试一个新的 C++ 编译器，就给它和 GCC、Clang 喂同一段 C++ 代码，看编译出来的行为是否一致。

3. Metamorphic Testing (蜕变测试)

• 应用场景： 针对单个程序，你不知道单一输入的正确答案，但你知道输入之间如果发生某种变化，输出也应该发生相应的变化（这叫蜕变关系）。
• 怎么做：
  1. 给程序 $P$ 一个初始输入 $I$，得到输出 $O$ 。
  2. 根据已知的数学/逻辑关系，把输入 $I$ 修改成衍生输入 $I'$ (Derived follow-up input) 。
  3. 将 $I'$ 喂给同一个程序 $P$，得到输出 $O'$ 。
• 怎么判断对错： 检查 $O$ 和 $O'$ 之间的关系是否符合预期（它们互为对方的 Oracle） 。
• 例子： 测试计算 $\sin(x)$ 的函数。你不知道 $\sin(1.23)$ 是多少，但你知道 $\sin(x) = \sin(x + 2\pi)$。所以 $I=1.23$，$I' = 1.23 + 2\pi$，如果两次输出结果不一样，函数就写错了。

4. Intramorphic Testing (同构测试 / 内变异测试)

• 核心逻辑： 它是变异测试和蜕变测试思想的一种结合。它控制变量的方法是改变程序本身，而不改变输入。
• 怎么做：
  1. 准备一个输入 $I$ 。
  2. 将输入 $I$ 喂给原程序 $P$，得到输出 $O$ 。
  3. 对原程序进行某种等价修改（比如代码重构、或者开启了某种编译器优化），得到修改后的程序 $P'$ (Modified program) 。
  4. 将同一个输入 $I$ 喂给修改后的程序 $P'$，得到输出 $O''$ 。
• 怎么判断对错： 如果程序修改（$P \to P'$）在逻辑上是等价的，那么输出 $O$ 和 $O''$ 必须完全一致（互为 Oracle） 。

5. Retromorphic Testing (逆向变形测试 / 反向测试)

• 应用场景： 适用于那些有着明确“正向”和“逆向”处理流程的系统，比如加密/解密、压缩/解压、数据序列化/反序列化。
• 怎么做： 涉及两个相反的程序 $P$ 和 $Q$。其中 $P$ 将数据从 $M_1$ 转换为 $M_2$，$Q$ 将数据从 $M_2'$ 转换回 $M_1'$ 。
  1. 将初始数据 $M_1$ 输入给程序 $P$，得到输出 $M_2$ 。
  2. 在中间环节，对 $M_2$ 进行合法的修改 (Modify $M_2$ to $M_2'$) 。
  3. 将修改后的 $M_2'$ 输入给逆向程序 $Q$，得到输出 $M_1'$ 。
• 怎么判断对错： 我们把最初的输入 $M_1$ 和经过一正一反处理后的结果 $M_1'$ 放在一起对比 (Oracle between $M_1$ and $M_1'$) 。如果它们符合预期的对应关系，说明正反向程序协同工作正常。

考前速记防混淆口诀：

• Mutation: 改代码，看测试用例能不能报错（测“测试”）。
• Differential: 同一个输入喂给多个程序，对比大家的结果（找不同）。
• Metamorphic: 一个程序喂入两个相关的输入，对比输出的关系（抓规律）。
• Intramorphic: 同一个输入喂给原程序和重构后的程序，对比结果（查等价）。
• Retromorphic: 经过正向程序加工再经过反向程序还原，对比源头和结果（测可逆）。

模块四：符号执行 (PPT P34-44, P8-10 往年卷)

1. 符号执行 (Symbolic Execution) —— 10分必考大题！

传统测试是给变量赋具体的值（如 $x=1$），而符号执行是把变量变成代数符号（如 $x=\alpha$），让程序去推导数学表达式 。这道 10 分大题的套路非常死，严格按以下三步走：

• 核心概念 1：符号状态 (Symbolic State) 随着代码一行行往下走，变量的代数式会不断变化。比如 x = a，下一行 y = x + 1，那么在符号状态里 $y$ 就等于 $a + 1$ 。

• 核心概念 2：路径约束 (Path Constraint, PC) 遇到 if 语句时，只有满足特定条件才能走进去。你把一路走来的 if 条件用逻辑与（$&&$）连起来，就是这条路径的“通关密码” 。

期末大题解题套路 (参考往年卷 Q7)：

1. 数路径： 题目会问有几条路径能到达 ERROR。你就看 ERROR 外面包着几个 if，画一画分支，数清楚到底有几条逻辑线能走到那一步 。

2. 写约束 (极易出错的地方！)： 把初始输入设为符号（比如 $a_0, b_0$）。一定要注意变量被覆盖的情况！

• 错误示范： 看到 if (x > 10)，直接写约束 $x > 10$。
• 正确做法： 往回找 $x$ 是怎么算出来的。如果前面写着 $x = 2 * a_0 + b_0$，那约束必须写成 $2 * a_0 + b_0 > 10$。路径约束里只能包含初始的输入符号，不能有中间变量 。

3. 判断可解性 (Satisfiability)： 看着你写出的一堆不等式/等式，问自己：这套方程有解吗？

• 有解就是 Satisfiable (T)。然后你随便猜一组数字（比如 $a_0=1, b_0=2$）写上去，这就是生成的高覆盖率 Test Input 。

• 如果条件互相矛盾（比如 $a > 5 && a < 3$），那就是 Unsatisfiable (F)，说明这条路径在现实中是不可能走通的（死代码） 。

3. 混合执行 (Concolic Execution) / 动态符号执行

符号执行虽然厉害，但遇到非常复杂的数学运算（比如哈希、加密）或者外部库调用时，方程根本解不出来 。

• 应对策略： Concolic = Concrete (具体) + Symbolic (符号) 。

• 考点： 它是先随机给一个具体的真实输入（比如 $x=3$）跑一遍，把沿途的条件收集起来。遇到解不开的复杂约束，直接用具体的真实数值替换掉，强行解开并探索新的分支。它极大扩展了纯符号执行的能力边界 。

符号执行的逻辑推导是软件分析里最经典的题型。到了考场上，遇到这种题千万别慌，拿笔在草稿纸上把变量 $x, y, z$ 的代数式一步步列出来，最后把 if 里的变量替换掉，稳拿 10 分。

模块五：建模、UML 与有限状态机 (PPT P48-P55)

这部分的本质是建模 (Modeling)。闭卷考选择题喜欢考建模的目的：建模是建立现实的抽象 (Abstraction of reality)，为了应对复杂性 (dealing with complexity) 而忽略无关细节 (ignore irrelevant details) 。

1. UML 的两大阵营 (选择题必考)

UML 图分为两派，选择题极大概率会给你几个图的名字，问你哪个是静态的，哪个是动态的 ：

• 静态/结构图 (Static/Structural)： 描述系统长什么样。类图 (Class Diagram) 是绝对的核心代表 。

• 动态/行为图 (Dynamic/Behavioral)： 描述系统怎么动。记住三大代表：用例图 (Use Case Diagram)、时序图 (Sequence Diagram)、状态机图 (State Machine Diagram) 。

2. 怎么画 UML 类图 (Class Diagram) - 大题考点

类图非常死板，就是一个分成三层的长方形 ：

• 第一层 (Name)： 类名。这是唯一强制要求必须有的信息 。

• 第二层 (Attributes)： 属性/状态。格式是 变量名: 类型（比如 zone2price: Table） 。

• 第三层 (Operations)： 方法/行为。格式是 方法名(参数): 返回值类型（比如 getPrice(z: Zone): Price） 。

3. 怎么画 UML 时序图 (Sequence Diagram) - 大题考点

时序图用来描述对象之间是如何按时间顺序交互的。闭卷考时，你需要把题目给的一大段文字交互步骤翻译成这个图 ：

• 参与者/对象 (Actors and objects)： 画在最顶部，作为列的表头（比如一个小人代表 :Client，一个方框代表 :Terminal） 。

• 时间线 (Time)： 时间是从上往下流动的 。

• 生命线 (Lifelines)： 从顶部的对象往下画的虚线 。

• 激活期 (Activations)： 虚线上的细长矩形，表示这个对象这段时间正在干活 。

• 消息 (Messages)： 对象之间传递的动作，用带箭头的实线表示（比如 insertCard()），从一个生命线指向另一个生命线 。

4. 怎么画有限状态机 (FSM) - 大题考点

FSM 专门用来描述系统的控制层面 (control aspects) 。系统有有限个状态，遇到不同的事件/输入就会在状态之间跳来跳去。

• 基本画法规范 (极易漏掉扣分)：

  • 初始状态 (Initial state)： 必须有一个箭头从虚空中指过来，通常标记为 $q_0$ 。
  • 最终/接受状态 (Final state)： 必须画成双层圆圈（比如 $q_f$），表示到这里任务成功结束 。
  • 状态跳转： 两个圆圈之间的箭头，上面标明是因为什么输入（比如输入了字母 e，或投入了 5p 硬币）才跳转的 。

• 经典考法 (FSM as Recognizers)： PPT 里给的经典例子是“识别编程语言的标识符 (变量名)”。规则是：必须以字母开头，后面可以跟字母或数字 。

  • 怎么画： 初始状态 $q_0$ 遇到 <letter> 跳到 $q_1$（此时变成了接受状态，因为单字母也是合法变量名）；$q_1$ 遇到 <letter> 或 <digit> 自己绕圈（指向自己）；如果中途遇到任何非法字符，就走到死胡同 。

模块六：静态分析、数据流与格理论 (PPT P56-P83)

一、 静态分析的极限与妥协 (Static Analysis Limits)

静态分析是在不运行程序的情况下推断其行为。为什么我们不能做一个完美的静态分析工具？

核心在于 Rice's Theorem (莱斯定理)：任何关于图灵完备语言的非平凡属性（比如有没有除零错误、会不会死循环），都是不可判定 (Undecidable) 的 。

既然得不到完美答案，我们就必须在Soundness (健全性) 和 Completeness (完备性) 之间做数学上的妥协：

• Sound (健全 / 宁杀错不放过)：包含所有真实的可能，允许误报 (False Positives)，但绝不漏报。数学表达为 $Truth \subseteq Sound$ 。

• Complete (完备 / 宁漏网不冤枉)：报出来的全是真的，允许漏报 (False Negatives)，但绝不误报。数学表达为 $Complete \subseteq Truth$ 。

绝大多数静态分析为了保证安全（比如排查漏洞），选择的是 Soundness。其核心方法论是：Abstraction (抽象) + Over-approximation (过度近似) 。

二、 数据流分析框架 (Data Flow Analysis Framework)

数据流分析旨在计算程序在每个控制流节点（Basic Block）的输入状态 ($IN$) 和输出状态 ($OUT$)。一个完整的数据流分析框架可以形式化为一个三元组 $(D, L, F)$ ：

• $D$: 数据流的方向 (Direction, Forwards 或 Backwards)。
• $L$: 包含定义域值集合 $V$ 以及交/并算子的格 (Lattice)。
• $F$: 状态转移函数族 (Transfer functions, $V \rightarrow V$)。

何教授重点考以下三大经典数据流分析的公式推导 ：

1. 到达定值 (Reaching Definitions, RD)

目标：判断某个赋值语句（Definition）能否未经覆盖地到达某一点。

• 方向：Forwards (向前) 。

• 算子 (Meet Operator)：May (可能) $\Rightarrow$ 集合并集 ($\cup$) 。

• 转移方程 (Transfer Function)：

$$OUT[B] = gen_B \cup (IN[B] - kill_B)$$

(解释：流出基本块B的定值 = B自己产生的新定值 $\cup$ (流进B的定值 - 被B中途覆盖掉的定值))

• 控制流交汇 (Control Flow Meet)：

$$IN[B] = \bigcup_{P \in pred(B)} OUT[P]$$

(解释：流入B的定值 = B的所有前驱节点 P 流出定值的总和)

• 边界与初始化：

$$OUT[entry] = \emptyset$$

$$\forall B \neq entry, OUT[B] = \emptyset$$

2. 活跃变量 (Live Variables, LV)

目标：判断一个变量在某点的值，在未来是否会被使用。

• 方向：Backwards (向后) 。

• 算子 (Meet Operator)：May (可能) $\Rightarrow$ 集合并集 ($\cup$) 。

• 转移方程 (Transfer Function)：注意 $IN$ 和 $OUT$ 反过来了！

$$IN[B] = use_B \cup (OUT[B] - def_B)$$

(解释：流入B的活跃变量 = B中使用的变量 $\cup$ (流出B的活跃变量 - 在B中被重新赋值的变量))

• 控制流交汇 (Control Flow Meet)：

$$OUT[B] = \bigcup_{S \in succ(B)} IN[S]$$

(解释：流出B的活跃变量 = B的所有后继节点 S 需求变量的总和)

• 边界与初始化：

$$IN[exit] = \emptyset$$

$$\forall B \neq exit, IN[B] = \emptyset$$

3. 可用表达式 (Available Expressions, AE)

目标：判断在某一点，某个数学表达式（如 $x+y$）是否已经被计算过，且其操作数未被修改。

• 方向：Forwards (向前) 。

• 算子 (Meet Operator)：Must (必须) $\Rightarrow$ 集合交集 ($\cap$) 。

• 转移方程 (Transfer Function)：

$$OUT[B] = gen_B \cup (IN[B] - kill_B)$$

• 控制流交汇 (Control Flow Meet)：注意这里是交集！

$$IN[B] = \bigcap_{P \in pred(B)} OUT[P]$$

(解释：必须所有前驱节点都计算过该表达式，它才算“可用”)

• 边界与初始化 (极易出错考点)：

$$OUT[entry] = \emptyset$$

$$\forall B \neq entry, OUT[B] = U$$

(全集 Universal Set) (解释：由于求的是交集，如果初始化为 $\emptyset$，那么任何集合跟它取交集都会变成 $\emptyset$。所以必须初始化为全集 $U$)

三、 数学地基：偏序集、格与不动点定理 (Poset, Lattice & Fixed-Point)

迭代算法为什么能停下来？凭什么保证算出来的结果是对的？这需要数学理论支撑。考卷上大概率会出理论概念判定。

1. 偏序集 (Partially Ordered Set, Poset)

定义为一个二元组 $(P, \sqsubseteq)$。要成为偏序集，关系 $\sqsubseteq$ 必须满足三大公理 ：

1. Reflexivity (自反性): $\forall x \in P, x \sqsubseteq x$ 。

2. Antisymmetry (反对称性): $\forall x, y \in P, x \sqsubseteq y \wedge y \sqsubseteq x \Rightarrow x = y$ 。

3. Transitivity (传递性): $\forall x, y, z \in P, x \sqsubseteq y \wedge y \sqsubseteq z \Rightarrow x \sqsubseteq z$ 。

2. 上下界与格 (Bounds & Lattice)

• Least Upper Bound (lub / join / $\sqcup$): 集合 $S$ 的最小上界 。

• Greatest Lower Bound (glb / meet / $\sqcap$): 集合 $S$ 的最大下界 。

• Lattice (格): 在偏序集 $(P, \sqsubseteq)$ 中，如果任意两个元素都存在 $\sqcup$ 和 $\sqcap$，它就是格 。

• Complete Lattice (完全格): 如果任意子集 $S$ 都存在 $\sqcup$ 和 $\sqcap$，它就是完全格。完全格必然存在最大元素 Top ($\top$) 和最小元素 Bottom ($\bot$) 。

3. 不动点定理 (Fixed-Point Theorem) - 核心考点

不动点定理保证了数据流分析必定会收敛。 前提条件 ：

1. 给定一个完全格 $(L, \sqsubseteq)$，且 $L$ 是有限的 (finite)。
2. 状态转移函数 $f: L \rightarrow L$ 是单调的 (Monotonic)：

$$x \sqsubseteq y \Rightarrow f(x) \sqsubseteq f(y)$$

结论与迭代公式 ：

• 最小不动点 (Least Fixed Point)：通过从底端不断向上迭代得到：

$$f(\bot), f(f(\bot)), \dots, f^k(\bot)$$

直到 $f^k(\bot) = f^{k-1}(\bot)$

• 最大不动点 (Greatest Fixed Point)：通过从顶端不断向下迭代得到：

$$f(\top), f(f(\top)), \dots, f^k(\top)$$

直到 $f^k(\top) = f^{k-1}(\top)$

(注：May 分析通常求最小不动点，Must 分析通常求最大不动点 。)

最大迭代次数估算 ： 如果格的高度为 $h$ (从 Top 到 Bottom 的最长路径长度)，CFG 有 $k$ 个节点，那么算法最多经过 $i = h \times k$ 次迭代就能到达不动点 。

四、 算法优化：Worklist Algorithm

普通的迭代算法（Iterative Algorithm）非常低效，因为只要有一个节点的 $OUT$ 变了，下一个循环就会把所有节点重新算一遍。

Worklist 算法的优化逻辑：只有当节点 $B$ 的输出改变时，才将受它影响的节点（即它的后继节点）加入待处理队列 。

核心伪代码逻辑 (以 Forward 分析为例) ：

1. 将所有节点加入 Worklist。
2. while (Worklist is not empty):

• 从队列中取出一个块 $B$。
• 记录 old_OUT = OUT[B]。
• 计算 IN[B] 和新的 OUT[B]。
• 核心判断：if (old_OUT != OUT[B])
• 将 $B$ 的所有后继节点 (successors) 重新加入 Worklist。