Epsilon-production elimination in Python
Removes ε-productions from a grammar while preserving the language minus the empty string.
- File
epsilon_production_elimination.py, 81 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/epsilon-production-elimination/. The authors are listed in prov/YT0RZM.jsonl.
"""Remove the empty productions A -> () from a context-free grammar.
A grammar is a list of productions (A, rhs), where rhs is a tuple of symbols.
The nonterminals are the left sides; every other symbol is a terminal. The
result generates the same nonempty strings as the input. With keep_empty=True
and the empty string in the language, a fresh start symbol S' with S' -> S and
S' -> () is added; S' is on no right side. A nonterminal that derives only the
empty string disappears from the result.
"""
from itertools import product
from typing import Sequence
Production = tuple[str, tuple[str, ...]]
def nullable_set(productions: Sequence[Production]) -> set[str]:
"""Nonterminals that derive the empty string, by a worklist in O(|G|) time.
count[p] is the number of symbols of the right side of production p that are
not yet known to be nullable; a left side becomes nullable when a count hits 0."""
nts = {a for a, _ in productions}
count = [len(rhs) for _, rhs in productions]
uses: dict[str, list[int]] = {}
for p, (_, rhs) in enumerate(productions):
for x in rhs:
if x in nts:
uses.setdefault(x, []).append(p)
nullable: set[str] = set()
work = [a for p, (a, rhs) in enumerate(productions) if not rhs]
for a in work:
nullable.add(a)
while work:
x = work.pop()
for p in uses.get(x, []):
count[p] -= 1 # one occurrence of x is now known nullable
a = productions[p][0]
if count[p] == 0 and a not in nullable:
nullable.add(a)
work.append(a)
return nullable
def eliminate_epsilon(
productions: Sequence[Production], start: str, keep_empty: bool = True
) -> tuple[list[Production], str]:
"""Return (new_productions, new_start) with no empty production, except
S' -> () for a fresh start S' when keep_empty is set and start is nullable."""
nullable = nullable_set(productions) # @line L1
out: dict[Production, None] = {} # @line L2
for a, rhs in productions: # @line L3
choices = [((x,), ()) if x in nullable else ((x,),) for x in rhs]
for pick in product(*choices): # @line L4
new_rhs = tuple(s for part in pick for s in part) # @line L5
if new_rhs: # @line L6
out[(a, new_rhs)] = None
nts = {a for a, _ in productions}
# A nonterminal of G left without productions (its only productions were
# empty) derives no string in the result, so a production that mentions it
# is never used in a derivation of a terminal string. Drop such productions,
# so that the symbol is not read as a terminal; dropping can leave another
# nonterminal without productions, so repeat until nothing changes.
result = list(out)
while True:
lhs = {a for a, _ in result}
kept = [(a, r) for a, r in result if all(x in lhs or x not in nts for x in r)]
if len(kept) == len(result):
break
result = kept
if keep_empty and start in nullable: # @line L7
symbols = {a for a, _ in productions} | {x for _, r in productions for x in r}
new_start = start + "'"
while new_start in symbols:
new_start += "'"
head = [(new_start, (start,))] if any(a == start for a, _ in result) else []
result = head + [(new_start, ())] + result
return result, new_start
return result, start # @line L8
test_epsilon_production_elimination.py 130 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/epsilon-production-elimination/. The authors are listed in prov/YT0RZM.jsonl.
import itertools
import random
from epsilon_production_elimination import eliminate_epsilon, nullable_set
def language(productions, start, max_len):
"""Independent oracle: every terminal string of length at most max_len that
start derives, by a least fixed point over sets of short strings."""
nts = {a for a, _ in productions}
sets = {a: set() for a in nts}
changed = True
while changed:
changed = False
for a, rhs in productions:
partial = {()}
for x in rhs:
opts = sets[x] if x in nts else {(x,)}
partial = {p + o for p in partial for o in opts if len(p) + len(o) <= max_len}
if not partial:
break
if not partial <= sets[a]:
sets[a] |= partial
changed = True
return sets.get(start, set())
def nullable_brute(productions):
nts = {a for a, _ in productions}
return {a for a in nts if () in language(productions, a, 0)}
def size(productions):
return sum(len(r) + 1 for _, r in productions)
def random_grammar(rng, max_len=3):
nts = ["S", "A", "B", "C"][: rng.randint(1, 4)]
syms = nts + ["a", "b"]
prods = set()
for a in nts:
for _ in range(rng.randint(1, 3)):
if rng.random() < 0.3:
prods.add((a, ()))
else:
prods.add((a, tuple(rng.choice(syms) for _ in range(rng.randint(1, max_len)))))
return sorted(prods)
def check(g, start):
for keep in (True, False):
g2, s2 = eliminate_epsilon(g, start, keep_empty=keep)
empties = [(a, r) for a, r in g2 if not r]
nts, lhs2 = {a for a, _ in g}, {a for a, _ in g2}
assert all(x in lhs2 or x not in nts for _, r in g2 for x in r)
lang = language(g, start, 5)
lang2 = language(g2, s2, 5)
if keep:
assert lang2 == lang
if () in lang:
assert empties == [(s2, ())] and s2 != start
assert all(s2 not in r for _, r in g2)
else:
assert not empties and s2 == start
else:
assert not empties and s2 == start
assert lang2 == lang - {()}
def test_example():
g = [
("S", ("A", "B")),
("A", ("a", "A", "A")), ("A", ()),
("B", ("b", "B", "B")), ("B", ()),
]
assert nullable_set(g) == {"S", "A", "B"}
g2, s2 = eliminate_epsilon(g, "S")
assert s2 == "S'"
assert g2 == [
("S'", ("S",)), ("S'", ()),
("S", ("A", "B")), ("S", ("A",)), ("S", ("B",)),
("A", ("a", "A", "A")), ("A", ("a", "A")), ("A", ("a",)),
("B", ("b", "B", "B")), ("B", ("b", "B")), ("B", ("b",)),
]
check(g, "S")
def test_edge_cases():
assert eliminate_epsilon([("S", ())], "S") == ([("S'", ())], "S'")
assert eliminate_epsilon([("S", ())], "S", keep_empty=False) == ([], "S")
assert eliminate_epsilon([("S", ("a",))], "S") == ([("S", ("a",))], "S")
g = [("S", ("S", "S")), ("S", ("a",)), ("S", ())]
check(g, "S")
g2, _ = eliminate_epsilon(g, "S", keep_empty=False)
assert g2 == [("S", ("S", "S")), ("S", ("S",)), ("S", ("a",))]
def test_fresh_start_name():
g = [("S", ("S'", "a")), ("S'", ()), ("S", ())]
g2, s2 = eliminate_epsilon(g, "S")
assert s2 == "S''"
check(g, "S")
def test_exponential_without_binarization():
k = 6
g = [("S", tuple(f"A{i}" for i in range(k)))] + [(f"A{i}", ()) for i in range(k)] + [
(f"A{i}", ("a",)) for i in range(k)
]
g2, _ = eliminate_epsilon(g, "S", keep_empty=False)
assert sum(1 for a, _ in g2 if a == "S") == 2 ** k - 1
def test_binarized_input_stays_linear():
rng = random.Random(7)
for _ in range(300):
g = random_grammar(rng, max_len=2)
g2, _ = eliminate_epsilon(g, "S", keep_empty=False)
assert size(g2) <= 3 * size(g)
def test_random_against_oracle():
rng = random.Random(20261106)
for _ in range(600):
g = random_grammar(rng)
assert nullable_set(g) == nullable_brute(g)
check(g, "S")
What the next level needs
- the tests did not run in this build