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.

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

b) Show the grammar is ambiguous.

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.

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).
```