parsingcompiler-constructionlr1

Computing the FIRST & FOLLOW sets of a grammar

I have the following grammar:

S -> aXab
S -> Y
X -> bYa
X -> epsilon
Y -> Sc

I have computed the first and follow sets for this grammar and I would like to know if it is correct. Here is my solution:

First Sets:
S -> {a} 
X -> {b,epsilon}
Y -> {a}

Follow Sets:
S -> {$,c} 
X -> {a}
Y -> {c,a}

Any help is appreciated. Thanks.

Solution

  • FIRST sets are correct. FOLLOW(Y) should be {$,c,a}

    FOLLOW(A) definition is

    FOLLOW(A) of non-terminal A is the set of terminal symbols that can follow in the
    derivation sequence

    FOLLOW(Y), check where it is there in the right-hand side

            1) X -> bYa

    when this production is taken for derivation what follows Y is 'a'

            2) S -> Y

    when this production is taken for derivation what follows Y is, What ever that was following S. FOLLOW(S)={$,c}

         FOLLOW(Y)={$,a,c}