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