在第 29 页上，它说“从左到右读取的解析树的叶子形成树的产量，这是从解析树根部的非终结符生成或派生的字符串。在图 2.2 中，生成的字符串是9-5*2。在那个图中，所有的叶子都显示在最底层。以后我们不一定要这样排列叶子。为什么不？
它还说“任何一棵树都赋予它的叶子一个自然的从左到右的顺序，基于这样的想法，如果 a 和 b 是具有相同父母的两个孩子，并且 a 在 b 的左边，那么 a 的所有后代位于 b 的后代的左侧。” 这是什么意思？
PS这是本书的第二版
问问题
137 次
1 回答
3
所以首先，对于其他想对此发表评论的人，上面的页码指的是第一版。在第二版中，页码是46，参考的图表是图2.5。
编辑：作者在提到将叶子向下延伸到底部时，是在谈论移动树的所有叶子以相互垂直对齐，无论它们在树中是否处于同一级别。图 2.2 将它们延伸到底部，这样每片叶子都在图的底部，从左到右垂直对齐。如果您查看本书后面的一些其他图表，这还没有完成，并且叶子显示为与同一级别的其他节点垂直对齐，无论这些其他节点是否是叶子。后一种方式是绘制树的正常方式，并且是最节省空间的方式。
至于你的第一个问题，我相信他们不这样做的原因是为了节省空间。如果你看图 2.4 的右侧，如果作者要将叶子向下延伸到底部，那么以字母为根的子树将不得不向右移动，占用的空间比实际空间大需要。虽然这是一个最小的案例，并没有太大的不同，但可以想象一棵更大的树（我确定这在书中，虽然我没有去看），它需要更多的空间。
对于第二个问题，本质上是说，如果您有 a*b + c*d，并且您将乘法视为兄弟（因为它们将保持操作顺序有效），那么叶子 a 和 b 将是树中 c 和 d 的左侧，就像等式中 c 和 d 的左侧一样。本质上它只是在说它在第一部分中已经说过的内容，即树的叶子应该能够从左到右阅读，以便准确地再现原始语法，而不是切换任何部分的顺序（即，如果树读取从左到右 c*d + a*b，这可能仍然有效，但不会是我们正在考虑的树）。
于 2012-03-28T07:37:38.600 回答