Due Monday, October 31st, 10:10am.

Recall that a grammar is LR(0) if an LR(0) parsing table constructed for it has no conflicts. It is SLR if the same table has no SLR conflicts. Note that every LR(0) grammar is an SLR grammar.

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

S -> E eof
E -> id
E -> id ( E )
E -> E + id

• Is the grammar LR(0)? Justify your answer.
• Compute the follow sets of S and E.
• Is the grammar SLR? Justify your answer.

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

S -> SS
   | (S)
   | ()

• Locate the shift/reduce conflict in the table.

The presence of a conflict tells us that the grammar is not LR(0).

• Compute the follow set of S.
• Is the grammar SLR? Justify your answer.

• Is there an SLR grammar G' that specifies the same language as the language of the grammar G from Problem 2? Justify your answer rigorously.