Homework 05

Due Wednesday, 10 November, 10:10am. Please hand it in to Hossein before the beginning of the exercise session.

Problem 1

Construct an LR(0) parsing table for the following grammar.

S -> SS
   | (S)
   | ()
  • Locate the shift/reduce conflict in the table.
  • Using some test inputs, resolve the conflict in favor of a shift or a reduction.

Problem 2

Construct an SLR parse table for the following grammar.

S -> E + E
E -> E * a
S -> a
E -> a
  • Is SLR powerful enough to resolve the conflicts?
  • Draw the LR(1) automaton for parsing.
  • Determine the set of states that can be merged for an LALR parser.