我有一个玩具编程语言的 AST。我需要找到未使用的赋值，即写入该变量的值在程序结束或下一次赋值之前保持未读取状态的赋值。 这个问题看起来很简单，但我无法想出一个快速的算法。我的做法： 构建一个控制流图，并从每个赋值中运行一个 DFS，该 DFS 不会传递对此变量的其他赋值。这样我们就会明白从赋值到读取这个值是否有路径，即是否使用了这个赋值。粗略的复杂度估计：控制流图将有 O(n) 个边和顶点，其中 n 是令牌的数量。那么算法的复杂度就是O(n^2)。考虑到程序的源代码理论上可以包含数百万个令牌，这看起来是一个很大的数字
看来您的“未使用的分配分析”与“实时变量分析”的问题类似。如果您关心解决这个问题的算法的理论复杂性，可以通过应用格定理来解决。如果您关心实现，GitHub 上有一些针对 C/C++、JAVA 活性分析的开源实现（我的课程作业代码，可能有 bug）。