静态程序分析学习笔记(2)

1. TIP语言语法

TIP语言是本书应用于教学的语言，基本语法如下：

基本表达式

整数和变量:
```
Exp ::= Int | Id
```

算术操作:

Exp ::= Exp + Exp | Exp - Exp | Exp * Exp | Exp / Exp

比较操作:
```
Exp ::= Exp > Exp | Exp == Exp
```
其他表达式:
```
Exp ::= ( Exp ) | input
```

指针操作

分配和引用:
```
Exp ::= alloc Exp | & Id | * Exp | null
```
存储操作:
```
Stm ::= * Exp = Exp;
```

记录操作（类似结构体）

创建和读取:

Exp ::= { Id : Exp , ..., Id : Exp } | Exp . Id

更新:

Stm ::= Id . Id = Exp; | ( * Exp ) . Id = Exp;

语句

赋值和输出:
```
Stm ::= Id = Exp; | output Exp;
```

控制结构:

Stm ::= Stm Stm
   | if ( Exp ) { Stm } else { Stm }
   | while ( Exp ) { Stm }

函数

函数声明:

Fun ::= Id ( Id , ..., Id ) { var Id , ..., Id; Stm return Exp; }

函数调用:

Exp ::= Id ( Exp, ..., Exp ) | Exp ( Exp , ..., Exp )

程序结构

程序:
```
Prog ::= Fun ... Fun
```
main函数作为程序的入口，参数从输入流中提供，返回值输出到输出流。

示例程序

迭代计算阶乘:

iterate(n) {
  var f;
  f = 1;
  while (n > 0) {
      f = f * n;
      n = n - 1;
  }
  return f;
}

递归计算阶乘:

recurse(n) {
  var f;
  if (n == 0) {
      f = 1;
  } else {
      f = n * recurse(n - 1);
  }
  return f;
}

复杂的计算阶乘:

foo(p, x) {
  var f, q;
  if (*p == 0) {
      f = 1;
  } else {
      q = alloc 0;
      *q = (*p) - 1;
      f = (*p) * (x(q, x));
  }
  return f;
}

main() {
  var n;
  n = input;
  return foo(&n, foo);
}

2. 规范化 / 中间表示（IR）

在编译器设计和程序分析中，规范化是一种将程序转换为语法上更简单或更标准形式的过程。这样做的目的是简化分析和优化的实现。这种标准形式通常称为中间表示（Intermediate Representation，IR）。中间表示是一种抽象的、标准化的代码形式，介于高级编程语言的源代码和低级机器代码之间。

表达式的规范化

表达式的规范化（Flattening expressions）是将复杂的表达式分解为一系列简单的语句，每个语句只执行一个操作。这种形式通常称为A-正常形式（A-Normal Form，ANF）。

例如，考虑以下C表达式：

x = f(y + 3) * 5;

这个表达式可以被规范化为：

t1 = y + 3; t2 = f(t1); x = t2 * 5;

指针操作的规范化

指针操作的规范化旨在将复杂的指针操作分解为简单的加载和存储操作。例如，考虑以下指针操作：

x = (**f)(g() + h());

这个操作可以规范化为：

t1 = g(); t2 = h(); t3 = t1 + t2; t4 = *f; t5 = *t4; x = t5(t3);

声明的唯一性

为了避免变量和函数名的冲突，我们可以对程序中的所有标识符进行重命名，使得每个标识符在整个程序中都是唯一的。例如，考虑以下C程序：

int main() {
    int x = 10;
    int y = 20;
    return x + y;
}

int foo() {
    int x = 30;
    return x;
}

在规范化过程中，我们可以对变量x进行重命名，使得其在每个作用域中都是唯一的：

int main() {
    int x1 = 10;
    int y = 20;
    return x1 + y;
}

int foo() {
    int x2 = 30;
    return x2;
}

3. 抽象语法树(AST)

抽象语法树（AST）是一种分层的树状数据结构，用于表示程序的语法结构。AST省略了源代码中的一些冗余细节，仅保留语法元素的基本结构，使得对程序的分析和处理更加方便。

AST的结构

AST的每个节点代表程序中的一个语法元素。节点分为内部节点和叶子节点：内部节点代表复合结构（如表达式、语句块），叶子节点代表基本元素（如变量、常量）。AST中的边表示语法结构的组成关系。

我们使用一个简单的C程序来展示如何构建其抽象语法树（AST）。以下是一个计算阶乘的简单C程序示例：

#include <stdio.h>

int factorial(int n) {
    int result = 1;
    while (n > 0) {
        result = result * n;
        n = n - 1;
    }
    return result;
}

int main() {
    int number;
    printf("Enter a number: ");
    scanf("%d", &number);
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

以下是上述C程序的AST表示(示例)：

Program
└── Function: factorial
    ├── Parameters: n
    ├── Variable Declaration: result
    ├── Statement: Assignment (result = 1)
    ├── Statement: While
    │   ├── Condition: (n > 0)
    │   └── Body
    │       ├── Statement: Assignment (result = result * n)
    │       └── Statement: Assignment (n = n - 1)
    └── Statement: Return (result)
└── Function: main
    ├── Variable Declaration: number
    ├── Statement: Function Call (printf("Enter a number: "))
    ├── Statement: Function Call (scanf("%d", &number))
    ├── Statement: Function Call (printf("Factorial of %d is %d\n", number, factorial(number)))
    └── Statement: Return (0)

AST的构建

从源代码构建AST的过程称为语法分析（解析）。语法分析通常分为两个步骤：

词法分析（Lexical Analysis）: 将源代码拆分为标记（tokens），这些标记是语法元素的基本组成部分。
语法分析（Syntax Analysis）: 根据语法规则将标记序列组织成AST。

相关资料建议参考编译原理的教材

4. 控制流图

控制流图（CFG）是一种表示程序的有向图，其中节点表示语句，边表示可能的控制流。CFG对于流敏感分析（如数据流分析）特别有用。

基本概念

节点：表示程序中的语句。
边：表示控制从一个语句流向另一个语句。
入口节点（entry）和出口节点（exit）：每个CFG有一个入口节点和一个出口节点。

示例：迭代阶乘函数的CFG

iterate(n) {
    var f;
    f = 1;
    while (n > 0) {
        f = f * n;
        n = n - 1;
    }
    return f;
}

其控制流图如下：

entry
  |
f = 1
  |
while (n > 0) - false -> exit
  |
true
  |
f = f * n
  |
n = n - 1
  |
back to while (n > 0)

5. 基本块(BB)

基本块（Basic Block）是一个直线代码序列，其中只有入口和出口，没有中途的分支和汇合。换句话说，一个基本块是一组按顺序执行的语句，没有内部跳转。

CFG生成基本块的算法

初始化：从程序的入口点开始，创建一个基本块。
遍历程序：
- 对于每个语句：
- 如果是基本块的开始点，创建一个新的基本块。
- 将语句添加到当前基本块中。
- 如果语句是跳转语句（如条件语句、循环），则结束当前基本块，并标记跳转目标和下一个语句为新的基本块开始点。
连接基本块：
- 根据程序的控制流，将基本块按顺序连接起来，形成控制流图。

以此程序为例：

main() {
    var x, y;
    x = 10;
    y = 20;
    if (x > y) {
        x = x - y;
    } else {
        y = y - x;
    }
    return x + y;
}

控制流图（CFG）：

entry -> B1 -> B2
             /  \
           true  false
           /       \
         B3         B4
           \       /
             \   /
              B5 -> exit

基本块形式

// Basic Block B1
B1:
  x = 10
  y = 20
  goto B2

// Basic Block B2
B2:
  if (x > y) goto B3 else goto B4

// Basic Block B3
B3:
  x = x - y
  goto B5

// Basic Block B4
B4:
  y = y - x
  goto B5

// Basic Block B5
B5:
  return x + y