【命题1】控制流图G中若a dom n，且b dom n，则a dom b 或b dom a
【证明】设G入口为s，假设结论不成立，即a 不dom b且b 不dom a，或a dom b且b dom a。根据支配结点定义，如果是前者，则从s有全部路径经a（或b）到n但不经过b（或a），这与题设b（或a）dom n矛盾；如果是后者，则从s有全部路径经a，然后经b，再经a，构成了无限循环a->b->a->•••，永远到不了n，这也与题设矛盾。故结论成立
【命题2】控制流图G中若m idom n，则m是唯一的，若d ≠ n 且d dom n ，则d dom m
【证明】设G入口为s，假设不唯一，G中有另一个结点m'且m' idom n，根据支配结点定义，从s经m到n的路径上必有m' dom m，从s经m'到n的路径上必有m dom m'，根据支配关系的反对称性，有m'=m，故唯一。假设d 不dom m，则从s到m的路径上不必然经过d，又m是n的唯一直接支配结点，则从s到n的路径上不必然经过d，即d 不dom n，这与题设矛盾，故d dom m。可以看到用反证法证明后一个结论时，直接支配结点的唯一性很关键
posted on 2023-09-06 22:57
春秋十二月 阅读(363)
评论(0) 编辑 收藏 引用 所属分类:
Compiler