Bottom-Up Parsing
Bottom-up parsing is a parsing technology that attempts to construct a parse tree by starting from the leaves and reaching the root. That is, It constructs the parse tree bottom-up.
In other words, it constructs the rightmost derivation of the input string in the reverse order by reducing the input string to the start symbol of the grammar.
This process is referred to as Reduction.
A bottom-up parser constructs the rightmost derivation of the input by matching the substring of input with any righthand side of the production of the grammar. If this is matched, then replace the string with the left-hand side of that production.
The process of replacing the right-hand side of the production with the left-hand side is called reduction.
If the input string is reduced to the start symbol of the grammar then the parser is the successful parsing of input otherwise it gives an error.
A bottom-up parser has three levels:
- Bottom-Up
- Shift Reduce
- LR parsing
- SLR Parsing
- LR Parsing
- LALR Parsing
Reference Link