Lesson 8: Bottom Up Parsing and Derivations in Compiler Theory

1. Lesson 8 CDT301 Compiler Theory, Spring 2011 Teacher: Linus Kllberg

2. 2 Outline Bottom-up parsing: Derivations and reductions Shift-reduce parsing LR parsing

3. BOTTOM-UP PARSING 3

4. Derivations and reductions Grammar: E E + T | T T T * F | F F ( E ) | id 4

5. Derivations and reductions id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E E T T * F F * F id * F id * id

6. Derivations and reductions Leftmost derivation, E * lm id * id : E T T * F F * F id * F id * id Rightmost derivation, E * rm id * id : E T T * F T * id F * id id * id 6

7. Derivations and reductions Reduction = reverse derivation Rightmost derivation: E T T * F T * id F * id id * id Leftmost reduction: id * id F * id T * id T * F T E 7

8. Handles 8 Reduction Handle id * id F * id T * id T * F T E F id T F F id T T * F E T

9. Derivations and reductions id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E id * id F T F T E id * id F * id T * id T * F T E

10. Exercise (1) Given the previous expression grammar, E E + T | T T T * F | F F ( E ) | id a) write down the leftmost reduction of the string ( id + id ). b) write down the handles in all the sentential forms along the reduction. 10

11. Shift-reduce parsers Performs a leftmost reduction More powerful than top-down parsers Commonly generated by parser generators 11

12. Shift-reduce parsers Four actions: Shift: consume and shift a terminal onto a stack Reduce: pop a handle from the stack and push the nonterminal Accept Error 12

13. Shift-reduce parsing in action Stack Input Action $ id * id $ sh. id $ id * id $ red. by F id $ F * id $ red. by T F $ T * id $ sh. * $ T * id $ sh. id $ T * id $ red. by F id $ T * F $ red. by T T * F $ T $ red. by E T $ E $ accept 13 id * id F * id T * id T * F T E

14. Exercise (2) Similar to the previous demonstration, do a shift-reduce parse of the same string, ( id + id ), as in the previous exercise, using the same grammar: E E + T | T T T * F | F F ( E ) | id Tip: reuse your leftmost reduction from the previous exercise. 14

15. LR(k) parsing Implementation of shift-reduce parsing L eft-to-right scanning of the input, R ightmost derivation in reverse k = 0 or k = 1: nr of lookahead tokens 15

16. Why LR parsing? LR(k) more powerful than LL(k) Efficient Early detection of syntax errors 16

17. Overview of LR parsing Table-driven Shifts states onto the stack One state represents: symbol + context 17

18. (1) E E + T (2) E T (3) T T * F (4) T F (5) F ( E ) (6) F id 18 State ACTION GOTO id + * ( ) $ E T F 0 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

19. LR parsing algorithm push state 0 repeat until success: s state on stack top a lookahead token case ACTION [s, a] of shift t: consume a push t reduce by A : pop | | states t state on stack top push GOTO [t, A] accept: success true empty: handle error 19

20. LR parsing in action Stack Input Action $ 0 id * id $ sh. 5 $ 0 5 id * id $ red. by (6) F id $ 0 3 F * id $ red. by (4) T F $ 0 2 T * id $ sh. 7 $ 0 2 T 7 * id $ sh. 5 $ 0 2 T 7 * 5 id $ red. by (6) F id $ 0 2 T 7 * 10 F $ red. by (3) T T * F $ 0 2 T $ red. by (2) E T $ 0 1 E $ accept 20

21. Exercise (3) Parse the string hxe. (1) S h B e (2) B B A (3) B (4) A x (5) A t 21 State ACTION GOTO h x t e $ S B A 0 s2 1 1 acc 2 r3 r3 r3 3 3 s6 s7 s4 5 4 r1 5 r2 r2 r2 6 r4 r4 r4 7 r5 r5 r5

22. Constructing the parsing table Several methods: Simple LR (SLR) Canonical LR LookAhead LR (LALR) Next time: SLR 22

23. Conclusion Bottom-up parsing vs. top-down parsing Derivations and reductions Sentential forms Handles Shift-reduce parsing LR parsing 23

24. Next time Creating LR parsing tables using the simple LR method 24