Introduction: The following grammar describes even-length strings of as and bs that are not of the form ww where w is any string of as and bs. In other words, the strings cannot consist of two identical halves.

• N -> A B
• N -> B A
• A -> a
• A -> C A C
• B -> b
• B -> C B C
• C -> a
• C -> b

The idea is that if the string does not consist of two identical halves, there must be a point in the first string that has an a where the equivalent point in the second string has a b or vice-versa. The grammar states that one of these is the case.
We first note that there is empty production in the grammar, so no production can be Nullable. So we immediately set up the equations for FIRST for each non-terminal and right-hand side:

FIRST(N) = FIRST(A B)∪ FIRST(B A)

FIRST(A) = FIRST(a)∪ FIRST(C A C)

FIRST(B) = FIRST(b)∪ FIRST(C B C)

FIRST(C) = FIRST(a)∪ FIRST(b)

FIRST(A B) = FIRST(A)

FIRST(B A) = FIRST(B)

FIRST(a) = {a}

FIRST(C A C) = FIRST(C)

FIRST(b) = {b}

FIRST(C B C) = FIRST(C)

Which we solve by fixed-point iteration. We initially set the FIRST sets for the non-terminals to the empty sets; calculate the FIRST sets for right-hand sides and then non-terminals, repeating the last two steps until no changes occur:

The next iteration does not add anything, so the fixed-point is reached. We now add the production N’ -> N$ and set up the constraints for calculating FOLLOW sets:

We first use the constraint {$} ⊆ FOLLOW (N) and constraints of the form FIRST (. . . . ) ⊆ FOLLOW (. . . . . ) to get the initial sets:

FOLLOW (N) ⊆ {$}

FOLLOW (A) ⊆ {a; b}

FOLLOW (B) ⊆ {a; b}

FOLLOW (C) ⊆ {a; b}

and then use the constraints of the form FOLLOW (. .) ⊆ FOLLOW (. .). If we do this in top-down order, we get after one iteration:

FOLLOW (N) ⊆ {$}

FOLLOW (A) ⊆ {a; b; $}

FOLLOW (B) ⊆ {a; b; $}

FOLLOW (C) ⊆ {a; b; $}

Another iteration does not add anything, so the final result is

FOLLOW (N) = {$}

FOLLOW (A) = {a; b; $}

FOLLOW (B) = {a; b; $}

FOLLOW (C) = {a; b; $}

Previous Next