Explanations about FOLLOW function - Grammar

Question

I've some problems to understand the function FOLLOW. I cannot calcule follow functions of a grammar and that's not good. I tried exercises to understand this function and in particulary this exercise, I've this grammar :

S -> E

E -> T E'

E' -> + T E' | minus T E' |

T -> F T'

T' -> * F T' |

F -> id | ( F'

F' -> E ) | n )

Here the results of the calculating of follow function :

S $

E ), $

E' ), $

T +, minus, ), $

T' +, minus, ), $

F *, +, minus, ), $

F' *, +, minus, ), $

I really don't understand why the FOLLOW(T)=FOLLOW(T') = { +, minus, ), $ } In the grammar that I give, theterminal symbols plus and minus never appears on the right of T or T' so if someon can explain me this, it will be cool

Answer 1

Conceptually, FOLLOW(X) is the set of tokens that can come AFTER an X in a legal sentence in the grammar. So to calculate it, you look at where X appears on the right side of a rule (any rule) and see what comes after it. In the case of T', you have

T -> F T'
T' -> * F T'

since T' is the last thing on the rhs in both cases, you end up with FOLLOW(T') = FOLLOW(T) ∪ FOLLOW(T'), which is equivalent to FOLLOW(T') = FOLLOW(T).

For T you have:

E -> T E'
E' -> + T E'

which gives you FOLLOW(T) = FIRST(E') ∪ FOLLOW(E) ∪ FOLLOW(E') -- the FOLLOWs are included because E' expands to ε. Depending on exactly whose formulation of FIRST and FOLLOW you use, that may mean that ε ∈ FIRST(E') (in which case you remove it from FOLLOW(T)) or that NULLABLE(E') = true, but the overall effect on FOLLOW(T) is the same -- it gets + and minus from FIRST(E') and ) and $ from FOLLOW(E)