Slr parser

Bottom-up parser
SLR PARSER
Parsing techniques

1. SLR PARSER Steps: create augment grammar generate kernel items find closure compute goto () construct parsing table parse the string Let us consider grammar: S->a S->(L) L->S L->L,S

2. Step :1 Create augment grammar S is start symbol in the given grammar Augment grammar is S’-> S Step :2 Generate kernel items Introduce dot in RHS of the production`` S’-> . S Step :3 Find closure ( Rule : A -> α . X β i.e if there is nonterminal next to dot then Include X production)) S’-> . S S-> . a S->.(L) I0

3. Step :4 compute goto () S’-> S . I1 Goto (I0,a) S-> a . I2 Goto (I0, ( ) S’-> . S S-> . a S->.(L) I0 S-> (.L) L->.S L>.L,S S->.a S->.(L) I3 Goto (I3, L ) S-> (L . ) L->L . ,S I4 Goto (I3, S ) L->S . I5 Goto (I3,a ) S->a . I2 Goto (I3, ( ) S-> ( . L ) L->.S L>.L,S S->.a S->.(L) I3 Goto (I0,S)

4. Goto (I4, ) ) S-> (L) . I6 Goto (I4, , ) L->L , . S S-> . a S->.(L) I7 Goto (I7, S ) L->L , S . I8 Goto (I7,a ) S-> a . I2 Goto (I7, ( ) S-> (.L) L->.S L>.L,S S->.a S->.(L) I3 label Production Ending iteration R0 S’-> S . I1 R1 S->a . I2 R2 S->(L) . I6 R3 L->S . I5 R4 L->L,S . I8

5. Step :5 construct parsing table Label the rows of table with no. of iterations Divide the Column into two parts Action part: terminal symbols Goto part: Nonterminal symbols Terminals Non terminals a ( ) , $ S L 1 2 3 4 5 6 7 8

6. Step :5 construct parsing table from step 4: Label the rows of table with no. of iterations Divide the Column into two parts Action part: terminal symbols Goto part: Nonterminal symbols ACTION GOTO a ( ) , $ S L S2 S3 1 1 2 3 S2 S3 5 4 4 S6 S7 5 6 7 S2 S3 8 8 Goto ( I0, S ) 1 Goto ( I3, ( ) 3 Goto ( I0, a ) 2 Goto ( I4, ) ) 6 Goto ( I0, ( ) 3 Goto ( I4, , ) 7 Goto ( I3, L ) 4 Goto ( I7, S ) 8 Goto ( I3, S ) 5 Goto ( I7, a ) 2 Goto ( I3, a ) 2 Goto ( I7, ( ) 3

7. Step :5 construct parsing table Label the rows of table with no. of iterations Divide the Column into two parts Action part: terminal symbols Goto part: Nonterminal symbols ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 label Production Ending iteration Follow(LHS) R0 S’-> S . I1 Follow(S’)={ $ } R1 S-> a . I2 Follow(S)={ $ ) , } R2 S-> ( L ) . I6 Follow(S)={ $ ) , } R3 L-> S . I5 Follow(L)={ ) , } R4 L-> L , S . I8 Follow(L)={ ) , }

8. Step :5 construct parsing table Label the rows of table with no. of iterations Divide the Column into two parts Action part: terminal symbols Goto part: Nonterminal symbols ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 label Production Ending iteration Follow(LHS) R0 S’-> S . I1 Follow(S’)={ $ } R1 S-> a . I2 Follow(S)={ $ ) , } R2 S-> ( L ) . I6 Follow(S)={ $ ) , } R3 L-> S . I5 Follow(L)={ ) , } R4 L-> L , S . I8 Follow(L)={ ) , } Goto ( I0, S ) 1 Goto ( I3, ( ) 3 Goto ( I0, a ) 2 Goto ( I4, ) ) 6 Goto ( I0, ( ) 3 Goto ( I4, , ) 7 Goto ( I3, L ) 4 Goto ( I7, S ) 8 Goto ( I3, S ) 5 Goto ( I7, a ) 2 Goto ( I3, a ) 2 Goto ( I7, ( ) 3

9. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

10. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

11. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

12. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

13. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

14. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

15. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

16. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 $ 0(3 L4 , 7 a 2 ) $ R1 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

17. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 $ 0(3 L4 , 7 a 2 ) $ R1 $ 0(3 L4 , 7S 8 ) $ R4 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

18. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 $ 0(3 L4 , 7 a 2 ) $ R1 $ 0(3 L4 , 7S 8 ) $ R4 $ 0(3L 4 ) $ S6 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

19. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 $ 0(3 L4 , 7 a 2 ) $ R1 $ 0(3 L4 , 7S 8 ) $ R4 $ 0(3L 4 ) $ S6 $ (3L4) 6 $ R2 label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .

20. Step :6 String parsing Let string w=( a,a ) derived from the given grammar S – Shift action * shift input symbol to the stack * shift number to the stack R – Reduce action * pop 2 times of RHS symbols * shift LHS to the stack * find the number in the parsing table for the last two elements in the stack ACTION GOTO a ( ) , $ S L S2 S3 1 1 accept 2 R1 R1 R1 3 S2 S3 5 4 4 S6 S7 5 R3 R3 6 R2 R2 R2 7 S2 S3 8 8 R4 R4 Stack Input Action $ ( a,a )$ S3 $ 0( 3 a ,a )$ S2 $ 0(3 a 2 , a)$ R1 $ 0(3 S 5 , a)$ R3 $ 0(3 L 4 , a)$ S7 $ 0(3 L4 , 7 a )$ S2 $ 0(3 L4 , 7 a 2 ) $ R1 $ 0(3 L4 , 7S 8 ) $ R4 $ 0(3L 4 ) $ S6 $ (3L4) 6 $ R2 $ 0S 1 $ accept Hence the string parsed successfully !!!!!! label Production R0 S’-> S . R1 S-> a . R2 S-> ( L ) . R3 L-> S . R4 L-> L , S .