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:

Top down parsing (Predictive parsing)Bottom up parsing (Shift reduce parsing)
Top down parser also called LL parser.Bottom up parser also called LR parser.
Stack predicts what is to come.Stack shows what has been so far.
Stack initially contains the start symbol of the grammar.Stack in initially empty.
Input tokens are popped off the stack.Input strings are pushed on the stack.
Left side of productions are popped off the stack.Right side of productions are popped off the stack.
Right side of productions are pushed on the stack.Left side of productions are pushed on the stack.
There is problem of backtracking.No backtracking.
Left recursion problem.No left recursion.
Less efficient.More efficient.
Less powerful.More powerful.
Not used for all programming languages.Used for all programming languages.

Leave a Reply