• 作业独立完成，和其他同学讨论的部分需在提交时说明。
  • 所有作业均在北大教学网上提交。如提交 PDF 文件，文件标题请以“学号-姓名-软分第x次作业”的格式书写。
  • 在无特殊说明的情况下，当周作业需在下一周周二上课之前提交至教学网。
  • 作业每道题目 10 分，晚于截止时间的作业，其最终得分将会乘以 0.6。
  • 课程作业计入总评 20 分，根据完成质量评分。

已发布作业

  • 第1次作业 2026/09/08 课程介绍 2026/09/22 上课前 截止
    • 假设我们设计一个程序分析来检测程序是否会抛出异常。该分析遍历输入空间中每一个输入，然后执行100条语句，看程序是否抛出异常。对于有限输入空间的程序，该分析是精确分析、上近似、下近似还是不属于以上三类？为什么？
    • 假设我们把符号分析的抽象域改成{自然数，负，槑}三个值，其中自然数表示所有正数和零，请写出加法和乘法的计算规则，并给出一个式子，在该抽象域上得到的结果不如{正，负，零，槑}精确。
  • 第2次作业 2026/09/15 程序设计语言基础知识 2026/09/22 上课前 截止
    • 课件中给出的 IMP 程序控制流图构建算法还有两个问题：（1）对于判断结点，出边没有区分是 true 还是 false；（2）对于基本块中的语句没有进行合并。请针对上面两个问题修改算法。注意可能既需要修改 f 函数的定义，也需要修改表示控制流图的数据结构。
  • 第3次作业 2026/09/17 数据流分析：示例 2026/09/29 上课前 截止
    • 繁忙表达式分析（very busy expression）

      繁忙表达式：从执行某个程序节点之前开始，在其中变量被修改之前，在所有终止执行中一定会被读取的表达式。如果从某个程序点开始的所有执行都不终止，则可返回任意结果。

      繁忙表达式分析：找到每个程序节点的繁忙表达式，要求下近似。例如：

      1. if (a > b)
2.   x=b-a
3.   y=x-y+(a+b+b)
4. else
5.   y=b-a
6. x=x-y+(a+b)

      在第一行，b-a、a+b、a>b 为繁忙表达式。

      请设计繁忙表达式分析。请给出分析方向、抽象域设计（抽象值集合、γ、初值）、转换函数、合并操作，并简要讨论正确性。

  • 第4次作业 2026/09/22 数据流分析：框架和扩展 2026/09/29 上课前 截止

    • 整数采用区间抽象，布尔值采用 {⊥, 真, 假, 值}。整数是数学定义，无上下界；区间抽象 [a, b] 表示大于等于 a、小于等于 b 的整数集合，其中 a 和 b 为任意整数。

      请针对逻辑与、逻辑非、大于、加法这四种操作，设计参考输入的反向抽象语义，要求尽可能精确。

      同时分析：基于你设计的反向语义，对任意表达式是否能保证收敛。表达式中可包含变量、常量和以上四种操作符。

  • 第5次作业 2026/09/29 加宽变窄 2026/10/13 上课前 截止

    • 对于下面程序，如果我们在条件分支的地方加上节点根据条件压缩抽象值，采用今天课上讲的加宽算子进行区间分析，每条语句对应的 OUT 值是什么？如果加上变窄，对应的 OUT 值是什么？

      1. x=1;
2. while (x < 100) {
3.   x++;}
4. skip;
  • 第6次作业 2026/10/15 抽象解释和其他模型（续） 2026/10/20 上课前 截止

    • 一个用 Datalog 编写的符号分析，在应用到下面程序上时，产生了一部分规则，请补全剩余的规则，并分析相比之前的符号分析，精度是否一样？如果不一样，请举一个例子。分析规则和结果中不出现槑和 ⊥。

      1. x-=1;
2. y+=1;
3. while(y < z) {
4.   x *= -100;
5.   y += 1;}

      输入：x 为负，y 为零，z 为正。求输出的符号。

      out(x, entry, 负)
out(y, entry, 零)
out(z, entry, 正)
out(x, exit, ?)
out(y, exit, ?)
out(z, exit, ?)
edge(1, 2), edge(2, 3), edge(5, 3), edge(3, 4),
edge(4, 5), edge(entry, 1), edge(3, exit)
out(x, 1, 正) :- in(x, 1, 正)
out(x, 1, 零) :- in(x, 1, 正)
out(x, 1, 负) :- in(x, 1, 负)
out(x, 1, 负) :- in(x, 1, 零)
out(v, 3, 甲) :- in(v, 3, 甲)
    注：只是将如上程序手动转换成 Datalog 规则，不用编写针对任意程序通用的分析。
  • 第7次作业 2026/10/20 过程间分析 2026/10/27 上课前 截止
    • 过程间可达定值分析

      设计一个过程间的可达定值分析。给出半格定义和变换函数定义，特别是 call 语句和 return 语句的变换函数。

      参数传递不认为是定值。例如，下面程序中，标号 2 位置的 c 是由标号 1 的语句定值的，而不是标号 3 的语句定值的。

      void main() {
  int a = 100; //1
  b(a) //3
}
void b(int c) {
  print(c); //2
}

      假设过程调用时不能传表达式，只能传变量，即 f(a+b) 不合法，f(a) 合法。

      根据上述定义的可达定值分析，采用基于克隆的方法分析下面的程序，k 至少应该设置成多少，分析结果才能和精确的上下文敏感分析等价？

      int g;
void main() {
  int a = 10;
  g = a + 1;
  h(a); h(a);
}
void h(int a) {
  x(a); g++; x(a);
}
void x(int a) {
  output(a);
}
    • 符号分析与 CFL 可达性

      对下面的程序做符号分析，抽象域参考下方绘图基础，考虑条件压缩函数，画出 CFL-reachability 的图。要求根据输入值 x 的符号，在这个程序上能分析出返回值完全精确的符号结果。

      一般性的符号分析无法转为 CFL 可达性，但本程序只涉及一元操作，所以可以用 CFL 可达性分析。

      int main() {
  ...
  assert(y > 0 && z < 0);
  f(y); f(z);
}
int f(int x) {
  if (x < 0) {
    x = x + 1;
    if (x == 0) x = 2025;
    else x = f(x);
  }
  else if (x > 0) {
    x = x - 1;
    if (x == 0) x = -2025;
    else x = f(x);
  }
  else x = 0;
  return x;
}

      假设 int 是无界整数，分析是否存在一个足够大的 k，使得基于克隆的方法在 f 的最后一行返回精确的结果。如果存在，请给出这样的 k；如果不存在，请给出简要证明。请针对“调用位置作为上下文”和“函数名称作为上下文”两种情况分别分析。

      符号分析的绘图基础：x、y、z 的符号节点及程序控制流

      图中每组三个节点从左到右依次表示 <0、=0、>0 的情况；蓝、紫、绿分别表示 x、y、z。浅灰色边仅表示控制流，不表示 CFL-reachability 图中的任何边；为使图更清晰，图中省略了部分节点和边。

    原图中的常数 2024 和 -2024 分别按上面程序中的 2025 和 -2025 读取。