6.4.3 有向无环图描述表达式

教材导航 · 第6章

原书定位

印刷页P237起,对应PDF第249页。下文为目视整理的知识提要;完整内容见原书对照。

DAG 没有有向环。把运算符与操作数作为结点,可以让完全相同的子表达式共享同一子图,减少表达式树中重复的存储和计算。

合并时检查运算符、左右操作数与顺序;减法、除法不能交换操作数。若图由运算符指向操作数,求值顺序应先算依赖的操作数,再算引用它的运算符。

表达式树与共享子表达式的 DAG

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

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P237,PDF第249页

原书对照,原书P238,PDF第250页