Compiler Construction
Spring 2000
Assignment III


Due : March 1.

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) Show the grammar is ambiguous.

c) construct an equivalent unambiguous grammar that gives the operators
star (repetition), concatenation, and alternation the usual precedences :

             repetition > concatenation > alternation.

d) Build the FIRST and FOLLOW set for this new grammar. Is it LL (1)?