Chapter 4, Problem 9RQ

Explanation of Solution

Differences between top-down and bottom-up parsers:

The differences between top-down and bottom-up parsers are as follows:

• Top down parser and bottom up parser differ in the way in which a parse tree is built. We know that a tree contains a special node called root which specifies the entry to the tree, some internal nodes and terminal nodes called leaves.
• If the parser starts building the tree from root (top), gradually expands down from root to leaves (ends at down part) it is the top-down approach and such a parser is called top-down parser.
• If the parser starts from leaf nodes(from down) and slowly builds up towards the root node, then the approach is called bottom up parsing method and such a parser is called bottom up parser.
• Top-down parser builds tree in pre-order where node root is first built and then it’s left branch and then its right branch where as a bottom up parser builds the tree starting from leaves and reach the root in upwards direction...