- 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.
- 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.|