【命題1】控制流圖G中若a dom n，且b dom n，則a dom b 或b dom a
【證明】設G入口為s，假設結(jié)論不成立，即a 不dom b且b 不dom a，或a dom b且b dom a。根據(jù)支配結(jié)點定義，如果是前者，則從s有全部路徑經(jīng)a（或b）到n但不經(jīng)過b（或a），這與題設b（或a）dom n矛盾；如果是后者，則從s有全部路徑經(jīng)a，然后經(jīng)b，再經(jīng)a，構(gòu)成了無限循環(huán)a->b->a->•••，永遠到不了n，這也與題設矛盾。故結(jié)論成立
【命題2】控制流圖G中若m idom n，則m是唯一的，若d ≠ n 且d dom n ，則d dom m
【證明】設G入口為s，假設不唯一，G中有另一個結(jié)點m'且m' idom n，根據(jù)支配結(jié)點定義，從s經(jīng)m到n的路徑上必有m' dom m，從s經(jīng)m'到n的路徑上必有m dom m'，根據(jù)支配關系的反對稱性，有m'=m，故唯一。假設d 不dom m，則從s到m的路徑上不必然經(jīng)過d，又m是n的唯一直接支配結(jié)點，則從s到n的路徑上不必然經(jīng)過d，即d 不dom n，這與題設矛盾，故d dom m。可以看到用反證法證明后一個結(jié)論時，直接支配結(jié)點的唯一性很關鍵
posted on 2023-09-06 22:57
春秋十二月 閱讀(461)
評論(0) 編輯 收藏 引用 所屬分類:
Compiler