Shift reduce parser

complete explanation about shift reduce parser in compiler design.

1. Shift reduce parser SUBMITTED BY TEJVEER SINGH MCA 2 nd Year SUBMITTED TO Dr. VANDANA RANA

2. Definition and explanation Bottom-up parsing is based on the reverse process to top-down. Instead of expanding successive non-terminals according to production rules, a current string form is collapsed each time until the start non-terminal is reached to predict the legal next symbol. This can be regarded as a series of reductions. This approach is also known as shift-reduce parsing. This is the primary parsing method for many compilers, mainly because of its speed and the tools which automatically generate a parser based on the grammar.

3. Shift reduce parser requires mainly two data structures: 1. A input buffer for storing the input string. 2. A stack for storing and accessing the production rules.

4. WORKING Initially , shift-reduce parser is present in the following configuration Stack contains only the $ symbol . 2. Input buffer contains the input string with $ at its end.

5. . After achieving this configuration, The parser stops / halts. It reports the successful completion of parsing. An error is detected. Or stack is left with only the start symbol and the input buffer becomes empty.

6. Basic Operations – Shift:   This involves moving of symbols from input buffer onto the top of the stack. Reduce:   The handle appearing on the stack top is replaced with the appropriate non-terminal symbol.

7. Accept:   If only start symbol is present in the stack and the input buffer is empty then, the parsing action is called accept. When accept action is obtained, it means successful parsing is done. Error:   In this situation parser becomes confused. Since the parser can neither perform shift action nor reduce action and not even accept action .

8. Rules To Remember If the priority of incoming operator is more than the priority of in stack operator, then shift action is performed. It is important to remember the following rules while performing the shift-reduce action If the priority of in stack operator is same or less than the priority of in stack operator, then reduce action is performed.

9. Problem-01 Consider the following grammar- E → E – E E → E * E E  → id Parse the input string “ id – id * id “ using a shift-reduce parser. Solution :- The priority order is : id > * > – $ id – id * id $ Shift $ id – id * id $ Reduce E → id $ E – id * id $ Shift $ E – id * id $ Shift $ E – id * id $ Reduce E → id $ E – E * id $ Shift $ E – E * id $ Shift $ E – E * id $ Reduce E → id $ E – E * E $ Reduce E → E * E

10. Problem 02: –  Consider the grammar         S –> S + S         S –> S * S         S –> id Perform Shift Reduce parsing for input string “id + id + id”. SOLUTION:-

11. Problem 03: –  Consider the grammar         E –> 2E2         E –> 3E3         E –> 4 Perform Shift Reduce parsing for input string “32423”. Solution:-

12. THANK YOU