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