設(shè)程序片段S=if C then S1 else S2，S1和S2可以是由賦值、條件、循環(huán)構(gòu)成的復雜語句，S不為當前程序最后語句或某個循環(huán)主體最后語句，則S對應的流圖生成的深度優(yōu)先生成樹T有3條樹邊，有S1的出口數(shù)+S2出口數(shù)-1條交叉邊。為什么是3條樹邊？C到S1、C到S2、S1或S2到S3（S3是S后繼結(jié)點，下同）。為什么交叉邊數(shù)是S1出口數(shù)+S2出口數(shù)-1？因為流圖中S1出口及S2出口到S3的邊，在生成T的過程中，只有1個出口比S3先訪問，這對應形成1條樹邊，訪問S3后再訪問其它出口，這對應形成其它出口到S3的交叉邊，注意這里沒有前向邊，因為較晚訪問的出口在T中不可能是S3的祖先。如果把S改為if C then S1，情況會怎樣？結(jié)果取決于生成T的過程中先訪問S3還是S1。若先訪問S3，則有樹邊2條：C到S3、C到S1，交叉邊數(shù)等于S1的出口數(shù)：S1的每個出口到S3各一條邊，沒有前向邊。若先訪問S2，則有樹邊1條：C到S2，前向邊1條：C到S3，交叉邊數(shù)等于S1出口數(shù)-1。
總結(jié)此類問題分析的基本思路是對程序控制結(jié)構(gòu)先構(gòu)建流圖，再構(gòu)建深度優(yōu)先生成樹，辨別其中的前向邊、交叉邊、后退邊
posted on 2023-09-07 06:50
春秋十二月 閱讀(63)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler