软考题库
软件设计师 · 高频练习

DAG 为什么能表示公共子表达式共享？

中级 单选题 第 848 题 中等 软件设计师编译原理DAG公共子表达式局部优化
内容整理：软考题库编辑部 最近更新：
题目

对基本块中的表达式 y=a*b+a*b 建立 DAG。若两次 a*b 的操作数和值都相同，DAG 的典型处理是（）。

A 无条件建立两个完全独立的乘法结点
B 让两个加法输入共享同一个乘法结点
C 删除加法，只保留一次 a*b
D 把 a 和 b 合并成同一个叶结点
题目类型：原创高频练习题 用途：用于帮助理解软件设计师相关考点和答案解析，不等同于官方真题。
正确答案
B
答案解析

DAG 允许一个结点被多个父结点引用。两次 a*b 在操作符和操作数均相同、且中间没有对 a 或 b 重新赋值时，计算结果相同，可以用同一个乘法结点表示；加法结点的两个输入都指向该结点。

选项分析

A

错误。这是普通语法树式的重复表示，没有利用 DAG 的共享能力。

B

正确。共享乘法结点体现了相同公共子表达式只计算一次。

C

错误。原表达式需要把两个相同结果相加，不能连外层加法一起删除。

D

错误。a 和 b 是不同变量叶结点，不能因为参与同一运算就合并。

本题为什么容易错

看到“公共子表达式消除”容易误以为把重复部分直接删掉。优化的真实含义是复用第一次计算结果，凡是使用该结果的地方仍要保留数据依赖。

先看结论

简短答案

DAG 为什么能表示公共子表达式共享，正确答案是 B（让两个加法输入共享同一个乘法结点）。DAG 允许一个结点被多个父结点引用。两次 a*b 在操作符和操作数均相同、且中间没有对 a 或 b 重新赋值时，计算结果相同，可以用同一个乘法结点表示；加法结点的两个输入都指向该结点。

解析

易混淆概念对比表

概念本题判断区别要点记忆提示
无条件建立两个完全独立的乘法结点 本题干扰项 错误。这是普通语法树式的重复表示，没有利用 DAG 的共享能力。 看到该词不要急着选，先判断是否真正解决题干问题
让两个加法输入共享同一个乘法结点 本题正确答案 正确。共享乘法结点体现了相同公共子表达式只计算一次。 看到题干核心场景时优先联想到它
删除加法，只保留一次 a*b 本题干扰项 错误。原表达式需要把两个相同结果相加，不能连外层加法一起删除。 看到该词不要急着选，先判断是否真正解决题干问题
把 a 和 b 合并成同一个叶结点 本题干扰项 错误。a 和 b 是不同变量叶结点，不能因为参与同一运算就合并。 看到该词不要急着选，先判断是否真正解决题干问题
本题易混淆选项怎么区分
  • 无条件建立两个完全独立的乘法结点：错误。这是普通语法树式的重复表示，没有利用 DAG 的共享能力。
  • 删除加法，只保留一次 a*b：错误。原表达式需要把两个相同结果相加，不能连外层加法一起删除。
  • 把 a 和 b 合并成同一个叶结点：错误。a 和 b 是不同变量叶结点，不能因为参与同一运算就合并。
复习

知识点详解

抽象语法树中每次语法出现通常对应独立子树，而 DAG 可以让多条边指向同一结点，表示多个表达式使用同一个值。基本块优化常借助 DAG 发现公共子表达式、无用赋值和名称等价关系。若某个操作数在两次表达式之间被重新定义，即使文字仍写成 a*b，也不再代表同一个值，不能盲目共享。

备考速记

同操作、同输入、值没变，DAG 才共享；共享计算，不删除用途。

DAG 在局部优化场景中的作用

DAG在本题中的核心价值，是解决“对基本块中的表达式 y=a*b+a*b 建立 DAG。若两次 a*b 的操作数和值都相同，DAG 的典型处理是（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。

拓展

同类题怎么考

  • 给出基本块三地址码，画 DAG 并找出公共子表达式。
  • 判断变量重新赋值后，原公共子表达式是否还能复用。
  • 比较语法树与 DAG 在结点共享和优化表示上的差异。
DAG 在软件设计师软考中的考法

软考选择题通常不会只考概念定义，还会把DAG放到局部优化场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。

解题思路

语法树会老老实实画两棵 a*b；DAG 会先问：第二次乘法和前一次是不是同一件事？如果 a、b 都没被改写，就不必再造一个乘法结点，让两条边指向旧结点即可。注意这里只省掉重复乘法，外层加法仍然存在。

考点定位

DAG 与普通语法树的关键差异是允许共享子结点，因此能显式表示基本块内的公共子表达式，但共享前必须确认操作数的值没有改变。

易错提醒

  • 共享前没有检查变量是否在两次计算之间被重新定义。
  • 把重复子表达式和整个表达式混为一谈，错误删除外层运算。
  • 把 DAG 的共享理解成变量结点合并，而不是相同运算结果结点复用。

备考提示

  • 画 DAG 时先为变量建叶结点，再查找是否已有相同操作符且孩子相同的内部结点。
  • 遇到赋值语句要更新变量标签，重新判断旧结点中的值是否仍代表当前变量。

你可能还想了解

  • DAG 与抽象语法树的主要区别是什么？
  • 变量重新赋值后为什么不能继续共享旧结点？
  • 公共子表达式消除是不是直接删除第二个表达式？
  • 基本块 DAG 还能用于哪些局部优化？

本文小结

在 a、b 的值没有变化时，两次 a*b 产生同一结果，DAG 可让外层加法的两个输入共享一个乘法结点。它复用的是计算结果，外层加法和数据依赖不能被删除。