龙书第二章的问题



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

它还说:"任何一棵树的叶子都有一个自然的从左到右的顺序,基于这样的想法,如果a和b是同一父母的两个孩子,a在b的左边,那么a的所有后代都在b的后代的左边。"这是什么意思?

p.S这是这本书的第二版

因此,首先,对于其他想要对此发表评论的人来说,上面的页码指的是第一版。在第二版中,页码为46,参考的图表为图2.5。

编辑:当提到将树叶向下延伸到底部时,作者所说的是移动树的所有树叶,使其相互垂直对齐,无论它们在树中是否处于同一水平面。图2.2将它们延伸到底部,这样每个叶子都在图的底部,从左到右垂直对齐。如果您在本书后面查看一些其他图表,则不会完成此操作,并且无论其他节点是否为叶子,叶子都与同一级别的其他节点垂直对齐。后一种方式是绘制树的正常方式,也是最节省空间的方式。

至于你的第一个问题,我相信他们不这么做的原因是为了节省空间。如果你看看图2.4的右手边,如果作者要将叶子向下延伸到底部,那么以字母为根的子树就必须向右移动,这会占用比实际需要的更多的空间。虽然这是一个最小的案例,没有太大的区别,但人们可以想象一棵更大的树(我确信这棵树在书中,尽管我没有去看)需要更多的空间。

对于第二个问题,它本质上是说,如果你有a*b+c*d,并且你认为乘法是兄弟的(因为它们将保持运算顺序有效),那么叶子a和b将在树中c和d的左边,就像它们在方程中c和d的左边一样。从本质上讲,它只是在说它在第一部分中已经说过的话,即树的叶子应该能够从左到右读取,以便准确地再现原始语法,而不是切换任何部分的顺序(即,如果树从左向右读取c*d+a*b,这可能仍然有效,但不是我们正在考虑的树)。

相关内容

  • 没有找到相关文章

最新更新