CODEWITHSUNDEEP
compiler-constructionsetgrammar
atsa
atsa

Reputation: 13

Building a FOLLOW set of a grammar

I have a grammar which has the left recursion removed and it is left factored also.

I created FIRST sets already, that was quite simple task, but constructing the FOLLOW sets is problematic. I tried to find helpful examples but failed to find any that would help me.

Here is the grammar:

St is the start symbol. 

St -> St'
St' -> i S'
E -> i E'
E' -> [ E ] E'
E' -> ε
S' -> = E
S' -> [ E ] = E

And the corresponding FIRST sets are 

E = { i }
E' = { [, ε }
S' = { [, = }
St = { i }
St' = { i }

Now, the rules for building the follow sets are from http://www.jambe.co.nz/UNI/FirstAndFollowSets.html are quite simple and yet i do not know how to apply them correctly.

Follow sets i have constructed so far are:

E = {}
E' = {}
S' = {}
St = {$}
St' {$}

but after this i have no clue how to proceed. Some tips would be most welcome, i'm not expecting to get complete solution to this problem, just some tips so i can understand how building follow sets work.

Upvotes: 0

Views: 165

Answers (1)

Arif H-Shigri
Arif H-Shigri

Reputation: 1136

Rules for Follow Sets

  • First put $ (the end of input marker) in Follow(S) (S is the start symbol) If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).

  • If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)

  • if there is a production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B) According To Above Rules Your Answer is :

    E = { ] }

E' = { ] }

S' = { $ }

St = { $ }

St'= { $ }

Upvotes: 2

Related Questions