Questions from the second chapter of the dragon book

Question

On page 29 it says "The leaves of a parse tree read from left to right form the yield of the tree, which is the string generated or derived from the nonterminal at the root of the parse tree. In Fig. 2.2 the generated string is 9-5*2. In that figure, all the leaves are shown at the bottom level. Henceforth, we shall not necessarily line up the leaves in this way." why not?

It also says "Any tree imparts a natural left-to-right order to its leaves, based on the idea that if a and b are two children with the same parent, and a is to the left of b, then all descendants of a are to the left of descendants of b." what does it mean?

P.S It's the second edition of the book

Answer 1

So first of all, for anyone else wanting to comment on this, the page numbers above refer to the first edition. In the second edition, the page number is 46, and the diagram referred to is figure 2.5.

EDIT: The author, when referring to extending the leaves down to the bottom, is talking about moving all leaves of the tree to be aligned vertically with each other, whether or not they are at the same level in the tree. Figure 2.2 has them extended to the bottom, such that every leaf is at the bottom of the diagram, aligned together vertically from left to right. If you look at some of the other diagrams later in the book, this is not done, and leaves are shown vertically aligned with other nodes at the same level, whether or not those other nodes are leaves. This latter way is the normal way of drawing trees, and is the most space efficient.

As for your first question, I believe the reason they do not do that is to save room. If you look at the right hand side of figure 2.4, if the author was to extend the leaves down to the bottom, then the subtree with letter as its root would have to be moved to the right, taking up more room than what is actually needed. While this is a minimal case and doesn't make a huge difference, one could imagine a larger tree (which I'm sure is in the book, although I didn't go looking) which would need more room.

For the second question, it is essentially saying that if you had a*b + c*d, and you considered the multiplications as siblings (as they would be to keep order of operations valid), then the leaves a and b would be to the left of c and d in the tree, just as they are to the left of c and d in the equation. Essentially its just saying what it already said in the first part, which is that the tree's leaves should be able to be read left to right in order to reproduce the original syntax exactly, not switching the ordering of any portions (i.e. if the tree read left to right c*d + a*b, that might still be valid, but would not be a tree we are considering).