CODEWITHSUNDEEP
grammarcontext-free-grammar
subb
subb

Reputation: 1568

Follow sets for self-recursive rules

Alright, I'm trying to understand follow sets and I think I got it except for one thing:

X -> a X
X -> b X
X -> epsilon

Following the rules of this page, FOLLOW(X) should contains $, the end of file character (rule 1). Then, following rule 3, FOLLOW(X) contains everything of FOLLOW(X) which makes my brain melt.

To me, intuitively, FOLLOW(X) should be {a,b,$}, but trying this example in kfg Edit gives me only {$}. Why?

Upvotes: 1

Views: 756

Answers (1)

Gunther
Gunther

Reputation: 5256

FOLLOW(X) trivially is a subset of itself, so rule 3 does not contribute anything when applied to right-recursive productions.

While this is easily approached descriptively, your difficulty may originate from thinking about algorithms to compute. For computing FOLLOW sets, you could iteratively fill them according to the rules up to saturation. Then you don't need do anything for the trivial case either.

There is however no rule that gets a or b into FOLLOW(X), and I can't see any reason to expect them in FOLLOW(X). The grammar is simple enough to imagine the complete set of syntax trees that it can generate:

                                                                  X
                                                                 /|
                                                 X              / X
                                                /|             / /|
                                  X            / X            / / X
                                 /|           / /|           / / /|
                     X          / X          / / X          / / / X
                    /|         / /|         / / /|         / / / /|
          X        / X        / / X        / / / X        / / / / X
         /|       / /|       / / /|       / / / /|       / / / / /|
 X      / X      / / X      / / / X      / / / / X      / / / / / X
 |     /  |     / /  |     / / /  |     / / / /  |     / / / / /  |
 ε    α   ε    α α   ε    α α α   ε    α α α α   ε    α α α α α   ε    ...

( for α ∊ {a, b} )

They only ever allow X to the very right, so there is no way to have X followed by a or b.

Upvotes: 3

Related Questions