数据流图构造 [英] Data Flow Graph Construction

问题描述

在给出抽象语法树的情况下，我被要求编写一个程序来构造输入程序代码的数据流图。我在网上搜索数据流图的定义，发现在代码段的数据流分析中发生了很多事情。我想知道为给定代码构造数据流图时到底需要绘制什么。很感谢任何形式的帮助！

I have been asked to write a program to construct a data flow graph of a input program code, given the abstract syntax tree. I search for the definition of data flow graph online and found there are a lot of things that goes on in data flow analysis of a code segment. I want to know what exactly I have to draw to construct a data flow graph for a given code. Any help is very much appreciated!

推荐答案

给出AST，要生成数据流图，您必须：

Given an AST, to produce a data flow graph, you must:

• 建立符号表，以便将使用的每个标识符映射到其显式或隐式定义的类型，还允许您将一个作用域中的标识符与另一个作​​用域中的同一标识符区分开

• build up symbol tables, so that every identifier used is mapped to its explicitly or implicitly defined type, also allowing you distinguish an identifier in one scope from the same identifier in another scope

构建一个控制流图，显示了执行程序代码的顺序以及条件分支。 （在函数之间构造调用图的奖励点！）

construct a control flow graph, showing the order in which the program code is executed, and the conditional branches. (Bonus points for constructing a call graph between functions!)

确定数据如何沿控制流图流动，通常使用某种数据流分析框架，建立了对变量生命周期的引用，并将所有这些信息捕获为图表。

determine how data flows along the control flow graph, usually using some kind of data flow analysis framework, building up references to variable lifetimes, and capturing all this as a graph.

您可以使用某种外部图形绘制包绘制最终图形。

You can draw the final graph using some kind of external graph drawing package.

所有这些步骤都非常复杂，可能比您想象的要多得多。我觉得您在这里没有太多背景。您可以通过研究标准的编译器文本（Aho / Sethi / Ullman编译器）来获得该背景，它非常经典且非常好。但是在开始之前您需要这样做，否则您将无法真正理解这些步骤并将它们链接在一起。

All of these steps are pretty complicated, and are likely to be a lot more work than you might think. I get the impression you don't have much background here. You can get that background by studying a standard compiler text (Aho/Sethi/Ullman "Compilers") is pretty classic and very good. But you need to do that before you start, or you won't really understand the steps and they link together.

这篇关于数据流图构造的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！