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

已发布作业

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

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

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

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

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

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

  • 2026/09/29 加宽变窄 2026/10/13 上课前 截止

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

      1. x=1;
2. while (x < 100) {
3.   x++;}
4. skip;