Compiler Construction
Fall 1998
Assignment III


Due : October 20.

1. Consider the following grammar:

      R =>  R  '|' R
      R =>  R R
      R => R *
      R => ( R ) 
      R => a | b

where the terminals are {  |, *, (, ), a, b }. This grammar generates regular
expressions over a,b involving alternation, concatenation, and repetition.

a) Compute FIRST and FOLLOW for the only non-terminal in this grammar.

b) Build the LR(0) automaton for this grammar.

c) Identify shift-reduce conflicts, and resolve them so as to obtain the
usual precedence for the operators involved:

             repetition > concatenation > alternation.