Why do we have to use depth-first traversal for a parse tree?

Question

During my learning of parsing technology, it seems the parse tree is always traversed in a depth-first manner.

The leftmost derivation corresponds to a preorder traversal of the parse tree, while the rightmost derivation corresponds to the reverse of a postorder traversal of the parse tree. ^[1]

And pre-order and post-order traversals are just 2 specific types of depth-first tree traversal^[2].

I think the reason lies in the difference between a plain tree and a parse tree. A plain tree only records the topology structure among nodes, while a parse tree records more than that. A parse tree further implies that the parent node is built upon the child nodes because a parent node derives into a collection of child nodes. If we want to compute the root node of the parse tree, which is the ultimate goal of creating a parse tree, we have to compute all the prerequisites. So a depth-first traversal is a natural must.

Is my understanding correct? Or is there any other scenario where other ways of traversal of a parse tree are necessary/mandatory?

Answer 1

You are considering only two of the possible parsing strategies: top-down left-to-right parsing, and bottom-up left-to-right parsing. Those are the two most popular strategies, to be sure. But they are not the only possibilities.

Each of these two strategies corresponds to one parse tree traverse, as the text you quote indicates. And the two traverses are both depth-first, in effect because the two parse strategies are both left-to-right. [Note 1]

Many other parse strategies are available, and they would correspond to other tree traverses. You could, for example, attempt to parse the text by starting in the middle somewhere (say, at a point where you were for some reason certain of the parse, perhaps because you are within all possible parenthetic groupings) and work outwards from there in some manner determined by your parsing algorithm. This strategy is certainly possible, and there is even a certain amount of literature about it (possibly not very current) because it makes sense in the context of doing partial parses of incorrect texts, for example for diagnostic purposes or syntax-highlighted display.

Even if you perform a left-to-right parse, you don't need to choose between top-down and bottom-up parsing. Before the LALR algorithm was discovered, there was quite a bit of investigation of "left corner" (LC) parsing, which switches between top-down and bottom-up parsing at the point where it becomes convenient to do so (the "corner"). The derivation so produced is neither leftmost nor rightmost, and it is hard to characterize the corresponding traverse (as per my footnote), although I think that a reasonable characterization would still result in a depth-first correspondence because the algorithm is still left-to-right.

In all cases, once the parse tree (or abstract syntax tree) has been constructed, you are free to traverse it in any fashion you like, and different semantic analysis algorithms perform different types of traverses. In an optimizing multi-pass compiler, you would expect to find a huge variety of different tree traverses, some depth-first, some breadth-first, and some which bounce around as necessary.

---

Notes:

1. I'm not sure whether the word "traverse" is really accurate here. The parse tree is not really being traversed, as such, since it doesn't yet exist; it is being constructed. The top-down strategy can be viewed as a depth-first preorder traverse of a tree which magically springs into existence during the traverse.

   On the other hand, the bottom-up strategy starts at the leftmost leaf node, and proceeds to deduce the traverse which arrived at that point, which is why the quoted text calls it "the reverse" of a traverse. Is that really a meaningful concept? It is meaningful as a description of the final result, certainly, but it doesn't really correspond to any intuitive sense of the word "traverse". If you were travelling to London, you couldn't start your trip at the point where you make the final exit from the M40.