views:

30

answers:

1

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?

A: 

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.

Gunther