Search code examples
context-free-grammar

FOLLOW Set of grammar having left factoring eliminated

I wonder what the FOLLOW set of a certain NonTerminal is, when the left-recursion of a grammar is eliminated, like in the following example grammar.

let's assume this grammar

1 E → T E’
2 E’→ + T E’ 
3 E’→ ε
4 T → F T’
5 T’→ * F T’
6 T’→ ε
7 F → ( E ) 
8 F → id

Example 1:

Let's first take a look at the part row 4 - row 8

4 T → F T’
5 T’→ * F T’
6 T’→ ε
7 F → ( E ) 
8 F → id

Is it correct, that FOLLOW(F) in this context is... ?

{*}

Explanation:

  1. If T' repeats, then F is followed by +. If, on the other hand, T' expands to ε, F is followed by ε.

Example 2:

When we broaden the context and look at the whole grammar, is it correct, that the complete FOLLOW-Set of F for this grammar is... ?

-> {'+', '*', ')', '$'}

Explanation:

  1. Look at line 5. If T' repeats, then F is followed by '*'. If, on the other hand, T' expands to ε, F is followed by ε. Thus the rule is to add FOLLOW(T') to FOLLOW(F).

-> {'*'}

  1. If T' in row 4 again expands to ε, then the rule is to add FOLLOW(T) to FOLLOW(F).

  2. If E' in line 2 expands to T' again, then T is followed by +. If E' expands to ε, then T is followed by ε. Again the Rule "Add FOLLOW(E') to FOLLOW(T) applies

-> {'+'}

  1. It applies the same as in <2>. If E' in line 1 expands to ε, the Rule "Add FOLLOW(E) to FOLLOW(T)." Which is

-> {')'}

Yours sincerely

von Spotz

EDIT:

Corrected according to the answer ot rici that FOLLOW-Sets do not contain 'ε'. That's what the rule

If A -> αB, add FOLLOW(A) to FOLLOW(B)

is for.

Also rici's hint, that Follow of T is E, as stated in Example 2: (4) and thus also the accepting symbol '$' belongs to Follow(F).

Solution

  • FOLLOW(F) is {'+', '*', ')', $} (where $ is the end-marker).

    Follow sets never include ε. You need to take ε into account when you compute FOLLOW, but you don't add it to any FOLLOW set.