Compiler Design Unit 2

Parser

1. UNIT II SYNTAX ANALYSIS Mrs.D.Jena Catherine Bel Assistant Professor, CSE, Velammal Engineering College

2. Parser Program that take string ‘w’ as input and produce a parse tree for that string Types Top-down Parsing Recursive Descent Parsing Predictive Parsing Bottom-up Parsing Shift Reduce Parsing Operator Precedence Parsing LR Parsing Mrs.D.Jena Catherine Bel,AP/CSE, VEC 2

3. Bottom-up Parsing Methods Shift-reduce Parsing LR Parsing SLR LALR CLR Mrs.D.Jena Catherine Bel,AP/CSE, VEC 3

4. Shift Reduce Parsing Construct the parse tree for the string beginning at the leaves (bottom) and working towards the root (top). Equivalent to reducing the given string to the start symbol Mrs.D.Jena Catherine Bel,AP/CSE, VEC 4

5. Shift Reduce Parsing Consider the Grammar S  aAcBe A  Ab | b B  d The parsing of the string abbcde is shown below. a b bcde A  b aAbcde A  Ab aAcde B  d aAcBe S  aAcBe S Mrs.D.Jena Catherine Bel,AP/CSE, VEC 5

6. Handles Reduction : replacement of the right side of a production by the left side Requires the identification of a sub string in every sentential form and the sub string is called Handle Handle: right sentential form γ is a production A  β and a position of γ String β is found and replaced by A to produce the previous right sentential form in a rightmost derivation of γ Mrs.D.Jena Catherine Bel,AP/CSE, VEC 6

7. Handle Pruning Process of reducing the given string w to the starting symbol of the grammar Locate the handle and replace it by the left side of the production Gives the reverse of the right most derivation, called Canonical reduction sequence. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 7 The parsing of the string abbcde is shown below. a b bcde A  b a Ab cde A  Ab aAc d e B  d aAcBe S  aAcBe S

8. Stack Implementation of Shift reduce Parsing data structures - stack and an input buffer $ denotes bottom of the stack. The buffer is initialized with the string to be parsed. The parser operates by shifting zero or more input symbols until a handle β is on top of the stack. Replace β by left side of the appropriate production. Repeat until it has detected an error or until the stack contains the start symbol and the input buffer is empty. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 8

9. Actions of the Parser Shift : Shift next input symbol to the stack from the input buffer. Reduce : When the parser finds the right end of the handle on the top of the stack, Locate the left end of the handle within the stack Decides the non-terminal to replace the handle. Accept : The parser announces the successful completion of the parsing. Error : The parser discovers that a syntax error has occurred and calls an error recovery routine. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 9

10. Shift Reduce Parsing Example 1 Consider the grammar E  E + E | E * E | ( E ) | id Show how the string id+id *id is parsed by the Shift-reduce parser.   Parsing Process Step 1: Construct the right most derivation for id + id * id Mrs.D.Jena Catherine Bel,AP/CSE, VEC 10

11. Shift Reduce Parsing Step 2: Handle Pruning Mrs.D.Jena Catherine Bel,AP/CSE, VEC 11

12. Shift Reduce Parsing Step 3: Stack Implementation for id + id * id Mrs.D.Jena Catherine Bel,AP/CSE, VEC 12

13. LR PARSER bottom up parsers scanning the input from left to right and construct the right most derivation in reverse consists of a driver routine and a parsing table. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 13

14. The techniques used for producing LR parsing table are Simple LR , which is the simple method but it may fails to produce parsing table for certain grammar. Canonical LR, which is the most powerful and work for large class of grammars but very expensive to implement. Look-ahead LR, having intermediate power in between SLR and Canonical LR methods. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 14

15. Structure of an LR Parser Mrs.D.Jena Catherine Bel,AP/CSE, VEC 15 The parser has an input buffer, a stack and a parsing table. The stack contains a string of the form s X 1 s 1 X 2 s 2 … s m-1 X m s m , s m on the top X i is a grammar symbol and each s i is a symbol called state

16. Structure of an LR Parser Parsing table consists of two parts ACTION and a GOTO function Driver routine determines s m , the state currently on the top of the stack and a i , the current input symbol ACTION[ s m , a i ], and performs anyone of the actions shift s, reduce A  b, accept or error The GOTO function takes a state and grammar symbol as arguments and produce a state as output Mrs.D.Jena Catherine Bel,AP/CSE, VEC 16

17. Configuration of an LR parser A pair whose first component is the stack contents and the second component is the unexpended input. (s X 1 s 1 X 2 s 2 … s m-1 X m s m , a i a i+1 a i+2 … a n $ ) Read a i and s m and consult the table entry ACTION[ a i , s m ]. If ACTION[ s m , a i ] = shift s, then the parser and enters into the configuration (s X 1 s 1 X 2 s 2 … s m-1 X m s m a i s a i+1 a i+2 … a n $ ) . The top state is s and the current input symbol a i+1 . If ACTION[ s m , a i ] = reduce A  b, then the parser enters into the configuration (s X 1 s 1 X 2 s 2 … X m -r s m -r A s, a i a i+1 a i+2 … a n $ ) where s = GOTO [ s m -r , A] and r is the length of β . Pops 2r number of symbols from the stack, push A (the left hand side of the production) and push s, the entry for GOTO [ s m -r , A], onto the stack. If ACTION[ s m , a i ] = accept, then parsing is completed. If ACTION[ s m , a i ] = error, calls an error recovery routine Mrs.D.Jena Catherine Bel,AP/CSE, VEC 17

18. SLR Parser LR parsing table is a Deterministic finite automata that recognizes all viable prefixes. every state available in the DFA has a set of items called LR (0) items or simply items. construct the canonical LR (0) items for the augmented grammar G’ – from the grammar G The procedures CLOSURE and GOTO are defined to construct the set of items C . Mrs.D.Jena Catherine Bel,AP/CSE, VEC 18

19. SLR Parser Mrs.D.Jena Catherine Bel,AP/CSE, VEC 19

20. SLR Parser Example Mrs.D.Jena Catherine Bel,AP/CSE, VEC 20

21. The initial state I is obtained by CLOSURE { ( E’  .E ) }. Finding the transitions from I for all the grammar symbols. This is obtained by the GOTO function. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 21 SLR Parser

22. SLR Parser Mrs.D.Jena Catherine Bel,AP/CSE, VEC 22

23. SLR Parsing table Construction algorithm Input : Canonical Set of Items C. Output : If possible an SLR parsing table with ACTION and GOTO. Method : Let C = { I , I 1 , I 2 , … I n } , the parsing actions for the state i are defined as follows. Step 1. If A  a.ab is in I i , GOTO ( I i , a ) = I j then ACTION [ i , a ] = “ shift j”. Step 2. If A  a. is in I i then ACTION [ i , a ] = “ reduce A  a ” " a in FOLLOW(A). Step 3. If S’  S. is in I i then ACTION [ i , $ ] = accept. Step 4. If GOTO ( I i , A ) = I j then GOTO ( i , A ) = j. Step 5. Make all the undefined entries as Error. Step 6. The initial state of the parser is the state constructed from the item [ S’  .S ]. Mrs.D.Jena Catherine Bel,AP/CSE, VEC 23

24. SLR Parser Mrs.D.Jena Catherine Bel,AP/CSE, VEC 24

25. Stack Input Action (to be performed) 0 id* id+id $ Shift id 0id5 * id+id $ Reduce F  id 0F3 * id+id $ Reduce T  F 0T2 * id+id $ Shift * 0T2*7 id+id $ Shift id 0T2*7id5 +id$ Reduce F  id 0T2*7F10 +id$ Reduce T  T * F 0T2 +id$ Reduce E  T 0E1 +id$ Shift + 0E1+6 id$ Shift id 0E1+6id5 $ Reduce F  id 0E1+6F3 $ Reduce T  F 0E1+6T9 $ Reduce E  E + T 0E1 $ Accept Mrs.D.Jena Catherine Bel,AP/CSE, VEC 25