Differentiate between top-down and bottom-up parsing.

Bottom-Up Parsing

• Bottom-up parsers build a parse tree from the bottom (leave) to top (root).
• The top-down parser starts with the root and works down to the leaves.
• The bottom-up parsing method we discuss is called “shift-reduce” parsing since it consists of shifting input symbols into a stack until the right side of production appears on top of the stack.
• The right side may then be replaced by (reduced to) symbol on the left side of production and the process repeated.
• In either case, the input to the parser is scanned from left to right, one symbol at a time.
• Shift reduce parsing uses a bottom-up style of parsing.
• Since it attempts to construct a parse tree for an input string beginning at the leaves (bottom) and working up towards the root (top).
• The process is reducing a string w to the start symbol of a grammar.
• At each step, the string matching the right side of production is replaced by a symbol on the left.

Example: Consider the grammar S -> aAcBe, A -> Ab | b, B -> d

• The string is abbcde.
• We want to reduce this string to S.
• Scan abbcde looking for a substring that matches the right side of some production.
• The substrings b and d qualify (as A -> b and B -> d).
• Let us choose the leftmost b of the string, replace it with A (from A -> b).
• The string obtained is aAbcde.
• We can find that Ab, b, and d matches the right side of some production, (A -> Ab, A -> b, B -> d).
• Suppose we choose to replace the substring Ab by A (using A -> Ab).
• The string obtained is aAcde.
• Replace d with B (using B -> d). The string is aAcBe.
• Now we replace the entire string by S (as S -> aAcBe).
• Each replacement of the right side of production by the left side symbol is called reduction.
• The process of bottom-up parsing may be viewed as finding and reducing handles.

Top-Down Parsing:

• It can be viewed as attempting to construct a parse tree for the input starting from the root and creating a node of the parse tree in preorder. We are having:
• The general form of top-down parsing may involve backtracking (making repeated scans of input)
• Recursive descent parsing, which eliminates the need for backtracking over input.
• It can be viewed as an attempt to find the leftmost derivation for an input string.

Example: Consider the grammar
S -> c A d A -> a b | a, and input string is w = c a d.
to construct a parse tree for this sentence: