code-analysis - 在运行时计算生成的程序树的圈复杂度

Question

我正在运行一种自动生成表示抽象语法树的 S 表达式的进化算法。从那里我生成 C 代码来创建一个可编译的程序。

对于每个生成的表达式，我需要计算要在适应度计算中使用的圈复杂度。我注意到有一些工具可以这样做(例如 metrics Eclipse plugin )，但我希望有一些东西可以分析更通用的程序表示。

我可以看到调用外部工具，但我认为这会显着增加我的执行时间。有没有一种简单的方法可以通过某种考虑 S 表达式或抽象语法树的公式来计算圈复杂度？

Answer 1

如果您生成的程序是 goto-free(例如，“结构化”程序)，您可以使用一个简单的规则来计算圈复杂度:

CC(p) =  #conditionals +1

这是结构化程序的事实。如果您的程序是意大利面条控制流缠结，您只需要完整的定义。

请注意，条件语句应计算 while 和 for 循环(因为它们包含条件语句)以及表达式短路分支运算符 && 和 ||。