6.4.3 有向无环图描述表达式
原书定位
印刷页P237起,对应PDF第249页。下文为目视整理的知识提要;完整内容见原书对照。
DAG 没有有向环。把运算符与操作数作为结点,可以让完全相同的子表达式共享同一子图,减少表达式树中重复的存储和计算。
合并时检查运算符、左右操作数与顺序;减法、除法不能交换操作数。若图由运算符指向操作数,求值顺序应先算依赖的操作数,再算引用它的运算符。

表达式树与共享子表达式的 DAG,原书P238。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P237起,对应PDF第249页。下文为目视整理的知识提要;完整内容见原书对照。
DAG 没有有向环。把运算符与操作数作为结点,可以让完全相同的子表达式共享同一子图,减少表达式树中重复的存储和计算。
合并时检查运算符、左右操作数与顺序;减法、除法不能交换操作数。若图由运算符指向操作数,求值顺序应先算依赖的操作数,再算引用它的运算符。

表达式树与共享子表达式的 DAG,原书P238。

