Java Reference
In-Depth Information
Rule 7, F ::=
(
E
)
, adds
)
to follow(E), so
follow(E) = f
)
,
#
g
Rule 8 gives us nothing.
Summarizing round 1 of step 3, gives
follow(E) = f
)
,
#
g
follow(E
0
) = f
#
g
follow(T) = f
+
,
#
g
follow(T
0
) = f
+
,
#
g
follow(F)
= if
+
,
*
,
#
g
Now, in round 2 of step 3, the
)
that was added to follow(E) trickles down into the
other follow sets:
From rule 1, E ::= TE
0
, because rst(E
0
) contains , follow(T) contains follow(E). Also,
follow(E
0
) contains follow(E). So, we have
follow(E
0
) = f
)
,
#
g
follow(T)
= if
+
,
)
,
#
g
From rule 4, T ::= FT
0
, because rst(T
0
) contains , follow(F) contains follow(T). Also,
follow(T
0
) contains follow(T). So, we have
follow(T
0
) = f
+
,
)
,
#
g
follow(F)
= if
+
,
*
,
)
,
#
g
So round 2 produces
follow(E) = f
)
,
#
g
follow(E
0
) = f
)
,
#
g
follow(T) = f
+
,
)
,
#
g
follow(T
0
) = f
+
,
)
,
#
g
follow(F)
(3.24)
= if
+
,
*
,
)
,
#
g
Round 3 of step 3 adds no new symbols to any set, so we are left with (3.24).
Constructing the LL(1) Parse Table
Recall, assuming both and are (possibly empty) strings of terminals and non-terminals,
table[Y;a] = i, where i is the number of the rule Y ::= X
1
X
2
:::X
n
if either
1. X
1
X
2
:::X
n
) a, or
2. X
1
X
2
:::X
n
) , and there is a derivation S
#
) Y a, that is, a can follow Y in a
derivation.
This definition, together with the functions, first and follow, suggests Algorithm 3.5.
Search WWH ::
Custom Search