Compiler Construction
Fall 1998
Assignment II


Due : March 22. (after Spring break).

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.

2. From text: prob. 4.15. Build SLR tables for the dangling-else grammar,
find the conflicts, fix the table so that the conflict is resolved to the
nearest if-statement.