从AST建造CFG

Question

据我所知，在解析器构建AST之后，这个结构将被转换为一个“中间层”IR，例如三个入口代码或任何其他代码。然后，为了便于分析，将该IR变换成一个控制流图。我的问题是，如果不经过另一个IR就可以从AST表示到CFG，然后通过CFG执行数据流分析，并取得了成功的结果？

Answer 1

如果不首先执行作用域，然后进行名称解析，就无法构造CFG。

您需要范围解析来确定隐式控制传输的“范围”，例如if--然后--否则，一个try-语句的边界，带有“easy语句”的块，返回语句等等。这通常相当容易，因为作用域倾向于遵循语言的语法结构，而AST已经具有这种语法结构。

如果您的语言允许将控件传输到指定的实体(“goto ")、”调用“，则还需要范围解析来确定在何处定义标识符。不知道哪个范围包含goto，以及范围如何控制命名标签的查找，就无法知道goto的目标是什么。

使用范围解析，您可以实现名称解析；这允许您将名称分配给包含名称的定义范围，并附加名称的定义(例如，知道"goto x“指特定作用域中的x，因此可以在该范围中定义x的第750行)。

一旦您有了名称解析(因此您可以在"goto x“中查找x的定义)，现在您就可以构造一个控制流图了。

您可以使用属性语法来完成这三项任务，这实际上是在AST上直接进行的计算。所以，不，除了AST，您不需要其他任何东西来实现这些。{您可以了解有关属性计算at my SO answer describing them的更多信息。当然，对于一个正式的属性计算，您可以做的任何事情都可以通过编写大量递归过程来完成，这些过程遍历树并计算等效的结果；这就是在实践中将属性语法编译成的结果。

在这里你可以找到some details on how to extract the control flow graph by attribute computation

一个杂乱无章的问题是像"goto“这样的计算(GCC允许这样做)。要正确地执行此操作，需要计算标签变量的数据流(从技术上讲，这需要首先构造一个CFG :-( )。您可以通过构造一个保守的答案来避免执行数据流："goto @“可以转到其地址位于查找goto的函数中的任何标签。您也可以使用属性语法来计算这个值。

对于只有结构化控制流的语言，实际上可以通过属性语法直接实现数据流分析。