設程序片段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
春秋十二月 閱讀(77)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler