各位观众老爷，大家好！今天咱们不聊八卦，来点硬核的——AST（抽象语法树）和 CFG（控制流图）的结合，看看这两位大佬如何联手，把咱们的代码扒个底朝天，提取语义信息，搞更深度的程序分析。
开场白：代码的灵魂拷问
咱们写代码，那可不是随便敲几个字符，而是要表达一定的意图。比如，int x = 1 + 2; 这行代码，计算机读到它，知道你要声明一个整型变量 x，然后把 1 + 2 的结果赋值给它。但是，计算机是怎么理解这些意图的呢？这就得靠编译器/解释器里头的各种神器了，其中就包括 AST 和 CFG。
AST 就像是代码的骨架，它把代码的语法结构用树形结构表示出来，让计算机能更容易地理解代码的组成部分。而 CFG 则像是代码的血管，它描绘了代码的执行流程，让计算机知道代码的执行顺序。
第一幕：AST——代码的骨架
AST，全称 Abstract Syntax Tree，中文名叫抽象语法树。它是一种树状的数据结构，用来表示编程语言的语法结构。 简单来说，就是把代码拆解成一个个节点，然后按照语法规则把它们连接起来。
-
为什么叫“抽象”？
因为它忽略了一些无关紧要的细节，比如空格、注释等等，只保留了代码的核心结构。
-
AST 的节点类型
AST 的节点类型有很多种，常见的包括：
- 程序节点 (Program Node): 代表整个程序的根节点。
- 函数声明节点 (Function Declaration Node): 代表一个函数的声明。
- 变量声明节点 (Variable Declaration Node): 代表一个变量的声明。
- 赋值节点 (Assignment Node): 代表一个赋值操作。
- 二元运算节点 (Binary Expression Node): 代表一个二元运算，比如加法、减法等等。
- 一元运算节点 (Unary Expression Node): 代表一个一元运算，比如取反、逻辑非等等。
- 字面量节点 (Literal Node): 代表一个字面量，比如数字、字符串等等。
- 标识符节点 (Identifier Node): 代表一个标识符，比如变量名、函数名等等。
- 控制流节点 (Control Flow Node): 代表控制流语句，比如 if、else、for、while 等等。
-
来个栗子：
int x = 1 + 2;的 AST如果用 Python 来表示这个 AST，大概是这样的：
{ "type": "Program", "body": [ { "type": "VariableDeclaration", "declarations": [ { "type": "VariableDeclarator", "id": { "type": "Identifier", "name": "x" }, "init": { "type": "BinaryExpression", "operator": "+", "left": { "type": "Literal", "value": 1, "raw": "1" }, "right": { "type": "Literal", "value": 2, "raw": "2" } } } ], "kind": "int" } ] }用更直观的树形结构表示：
Program └── VariableDeclaration └── VariableDeclarator ├── id: Identifier (x) └── init: BinaryExpression (+) ├── left: Literal (1) └── right: Literal (2)可以看到，AST 把这行代码拆解成了声明、变量、加法运算、数字等等，并且用树形结构表示了它们之间的关系。
-
如何生成 AST？
生成 AST 的过程通常包括两个步骤：
- 词法分析 (Lexical Analysis)： 也叫扫描 (Scanning)，把代码分解成一个个的 Token，比如关键字、标识符、运算符等等。
- 语法分析 (Syntax Analysis)： 也叫解析 (Parsing)，根据语法规则把 Token 组织成 AST。
有很多工具可以用来生成 AST，比如：
- JavaScript: Acorn, Esprima, Babel
- Python: ast 模块, PLY, Lark
- Java: ANTLR
第二幕：CFG——代码的血管
CFG，全称 Control Flow Graph，中文名叫控制流图。它是一个有向图，用来表示程序的执行流程。
-
CFG 的节点类型
CFG 的节点通常代表一个基本块 (Basic Block)，也就是一段顺序执行的代码，中间没有分支和跳转。
-
CFG 的边类型
CFG 的边代表控制流的转移，也就是程序从一个基本块执行到另一个基本块。
-
来个栗子：
if (x > 0) { y = 1; } else { y = 2; }的 CFGStart ├── Condition: x > 0 │ ├── True Branch: y = 1 │ └── False Branch: y = 2 └── End可以用更直观的图形来表示：
[Start] --> [x > 0] [x > 0] --(True)--> [y = 1] --> [End] [x > 0] --(False)--> [y = 2] --> [End]可以看到，CFG 把这段代码的执行流程用图的形式表示出来，清楚地展示了条件判断和分支跳转。
-
如何生成 CFG？
生成 CFG 通常需要遍历 AST，然后根据代码的结构和控制流语句来构建图。
- 顺序语句： 直接把相邻的语句连接起来。
- 条件语句 (if/else)： 创建一个条件节点，然后分别连接到 then 分支和 else 分支。
- 循环语句 (for/while)： 创建一个循环头节点，然后连接到循环体和循环出口。
第三幕：AST + CFG——代码的灵魂拷问升级版
现在，咱们有了 AST 和 CFG 这两大利器，就可以开始对代码进行更深度的分析了。
-
语义分析 (Semantic Analysis)
语义分析是指检查代码的语义是否正确，比如类型检查、变量是否定义等等。AST 提供了代码的结构信息，CFG 提供了代码的执行流程信息，结合这两者，可以更准确地进行语义分析。
-
类型检查：
- 遍历 AST，找到所有的变量声明和赋值语句。
- 检查赋值语句的左右两边的类型是否匹配。
- 如果类型不匹配，就报错。
# 假设我们有如下代码 # int x = "hello"; # 遍历 AST，找到 VariableDeclaration 节点 # 找到 VariableDeclarator 节点，获取变量名和初始值 # 获取变量的类型 (int) 和初始值的类型 (string) # 发现类型不匹配，报错 print("类型错误：不能将字符串赋值给整型变量") -
变量是否定义：
- 遍历 AST，找到所有的标识符节点。
- 检查标识符是否在当前作用域内已经声明。
- 如果未声明，就报错。
# 假设我们有如下代码 # y = 1; # y 未声明 # 遍历 AST，找到 Identifier 节点 (y) # 检查 y 是否在当前作用域内已经声明 # 发现 y 未声明，报错 print("变量未声明：y")
-
-
数据流分析 (Data Flow Analysis)
数据流分析是指分析程序中数据的流动情况，比如变量的定义、使用、赋值等等。CFG 提供了代码的执行流程信息，可以用来追踪数据的流动路径。
-
活跃变量分析 (Live Variable Analysis)：
- 对于 CFG 中的每个基本块，计算在该基本块中活跃的变量。
- 一个变量在某个基本块中活跃，如果它在该基本块之后被使用，而且在该基本块到使用它的路径上没有被重新定义。
- 活跃变量分析可以用来进行死代码消除和寄存器分配。
# 假设我们有如下代码 # int x = 1; # int y = x + 2; # int z = y * 3; # return z; # 构建 CFG # 对于每个基本块，计算活跃变量 # 例如，在 "int z = y * 3;" 这个基本块中，活跃变量是 y 和 z # 因为 y 在该基本块之后被使用 (计算 z)，而 z 是返回值 # x 在该基本块中不活跃，因为它的值没有被使用 -
到达定值分析 (Reaching Definition Analysis)：
- 对于 CFG 中的每个基本块，计算到达该基本块的定值。
- 一个定值到达某个基本块，如果该定值在执行到该基本块的任何路径上都没有被重新定义。
- 到达定值分析可以用来进行常量传播和代码优化。
# 假设我们有如下代码 # int x = 1; # if (condition) { # x = 2; # } # int y = x + 3; # 构建 CFG # 对于 "int y = x + 3;" 这个基本块，到达该基本块的 x 的定值有两个： # 1. int x = 1; # 2. x = 2; (如果 condition 为真)
-
-
控制流分析 (Control Flow Analysis)
控制流分析是指分析程序的执行流程，比如循环、分支等等。CFG 本身就是控制流图，可以直接用来进行控制流分析。
-
循环检测：
- 在 CFG 中寻找环。
- 环代表程序中的循环。
- 循环检测可以用来进行循环优化。
-
可达性分析：
- 从 CFG 的起始节点开始，遍历所有可达的节点。
- 如果某个节点不可达，说明对应的代码是死代码。
- 可达性分析可以用来进行死代码消除。
-
-
更高级的应用
AST 和 CFG 的结合，还可以用于更高级的应用，比如：
- 漏洞检测： 分析代码是否存在潜在的安全漏洞，比如缓冲区溢出、SQL 注入等等。
- 代码克隆检测： 寻找代码中重复的部分，可以用来进行代码重构。
- 代码生成： 根据 AST 和 CFG，生成目标代码，比如汇编代码、字节码等等。
第四幕：代码示例：一个简单的表达式求值器
为了更好地理解 AST 和 CFG 的应用，咱们来写一个简单的表达式求值器。这个求值器可以解析包含加法和乘法的表达式，并计算出结果。
-
定义 AST 节点类型
class ASTNode: def __init__(self, type, value=None, left=None, right=None): self.type = type # 节点类型 (例如：'Number', 'Operator') self.value = value # 节点的值 (例如：1, '+') self.left = left # 左子节点 self.right = right # 右子节点 def print_ast(node, indent=0): """打印 AST 结构，方便调试""" if node: print(" " * indent + f"Type: {node.type}, Value: {node.value}") print_ast(node.left, indent + 1) print_ast(node.right, indent + 1) -
词法分析器 (Lexer)
class Lexer: def __init__(self, text): self.text = text self.pos = 0 self.current_char = self.text[self.pos] if self.pos < len(self.text) else None def advance(self): """移动到下一个字符""" self.pos += 1 self.current_char = self.text[self.pos] if self.pos < len(self.text) else None def skip_whitespace(self): """跳过空白字符""" while self.current_char is not None and self.current_char.isspace(): self.advance() def get_next_token(self): """返回下一个 token""" self.skip_whitespace() if self.current_char is None: return None if self.current_char.isdigit(): return self.get_number() if self.current_char == '+': self.advance() return ASTNode("Operator", "+") if self.current_char == '*': self.advance() return ASTNode("Operator", "*") raise Exception("Invalid character") def get_number(self): """返回一个数字 token""" number = "" while self.current_char is not None and self.current_char.isdigit(): number += self.current_char self.advance() return ASTNode("Number", int(number)) -
语法分析器 (Parser)
class Parser: def __init__(self, lexer): self.lexer = lexer self.current_token = self.lexer.get_next_token() def eat(self, token_type): """如果当前 token 类型匹配，则消耗掉它，否则报错""" if self.current_token and self.current_token.type == token_type: self.current_token = self.lexer.get_next_token() else: raise Exception(f"Expected {token_type}, got {self.current_token.type if self.current_token else None}") def term(self): """处理数字""" token = self.current_token self.eat("Number") return token def expr(self): """处理表达式""" node = self.term() while self.current_token and self.current_token.type == "Operator": token = self.current_token if token.value == "+": self.eat("Operator") elif token.value == "*": self.eat("Operator") else: break # 否则退出循环 node = ASTNode("Operator", token.value, node, self.term()) # 重新构建树 return node def parse(self): """解析表达式，返回 AST""" return self.expr() -
求值器 (Evaluator)
class Evaluator: def visit(self, node): """根据节点类型，调用不同的访问方法""" if node.type == "Number": return self.visit_number(node) elif node.type == "Operator": return self.visit_operator(node) else: raise Exception("Invalid node type") def visit_number(self, node): """访问数字节点""" return node.value def visit_operator(self, node): """访问操作符节点""" left = self.visit(node.left) right = self.visit(node.right) if node.value == "+": return left + right elif node.value == "*": return left * right else: raise Exception("Invalid operator") def evaluate(self, ast): """计算 AST 的值""" return self.visit(ast) -
主程序
def main(): text = "1 + 2 * 3" lexer = Lexer(text) parser = Parser(lexer) ast = parser.parse() print("AST:") print_ast(ast) evaluator = Evaluator() result = evaluator.evaluate(ast) print(f"Result: {result}") if __name__ == "__main__": main()运行结果：
AST: Type: Operator, Value: + Type: Number, Value: 1 Type: Operator, Value: * Type: Number, Value: 2 Type: Number, Value: 3 Result: 7这个例子虽然简单，但是展示了 AST 的基本用法。 可以看到，词法分析器把代码分解成 Token，语法分析器根据 Token 构建 AST，然后求值器遍历 AST，计算出表达式的值。
注意： 这个例子没有生成 CFG，因为表达式求值器没有复杂的控制流。
第五幕：总结与展望
今天咱们聊了 AST 和 CFG 的基本概念、生成方法以及它们在程序分析中的应用。AST 提供了代码的结构信息，CFG 提供了代码的执行流程信息，结合这两者，可以进行更深度的程序分析，比如语义分析、数据流分析、控制流分析等等。
当然，AST 和 CFG 只是程序分析的冰山一角，还有很多其他的技术，比如符号执行、模型检查等等。希望通过今天的讲座，能让大家对程序分析有一个更深入的了解，并且能够在实际工作中应用这些技术，写出更安全、更高效的代码。
互动环节：提问时间
现在是提问时间，大家有什么问题可以提出来，咱们一起讨论讨论。 比如：
- AST 和 CFG 在编译器/解释器中扮演什么角色？
- 如何选择合适的 AST 生成工具？
- 如何利用 AST 和 CFG 进行代码优化？
- AST 和 CFG 的优缺点是什么？
- 未来程序分析的发展趋势是什么？
期待大家的积极参与！