Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have computed the FIRST sets.
For the following grammar:
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | id
I found that the FIRST sets are:
FIRST(E) = { (, id }
FIRST(E') = { + , ε }
FIRST(T) = { (, id }
FIRST(T') = { *, ε }
FIRST(F) = { (, id }
When it comes to computing the FOLLOW sets, I am trying to use the following rules:
1. $ goes into the set FOLLOW(S) where S is the start symbol.
2. If A -> aBb, then (FIRST(b) - { ε }) is in FOLLOW(B).
3. If A -> aB then everything in FOLLOW(A) is in FOLLOW(B)
4. If A -> aBb and ε is in FIRST(b), then everything in FOLLOW(A) is in FOLLOW(B).
Obviously, the step I am most certain here is that
FOLLOW(E)
contains $
, based on rule 1. But everything after that, I seem to have a hard time following a pattern on how to systematically compute the FOLLOW sets. For example, to compute FOLLOW(E)
, how are we supposed to approach this?
E -> TE'
, looks like A -> aB
, so everything in FOLLOW(E)
is in FOLLOW(E')
. Where to go from here? Do I compute FOLLOW(E')
? Then going to FOLLOW(E')
:
E' -> + TE'
... looks like A -> aBb
. Then that means FIRST(E') - { ε }
is in FOLLOW(T)
. So I do know that { + }
is in FOLLOW(T)
.
As you can see, with the way I have interpreted this, I am going around all over the place computing the FOLLOW of another production. Ultimately, I end up losing track on what terminal symbols go into which follow set. :(
I am for sure misunderstanding something here.
What is the right approach/ordering to compute the FOLLOW sets?