“龙书”第二章的问题

Question

在第29页上，它说“从左到右读取的解析树的叶子形成了树的产出量，这是从解析树根部的非终结符生成或派生的字符串。在图2.2中，生成的字符串是9-5*2。在该图中，所有的叶子都显示在底部。从今以后，我们不一定要用这种方式排列叶子。”为什么不行？

它还说：“任何一棵树的叶子都有从左到右的自然顺序，这是基于这样的想法:如果a和b是具有相同父代的两个孩子，并且a在b的左边，那么a的所有后代都在b的后代的左边。”什么意思？

这是这本书的第二版

Answer 1

因此，首先，对于任何想要对此发表评论的人，上面的页码指的是第一版。在第二版中，页码是46，参考的图表是图2.5。

编辑:作者在提到将树叶向下延伸到底部时，是指移动树的所有树叶，使它们彼此垂直对齐，无论它们是否在树中的同一级别。图2.2将它们延伸到底部，这样每个叶子都在图的底部，从左到右垂直排列在一起。如果您查看本书后面的一些其他图，就会发现这并没有完成，并且叶子与同一级别的其他节点垂直对齐，无论这些其他节点是否是叶子。后一种方法是绘制树的常规方法，并且是最节省空间的。

至于你的第一个问题，我相信他们不这样做的原因是为了节省空间。如果您查看图2.4的右侧，如果作者要将叶子向下扩展到底部，则必须将以字母为根的子树移动到右侧，从而占用比实际所需空间更多的空间。虽然这是一个最小的情况，并没有造成很大的差异，但可以想象一棵更大的树(我确信这在书中，尽管我没有去寻找)，它将需要更多的空间。

对于第二个问题，本质上是说，如果您有a*b + c*d，并且您将乘法视为兄弟(因为它们将保持操作顺序有效)，那么叶a和b将位于树中c和d的左侧，就像它们在等式中c和d的左侧一样。本质上，它只是说了它在第一部分中已经说过的话，那就是树的叶子应该能够从左到右读取，以便准确地再现原始语法，而不是改变任何部分的顺序(即，如果树从左到右读取c*d + a*b，这可能仍然有效，但不是我们正在考虑的树)。