I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!

enter image description here

  • $\begingroup$ Perhaps this will help: stackoverflow.com/a/29200860/1566221 $\endgroup$ – rici Feb 22 at 19:49
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$ – D.W. May 20 at 5:04
  • $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please edit your question accordingly. You mentioned it is from a MOOC; I encourage you to indicate which MOOC (title, a link to it, which exercise number, etc.), so others with a similar question are more likely to be able to find this via search. $\endgroup$ – D.W. May 20 at 5:04

To find the follow of S, I feel that it would be helpful to calculate all the firsts of all the variables as it helps a lot. First, let us see all the rules to find the first as they will be helpful.

1. For terminal a, First(a) = {a}.
2. For production A -> a, add 'a' to First(A).
3. For production A -> πœ€, add 'πœ€' to First(A).
4. For production A -> BCD, add First(B) to First(A).
5. For production A -> BCD and πœ€ ∊ First(B), add First(CD) to First(A).

It would be easier for me to explain if we number all the productions, so we number the productions as follows:

1. S -> A(S)B
2. S -> πœ€
3. A -> S
4. A -> SB
5. A -> x
6. A -> πœ€
7. B -> SB
8. B -> y

Now as it is a recursive function, it would be better if we go in cycles to find the answer until we find a cycle in which the answer hasn't changed.

Firstly, find first using all the productions which start with a terminal, i.e. productions 2, 5, 6, 8.

Round 1

First(S) : {πœ€}, First(A) : {x, πœ€}, First(B) : {y}

From production 1, First(A) ∊ First(S), therefore add it. Also, as πœ€ ∊ First(A), add ( to First(S).

From production 3, First(S) ∊ First(A), therefore add it. Also from production 4, as πœ€ ∊ First(S), add First(B) to First(A).

From production 7, First(S) ∊ First(B), therefore add it.

Round 2

First(S) : {πœ€, x, (}, First(A) : {x, πœ€, (, y}, First(B) : {y, x, πœ€, (}

Add all the steps performed in round 2, again in round 3.

Round 3

First(S) : {πœ€, x, (, y}, First(A) : {x, πœ€, (, y}, First(B) : {y, x, πœ€, (}

This is the final outcome. After this, if you perform the steps again, you will get the same values of First.

Now we will find follow. First, let us understand the rules of follow as it will be helpful.

1. For start symbol S, add $ to follow(S).
2. For production A -> BC, add follow(A) to follow(C).
3. For production A -> Bb, add b to follow(B).
4. For production A -> BCD, add first(CD) to follow(B). 

Also, we don't add πœ€ in the follow.

As S is the start symbol, add $ to Follow(S)(rule 1).

To find other elements of Follow(S), find all the productions where S is in RHS. Here they are 1, 3, 4, 7.

From production 1, add ) to Follow(S)(rule 3), add ( to Follow(A)(rule 3), add follow(S) to follow (B)(rule 2).

Follow(S) = {$, )}, Follow(A): {(}, Follow(B): {$, )}

From production 3, add Follow(A) to Follow(S)(rule 2).

Follow(S) = {$, ), (}, Follow(A): {(}, Follow(B): {$, )}

From production 4, add Follow(A) to Follow(B)(rule 2) and add First(B) to Follow(S)(Rule 4)

Follow(S) = {$, ), (, x, y}, Follow(A): {(}, Follow(B): {$, ), (}

From production 1 again, add Follow(S) to Follow(B)(rule 2)

Follow(S) = {$, ), (, x, y}, Follow(A): {(}, Follow(B): {$, ), (, x, y}

Now we have found first and follow of all the variables. The actual solution might not be this big. I have tried to explain everything so it's a bit bigger. Hope you liked and understood the solution.


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.