Useless Non-Terminals and Inaccessible Tokens

Discover how grammars can contain dead-end rules and unreachable symbols, learn the two conditions that make a non-terminal useless, and walk through the algorithm for cleaning them up.

Why Useless Symbols Exist

As grammars grow — especially in real programming language specifications — they often accumulate symbols that contribute nothing to the language. These may come from:

Copy-paste errors when writing grammar rules
Refactoring that removed the only rule pointing to a non-terminal
Incomplete designs where a placeholder was never given a proper production

A useless symbol is any terminal or non-terminal that can never participate in a complete derivation — that is, a derivation starting from S and ending in a string of only terminals.

Useless symbols must be removed before the grammar is used in a compiler, because they bloat the grammar and confuse parser-construction algorithms.

Two Kinds of Useless Non-Terminals

A non-terminal X is useless if it satisfies at least one of two conditions:

Condition 1 — Non-Generating (Dead End)

A non-terminal X is non-generating if there is no derivation from X that produces a string of pure terminals.

In other words: no matter which rules you apply, you can never escape the loop and produce an actual output string.

Example

Grammar:

S → aB | b

B → cB ← B only ever produces more B; it loops forever

Non-generating check for B:

B → cB → ccB → cccB → ... (never reaches a terminal-only string)

Result: B is NON-GENERATING → useless

Condition 2 — Non-Reachable (Inaccessible)

A non-terminal X is non-reachable (inaccessible) if there is no derivation from the start symbol S that ever places X in a sentential form.

In other words: the rules that use X are dead code — nothing ever leads there.

Example

Grammar:

S → aS | b

C → cd ← C never appears on the right-hand side of any rule

Reachability check from S:

S reaches: { S, a, b }

C is never reached from S.

Result: C is NON-REACHABLE → useless

Why Both Conditions Matter Independently

A symbol can be non-generating without being non-reachable, and vice versa:

Symbol	Non-Generating?	Non-Reachable?	Verdict
B (loops forever, but reachable from S)	Yes	No	Useless
C (can generate strings, but S never calls it)	No	Yes	Useless
Both conditions	Yes	Yes	Useless
Neither condition	No	No	Useful

Algorithm — Removing Useless Symbols

We must remove useless symbols in a specific order: eliminate non-generating symbols first, then eliminate non-reachable symbols. Doing it in reverse order gives wrong results.

Phase 1 — Find Generating Symbols (Bottom-Up)

Start with the empty set and repeatedly add non-terminals that can generate at least one terminal string.

Example

GENERATING = {}

Round 1: Look at all productions.

Add X to GENERATING if the RHS contains only

terminals and symbols already in GENERATING.

Repeat until GENERATING stops growing.

Any non-terminal NOT in GENERATING is non-generating and must be removed.

Phase 2 — Find Reachable Symbols (Top-Down from S)

Start with {S} and mark every symbol you can reach by following production rules.

Example

REACHABLE = { S }

For each X in REACHABLE:

For each production X → α:

Add every symbol in α to REACHABLE.

Repeat until REACHABLE stops growing.

Any non-terminal NOT in REACHABLE is inaccessible and must be removed.

Final Step

Keep only the symbols that are both generating and reachable. Remove all others (and any rules that mention them).

Worked Example — Full Cleanup

Original Grammar:

Example

G: S → AB | a

A → b

B → BC

C → c

D → d

Non-terminals: {S, A, B, C, D} Terminals: {a, b, c, d}

Phase 1 — Find Generating Symbols

Example

GENERATING = {}

Round 1: Scan all productions for RHS with only terminals.

A → b ✓ add A → GENERATING = { A }

C → c ✓ add C → GENERATING = { A, C }

D → d ✓ add D → GENERATING = { A, C, D }

S → a ✓ add S → GENERATING = { A, C, D, S }

Round 2: Scan again. S → AB: B is not in GENERATING → skip.

No new additions.

Final GENERATING = { A, C, D, S }

B is NOT in GENERATING — B is NON-GENERATING (useless).

Remove B and any rule containing B:

Remove S → AB (mentions B)
Remove B → BC (is B's own rule)

Reduced grammar after Phase 1:

Example

S → a

A → b

C → c

D → d

Phase 2 — Find Reachable Symbols

Example

REACHABLE = { S }

S → a: add 'a' (terminal) → REACHABLE = { S }

(only terminals added; no new non-terminals from S → a)

No non-terminal in REACHABLE has rules leading to A, C, or D.

Final REACHABLE = { S }

A, C, D are NOT reachable — they are INACCESSIBLE (useless).

Remove A, C, D and their rules.

Final cleaned grammar:

Example

S → a

The language is simply L(G) = {a}. All other rules were dead weight.

Summary of What Was Removed

Symbol	Reason
B	Non-generating (infinite loop B → BC)
A	Non-reachable after B was removed
C	Non-reachable after B was removed
D	Non-reachable (nothing ever leads to D)

A Note on Inaccessible Tokens

The term inaccessible token sometimes refers to a terminal symbol that never appears in any reachable production rule — not just inaccessible non-terminals.

Example

Example:

Σ = {a, b, c}

Grammar rules only use a and b.

Terminal 'c' appears in no production rule at all.

Result: 'c' is an inaccessible terminal.

In practice this happens when:

A terminal was added to the alphabet but the corresponding rule was never written
A refactor removed the only rule that used that terminal

Effect: Inaccessible terminals cannot appear in any string of L(G). They make the grammar misleading — the alphabet suggests 'c' is valid, but no rule ever produces it.

Fix: Remove the inaccessible terminal from Σ, or write a rule that uses it.

Key Takeaway

Clean grammars are smaller, easier to reason about, and faster to parse. Before feeding a grammar to a parser generator, always:

Remove non-generating non-terminals (they cause infinite loops)
Remove non-reachable symbols (they are dead code)
Check for inaccessible terminals (they misrepresent the language)

Why Useless Symbols Exist

As grammars grow — especially in real programming language specifications — they often accumulate symbols that contribute nothing to the language. These may come from:

Copy-paste errors when writing grammar rules
Refactoring that removed the only rule pointing to a non-terminal
Incomplete designs where a placeholder was never given a proper production

A useless symbol is any terminal or non-terminal that can never participate in a complete derivation — that is, a derivation starting from S and ending in a string of only terminals.

Useless symbols must be removed before the grammar is used in a compiler, because they bloat the grammar and confuse parser-construction algorithms.

Two Kinds of Useless Non-Terminals

A non-terminal X is useless if it satisfies at least one of two conditions:

Condition 1 — Non-Generating (Dead End)

A non-terminal X is non-generating if there is no derivation from X that produces a string of pure terminals.

In other words: no matter which rules you apply, you can never escape the loop and produce an actual output string.

Example

Grammar:

S → aB | b

B → cB ← B only ever produces more B; it loops forever

Non-generating check for B:

B → cB → ccB → cccB → ... (never reaches a terminal-only string)

Result: B is NON-GENERATING → useless

Condition 2 — Non-Reachable (Inaccessible)

A non-terminal X is non-reachable (inaccessible) if there is no derivation from the start symbol S that ever places X in a sentential form.

In other words: the rules that use X are dead code — nothing ever leads there.

Example

Grammar:

S → aS | b

C → cd ← C never appears on the right-hand side of any rule

Reachability check from S:

S reaches: { S, a, b }

C is never reached from S.

Result: C is NON-REACHABLE → useless

Why Both Conditions Matter Independently

A symbol can be non-generating without being non-reachable, and vice versa:

Symbol	Non-Generating?	Non-Reachable?	Verdict
B (loops forever, but reachable from S)	Yes	No	Useless
C (can generate strings, but S never calls it)	No	Yes	Useless
Both conditions	Yes	Yes	Useless
Neither condition	No	No	Useful

Algorithm — Removing Useless Symbols

We must remove useless symbols in a specific order: eliminate non-generating symbols first, then eliminate non-reachable symbols. Doing it in reverse order gives wrong results.

Phase 1 — Find Generating Symbols (Bottom-Up)

Start with the empty set and repeatedly add non-terminals that can generate at least one terminal string.

Example

GENERATING = {}

Round 1: Look at all productions.

Add X to GENERATING if the RHS contains only

terminals and symbols already in GENERATING.

Repeat until GENERATING stops growing.

Any non-terminal NOT in GENERATING is non-generating and must be removed.

Phase 2 — Find Reachable Symbols (Top-Down from S)

Start with {S} and mark every symbol you can reach by following production rules.

Example

REACHABLE = { S }

For each X in REACHABLE:

For each production X → α:

Add every symbol in α to REACHABLE.

Repeat until REACHABLE stops growing.

Any non-terminal NOT in REACHABLE is inaccessible and must be removed.

Final Step

Keep only the symbols that are both generating and reachable. Remove all others (and any rules that mention them).

Worked Example — Full Cleanup

Original Grammar:

Example

G: S → AB | a

A → b

B → BC

C → c

D → d

Non-terminals: {S, A, B, C, D} Terminals: {a, b, c, d}

Phase 1 — Find Generating Symbols

Example

GENERATING = {}

Round 1: Scan all productions for RHS with only terminals.

A → b ✓ add A → GENERATING = { A }

C → c ✓ add C → GENERATING = { A, C }

D → d ✓ add D → GENERATING = { A, C, D }

S → a ✓ add S → GENERATING = { A, C, D, S }

Round 2: Scan again. S → AB: B is not in GENERATING → skip.

No new additions.

Final GENERATING = { A, C, D, S }

B is NOT in GENERATING — B is NON-GENERATING (useless).

Remove B and any rule containing B:

Remove S → AB (mentions B)
Remove B → BC (is B's own rule)

Reduced grammar after Phase 1:

Example

S → a

A → b

C → c

D → d

Phase 2 — Find Reachable Symbols

Example

REACHABLE = { S }

S → a: add 'a' (terminal) → REACHABLE = { S }

(only terminals added; no new non-terminals from S → a)

No non-terminal in REACHABLE has rules leading to A, C, or D.

Final REACHABLE = { S }

A, C, D are NOT reachable — they are INACCESSIBLE (useless).

Remove A, C, D and their rules.

Final cleaned grammar:

Example

S → a

The language is simply L(G) = {a}. All other rules were dead weight.

Summary of What Was Removed

Symbol	Reason
B	Non-generating (infinite loop B → BC)
A	Non-reachable after B was removed
C	Non-reachable after B was removed
D	Non-reachable (nothing ever leads to D)

A Note on Inaccessible Tokens

The term inaccessible token sometimes refers to a terminal symbol that never appears in any reachable production rule — not just inaccessible non-terminals.

Example

Example:

Σ = {a, b, c}

Grammar rules only use a and b.

Terminal 'c' appears in no production rule at all.

Result: 'c' is an inaccessible terminal.

In practice this happens when:

A terminal was added to the alphabet but the corresponding rule was never written
A refactor removed the only rule that used that terminal

Effect: Inaccessible terminals cannot appear in any string of L(G). They make the grammar misleading — the alphabet suggests 'c' is valid, but no rule ever produces it.

Fix: Remove the inaccessible terminal from Σ, or write a rule that uses it.

Key Takeaway

Clean grammars are smaller, easier to reason about, and faster to parse. Before feeding a grammar to a parser generator, always:

Remove non-generating non-terminals (they cause infinite loops)
Remove non-reachable symbols (they are dead code)
Check for inaccessible terminals (they misrepresent the language)