Exercise 4 Name __________________ Score __/26
(8) Find FIRST and FOLLOW sets for the grammar:
Given a non-terminal A, the set
FOLLOW(A)
consists of terminals and possibly $ is defined as:
if A is a start symbol then $ is in Follow(A).
if production B
®
a
A
g
, then First(
g
)-{
є
} is in Follow(A)
if production B
®
a
A
g
, such that
є
is in First(
g
), then Follow(A) contains Follow(B); since whatever follows B can follow A when
g=
є
if production B
®
a
A, then Follow(A) contains Follow(B); since whatever follows B can follow A
S
®
ABC
A
®
a | Cb | є
B
®
c | dA | є
C
®
e | f
(4) Give the parse table for Question 1.
Blank entries are error conditions. Rules for typical production X
® b
are:
For all
terminals
a
in FIRST(
b
) except є, [X,a] = X
® b
If
b
=є or if є is in FIRST(
b
) then: For all
a
in FOLLOW(X), [X,a]=X
®
є
(2) For grammar
A
®
Ac | Ad | e | f
which strings are valid?
e
ccce
cdccd
ecdccdf
fcdcd
(2) Remove left-recursion in the grammar: A
®
Ac | Ad | e | f
(4) Using GRAMMAR 3.1 and the LR parsing TABLE 3.19, give a bottom-up parse with the following of: x:=a+3
