支配性、嚴(yán)格支配性、直接支配性、支配邊界

支配性

如果每一條從流圖到入口節(jié)點(diǎn)到節(jié)點(diǎn)n都需要經(jīng)過節(jié)點(diǎn)d，則稱d支配n，又記d （支配）dominance n。

如上圖入口節(jié)點(diǎn)1到節(jié)點(diǎn)4都需要經(jīng)過節(jié)點(diǎn)3，3節(jié)點(diǎn)則支配節(jié)點(diǎn)4.

嚴(yán)格支配性

當(dāng)d！=n時且d dom n ，則d sdom n

直接支配性

在支配樹（dominator tree）中，對于結(jié)點(diǎn) n 來說，從根節(jié)點(diǎn)到結(jié)點(diǎn) n 所在路徑上的結(jié)點(diǎn)（不包括）都嚴(yán)格支配結(jié)點(diǎn) n，例如上圖中從根節(jié)點(diǎn) 1 -> 2 -> 3，其中結(jié)點(diǎn) 1 和 結(jié)點(diǎn) 2 都嚴(yán)格支配結(jié)點(diǎn) 3。該路徑上離結(jié)點(diǎn) n 最近的結(jié)點(diǎn)叫做結(jié)點(diǎn) n 的 直接支配結(jié)點(diǎn)（immediate node），用 IDom(n) 表示，例如上圖中 IDom(6) = 2。換句話說，就是在嚴(yán)格支配性的基礎(chǔ)上還得是節(jié)點(diǎn)n前的最后一個嚴(yán)格支配節(jié)點(diǎn)。

支配邊界

Y 是 X 的支配邊界，當(dāng)且僅當(dāng) X 支配 Y 的一個前驅(qū)結(jié)點(diǎn)（CFG）同時 X 并不嚴(yán)格支配 Y

總結(jié)

以上是生活随笔為你收集整理的编译原理支配树部分名词介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。