设程序片段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
春秋十二月 阅读(47)
评论(0) 编辑 收藏 引用 所属分类:
Compiler