设程序片段S=if C then S1 else S2，S1和S2可以是由赋值、条件、循环构成的复杂语句，S不为当前程序最后语句或某个循环主体最后语句，则S对应的流图生成的深度优先生成树T有3条树边，有S1的出口数+S2出口数-1条交叉边。为什么是3条树边？C到S1、C到S2、S1或S2到S3（S3是S后继结点，下同）。为什么交叉边数是S1出口数+S2出口数-1？因为流图中S1出口及S2出口到S3的边，在生成T的过程中，只有1个出口比S3先访问，这对应形成1条树边，访问S3后再访问其它出口，这对应形成其它出口到S3的交叉边，注意这里没有前向边，因为较晚访问的出口在T中不可能是S3的祖先。如果把S改为if C then S1，情况会怎样？结果取决于生成T的过程中先访问S3还是S1。若先访问S3，则有树边2条：C到S3、C到S1，交叉边数等于S1的出口数：S1的每个出口到S3各一条边，没有前向边。若先访问S2，则有树边1条：C到S2，前向边1条：C到S3，交叉边数等于S1出口数-1。
总结此类问题分析的基本思路是对程序控制结构先构建流图，再构建深度优先生成树，辨别其中的前向边、交叉边、后退边
posted on 2023-09-07 06:50
春秋十二月 阅读(53)
评论(0) 编辑 收藏 引用 所属分类:
Compiler