简单DAG生成算法的一个性质
2009-06-03 08:30:24 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鎯у⒔閹虫捇鈥旈崘顏佸亾閿濆簼绨绘い鎺嬪灪閵囧嫰骞囬姣挎捇鏌熸笟鍨妞ゎ偅绮撳畷鍗炍旈埀顒勭嵁婵犲嫮纾介柛灞捐壘閳ь剛鎳撻~婵嬪Ω閳轰胶鐤呯紓浣割儐椤戞瑩宕ョ€n喗鐓曟い鎰靛亝缁舵氨绱撻崘鈺傜婵﹤顭峰畷鎺戔枎閹搭厽袦婵犵數濮崑鎾绘⒑椤掆偓缁夌敻骞嗛悙鍝勭婵烇綆鍓欐俊鑲╃磼閹邦収娈滈柡灞糕偓鎰佸悑閹肩补鈧尙鏁栧┑鐐村灦閹稿摜绮旈悽绋课﹂柛鏇ㄥ灠閸愨偓濡炪倖鍔﹀鈧繛宀婁邯濮婅櫣绱掑Ο璇茶敿闂佺ǹ娴烽弫璇差嚕婵犳碍鏅插璺猴工瀹撳棝姊虹紒妯哄缂佷焦鎸冲畷鎴﹀箻鐠囧弶宓嶅銈嗘尰缁嬫垶绂嶉悙顒佸弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

“简单”嘛说明肯定有更麻烦、效果可能更好的办法。这里提到的算法就是这样。
龙书第二版363页习题6.1.2有点意思。题目如下:
Compilers - Principles, Techniques, & Tools, Second Edition 写道
Exercise 6.1.2: Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming + associates from the left.
a) a + b + (a + b)
b) a + b + a + b
c) a + a + ((a + a + a + (a + a + a + a))
(c)原本在书上就是这么写的……很明显括号没配对是吧 = =
勘误表里没提到这项。莫非是国内的影印版的问题?我无法确认。正确的代码应该是:
a + a + (a + a + a + (a + a + a + a))
这样才对)
如何从表达式的源码生成DAG(Directed Acyclic Graph,有向无环图)呢?龙书在前面给出了一个算法:在解析源码并生成语法树的算法的基础上,如果在创建新的节点前先检查是否已存在相同的节点,若存在则返回已有节点,否则返回新建的节点。
假设DAG的节点是<op,left,right>形式的三元组,其中op是表示运算符的枚举类型的值,left和right是表示子节点的引用。那么在检查是否已存在相同的节点时,只需要分别检查op、left和right是否相同即可。
但是这个简单的算法很明显不保证生成最优(节点数最少)的DAG。以习题6.1.2中的a)和b)为例:
a)
AST:
更多精彩
赞助商链接