Search code examples
context-free-grammarcompiler-theory

how to remove Circular Dependency in FOLLOW set

Consider a short gramma bellow

S -> Bc | DB
B -> ab | cS
D -> d | epsilon

The FIRST set is

FIRST(S) ={a,c,d}
FIRST(B) = { a,c }
FIRST(D)= { d, epsilon }

in it the 

Follow(S)={ Follow(B) }

and 

Follow(B) ={ c , Follow(S) }

my question is that how to resolve this circular dependency ?

Solution

  • This circular dependency shouldn't be there to start with. this is the algorithm for finding 'follow's:

    Init all follow groups to {}, except S which is init to {$}.
    While there are changes, for each A∈V do:
      For each Y → αAβ do:
        follow(A) = follow(A) ∪ first(β)
        If β ⇒* ε, also do: follow(A) = follow(A) ∪ follow(Y)

    So in your case, you should get:
    Follow(S)={c,$}
    Follow(B)={c,$}
    Follow(D)={a,c}