schonber@griffin 130% more ass4.html Solution to Assignment 3

Compiler Construction
Spring 2000
Solutions to Assignment III

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.
Answer: 

FIRST(R) = {a, b, (}
FOLLOW(R) = {|, *, ), a, b, (, $}

b) Show the grammar is ambiguous.
Answer:

There are two left-most derivations for the string "ab | a":

R => RR => aR => aR | R => ab | R => a b |  a,      that is to say  a (b | a)
R => R | R => RR | R => aR | R => ab | R => ab | a. that is to say (ab) | a

(similar to the arithmetic ambiguity in a + b * c when we give all arithmetic
operators the same precedence).

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

A new grammar is (e is the empty symbol):

R  => B R'
R' => '|' R | e
B  => A B'
B' => B | e
A  => F A''
A' => * A''
A'' => A' | e
F  => a | b | ( R )
 
This corresponds to the standard strategy of creating different non-terminal
symbols for each level of binding we want to impose.

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

SYMBOL	     FIRST	      FOLLOW

F	     a, b, (	      *, a, b, (, |, ), $
A'	     *		      a, b, (, |, ), $
A''	     *, e	      a, b, (, |, ), $
A	     a, b, (	      a, b, (, |, ), $
B	     a, b, (	      |, ), $
B'	     a, b, (, e	      |, ), $
R'	     |, e	      $, )
R	     a, b, (	      $, )

It can be verified that the new grammar is LL(1) by constructing a
parsing table that has no conflicts (omitted here).