COMS W4115
Programming Languages and Translators
Lecture 9: Bottom-Up Parsing
February 18, 2015

Lecture Outline

  1. Bottom-up parsing
  2. LR(1) parsing
  3. Constructing a simple LR(1) parser
  4. DFA for viable prefixes

1. Bottom-up Parsing

2. LR(1) Parsing

3. Constructing a Simple LR(1) Parsing Table for a Grammar

4. DFA for Viable Prefixes

5. Practice Problems

    Consider the following grammar G:
  1. Construct a rightmost derivation and parse tree for the input string aaa*+$.
  2. Show the handle in each sentential form in the derivation.
  3. Construct the canonical collection of sets of LR(0) items for the augmented grammar.
  4. Construct an SLR(1) parsing table for G.
  5. Show how your SLR(1) parser processes the input string aaa*+$.

6. Reading



aho@cs.columbia.edu