lr parsers bottom up parsers slr parser.pptx

parsers

1. LR Parsers

2. Left- to- Right scan Rightmost Derivation In Reverse Number Of Input Symbols Of Look Ahead L L R R ( k k) LR Parsers

3. Types of LR Parsers Simple LR- Parser (SLR) Canonical LR Parser (CLR) LALR Parser.

4. LR Parsing Engine a 1 a 2 … a i … a n $ The LR Parsing Algorithm Input Scanner s m X m s m- 1 X m- 1 … s Stack Parser Generator Action Goto Grammar Compiler Construction LR Parsing Tables

5. Parse Table The LR Shift- Reduce Parsers can be efficiently implemented by computing a table to guide the processing The Parsing Table consists of two parts : A Parsing Action Function and A GOTO function .

6. LR Driver Program The LR driver Program determines S m , the state on top of the stack and a i , the Current Input symbol . It then consults Action[ S m , a i ] which can take one of four values: Shift Reduce Accept Error

7. If Action[ S m , a i ] = Shift S Where S is a State , then the Parser pushes a i and S on to the Stack . If Action[ S m , a i ] = Reduce A  β , Then a i and S m are replaced by A if S was the state appearing below a i in the Stack, then GOTO[S, A] is consulted and the state pushed onto the stack.

8. If Action[ S m , a i ] = Accept , Parsing is completed If Action[ S m , a i ] = Error , The Parser discovered an Error.

9. 24 Augmented Grammar If G is a Grammar with Start Symbol S , the Augmented Grammar G’ is G with a New Start Symbol S`, and New Production S`  S$. . The Purpose of the Augmented Grammar is to indicate to the parser when it should stop parsing and announce acceptance of the input

10. LR(0) Items An LR(0) Item of a Grammar G is a Production of G with a Dot ( ) at some position of the right side. . Production A  XYZ yields the Four items: A  •XYZ We hope to see a string derivable from XYZ next on the input. A  X•YZ We have just seen on the input a string derivable from X and that we hope next to see a string derivable from YZ next on the input.

11. A  XY•Z A  XYZ• The production A  generates only one item, A  •. Each of this item is a Viable prefixes Closure Item : An Item created by the closure operation on a state. Complete Item : An Item where the Item Dot is at the end of the RHS.

12. SLR Parser SLR Parser stands for Simple LR . The letters “SLR” stand for “Simple”, “Left” and “Right”. “Left” indicates that the input is read from left to right and The “Right” indicates that a right- derivation is built

13. Example: SLR Parser 56 for the Following Construct the SLR Parser Grammar Context Free Grammar: E → E + T E → T T → T * F T → F F → ( E ) F → id

14. . 57 Augmented Grammar: E ’ → E# E → E + T E → T T → T * F T → F F → ( E ) F → id Context Free Grammar: E → E + T E → T T → T * F T → F F → ( E ) F → id Step 1: Define a Augmented Grammar

15. . E ’ → E# E → E + T E → T T → T * F T → F F → ( E ) F → id E → E + T E → T T → T * F . . Step2 : Constructing SLR Automaton Context Free Grammar : Adding the SLR Item E ’ → . E# T → . F F → . ( E ) F → . id

16. E’  . E# E  . E+T E  . T T  . T*F T  . F F  . (E) F  . id S 11 F  (E) . T  T*F . S 10 E  E + T . T  T . * F S 9 S 8 T  T* . F F  . (E) F  . id S 7 E  E+ . T T  . T*F T  . F F  . (E) F  . id S 6 F  id . S 5 S F  . id S 4 F  ( . E) E  . E+T E  . T T  . T*F T  . F F  . (E) T  T . * F E S 2  T . T  F . S 3 E’  E . # E  E . +T S 1 E T F id + * T * ( S 3 F id S 5 S 4 ( ( id S 5 F E ) T F ( id F  (E . ) E  E . +T + 59 S 6

17. I : E ’ → . E# E → . E + T E → . T T → . T * F T → . F F → . ( E ) F → . id I 2 : Goto(I ,T) E → T . E → T . *F I 3 : Goto(I ,F) T → F . I 1 : Goto(I ,E ) E → E . # E → E . +T I 4 : Goto(I ,( ) F → ( . E) E → . E+T E → . T T → . T * F T → . F F → . ( E ) F → . id T → id . 5 I : Goto(I ,id) I 6 :Goto(I 1 ,+) E → E+ . T T → . T * F T → . F F → . ( E ) F → . id I 7 :Goto(I 2 ,*) E → T* . F F → . ( E ) F → . id I 8 : Goto(I 4 ,E) E → (E . ) E → E . +T E → T . E → T . *F 2 4 I : Goto(I ,T) I 3 :Goto(I 4 ,F) T → F . I 9 :Goto(I 6 ,T) E → E+T . T → T . * F I 10 :Goto(I 7 ,F) T → T * F . T → (E) . I 11 :Goto(I 8 ,) ) I 3 :Goto(I 6 ,F) T → F . I 4 :Goto(I 6 ,( ) I 5 :Goto(I 6 ,id) T → id . I 3 :Goto(I 4 ,F) I 5 :Goto(I 7 ,id) I 4 :Goto(I 4 ,( ) I 5 :Goto(I 4 ,id) I 7 :Goto(I 9 ,* ) I 4 :Goto(I 7 ,( ) I 6 :Goto(I 8 ,+) Constructing the SLR Items 60

18. S S 1 S 2 S 4 S 6 S 3 S 11 S 5 S 9 ( id S 3 F S 5 S 4 E T F id ( + T S 7 S 8 S 10 S 5 S 4 ( id * F T id F S 3 E ( ) + S 7 * Construction of DFA for SLR Items 61

19. Construction of Follow Function E ’ → . E# E → . E + T E → . T T → . T * F T → . F F → . ( E ) F → . id Follow (E) = { # , + , ) } Follow (T) = { * , # , + , ) } Follow (F) = { * , # , + , ) } ( r1 ) ( r2 ) ( r3 ) ( r4 ) ( r5 ) ( r6 ) 62

20. Constructing the SLR Parsing Table 63 States Input Action Part Goto Part id + * ( ) # E T F S5 S4 1 2 3 1 S6 Acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 S7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5

21. String Acceptance id * id + id # STACK INPUT ACTION (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) id 5 F 5 T 2 T 2 * 7 T 2 * 7 id 5 T 2 * 7 F 10 T 2 E 1 E 1 + 6 E 1 + 6 id 5 E 1 + 6 F 3 E 1 + 6 T 9 E 1 id * id + id # id + id # id + id # id + id # id + id # + id # + id # + id # + id # I d # # # # # shift reduced by F  id reduced by T  F shift shift reduced by F  id reduced by T  T * F reduced by E  T shift shift reduced by F  id reduced by T  F E  E + T accept