Question

如何使用AST生成程序的控制流图

Answer 1

对一个有结构化编程特性的编程语言而言，抽象语法树（AST）与“流分析”（flow analysis）不够兼容的地方在于：这些编程语言会有分支、循环、跳转（break/continue，或者像C#那样受限的goto）、异常处理等语法结构，它们隐含了不连续的控制流；而AST的结构虽然已经省略了一些语法细节，但仍然贴近语言的语法，所以AST里控制流往往是隐含在上述语法结构对应的节点里。更糟糕的是，这些编程语言中许多都有条件表达式（典型的是 ? : 三元运算符）以及带有短路求值语义的逻辑运算表达式（典型的是 &&、|| 二元运算符），这些“表达式”内也隐含控制流，更是藏得深。

所以正统做法推荐的是在做数据流分析之前，先把AST转换为一种更细粒度的、把控制流显式暴露出来的中间表示（IR）。虎书教的做法正是如此，第7章介绍从AST生成IR，第8章介绍了IR里的控制流与基本块。前面 @vczh 和 @陈炜 的回答都提到了这一点。 @邵成 的回答提到龙书第8～9章，我觉得把第6章（特别是6.6 Control Flow）也包括进来更好。

对数据流分析来说，IR无论是树形、DAG还是线性形式都没关系，只要控制流和数据依赖易于分析就好。SSA形式的IR可以把两者都显式暴露出来，特别是use-def关系（并且有些IR会额外维护def-use关系），所以在现代编译器和程序分析器里比较流行。