Lesson 8: Bottom Up Parsing and Derivations in Compiler Theory

In this lesson, teacher Linus Kllberg explains the concept of bottom up parsing and how it is used in compiler theory. The lesson also covers derivations and reductions in grammar, with examples provided.

• Uploaded on | 1 Views
• agate

About Lesson 8: Bottom Up Parsing and Derivations in Compiler Theory

PowerPoint presentation about 'Lesson 8: Bottom Up Parsing and Derivations in Compiler Theory'. This presentation describes the topic on In this lesson, teacher Linus Kllberg explains the concept of bottom up parsing and how it is used in compiler theory. The lesson also covers derivations and reductions in grammar, with examples provided.. The key topics included in this slideshow are bottom up parsing, derivations, reductions, grammar, compiler theory,. Download this presentation absolutely free.

Presentation Transcript

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

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