CS 480: Translators

Winter Term, 2005, Professor Budd

Homework Assignment 3

Due Friday, January 28

LR states and Manipulation

The following is a simplified version of just a portion of our grammar.

start::=statement
statement::=reference = expression
expression::=reference
|constant
reference::=identifier
|reference . identifier
|reference [ expression ]

I've added the traditional start production, and removed a lot of the extra productions. Using this grammar, answer the following four questions

  1. Write the item sets for each of the states in the DFSA that the LR parsing algorithm would generate for this grammar. (You don't need to keep the lookahead symbols, just the items).

  2. Draw the DFSA that the LR parsing algorithm would generate for this grammar. Number the productions and number your states, and mark the final states for each of the productions, which which production they correspond to.

  3. Show the sequence of shift and reduce steps (and the state of the stack at each step) during the parse of the input ``x = y''

  4. Do the same for the input ``x.a = y[b.c]''