Chomsky normal form conversion in Python
Transforms any context-free grammar into an equivalent grammar in Chomsky normal form.
- File
chomsky_normal_form_conversion.py, 211 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/chomsky-normal-form-conversion/. The authors are listed in prov/P1WQJZ.jsonl.
"""Conversion of a context-free grammar into Chomsky normal form.
A grammar is given by a start symbol, a list of productions (A, rhs) where rhs
is a tuple of symbols (the empty tuple is A -> ε), and the set of terminals.
Every symbol that is not a terminal is a nonterminal. The steps run in the
order START, TERM, BIN, DEL, UNIT, USELESS, which keeps the output size
O(|G|^2). All loops are iterative, so large grammars do not hit the
recursion limit.
"""
from collections import defaultdict, deque
def _fresh(base, used):
"""A new symbol name that starts with base and is not in used; it is added to used."""
name, i = base, 0
while name in used:
i += 1
name = f"{base}{i}"
used.add(name)
return name
def nullable_set(productions):
"""The nonterminals that derive ε, by a worklist with one counter per production (linear time)."""
count = []
occurs = defaultdict(list)
queue = deque()
nullable = set()
for idx, (a, rhs) in enumerate(productions):
count.append(len(rhs))
for x in rhs:
occurs[x].append(idx)
if not rhs and a not in nullable:
nullable.add(a)
queue.append(a)
while queue:
x = queue.popleft()
for idx in occurs[x]:
count[idx] -= 1
a = productions[idx][0]
if count[idx] == 0 and a not in nullable:
nullable.add(a)
queue.append(a)
return nullable
def _remove_useless(start, productions, terminals):
"""Keep the productions whose symbols all derive terminal strings and are reachable from start."""
count = []
occurs = defaultdict(list)
queue = deque()
generating = set()
for idx, (a, rhs) in enumerate(productions):
pending = {x for x in rhs if x not in terminals}
count.append(len(pending))
for x in pending:
occurs[x].append(idx)
if not pending and a not in generating:
generating.add(a)
queue.append(a)
while queue:
x = queue.popleft()
for idx in occurs[x]:
count[idx] -= 1
a = productions[idx][0]
if count[idx] == 0 and a not in generating:
generating.add(a)
queue.append(a)
kept = [(a, r) for a, r in productions
if a in generating and all(x in terminals or x in generating for x in r)]
by_lhs = defaultdict(list)
for a, r in kept:
by_lhs[a].append(r)
reach = {start}
stack = [start]
while stack:
a = stack.pop()
for r in by_lhs[a]:
for x in r:
if x not in terminals and x not in reach:
reach.add(x)
stack.append(x)
return [(a, r) for a, r in kept if a in reach]
def to_cnf(start, productions, terminals):
"""Return (new_start, productions) of a grammar in Chomsky normal form with the same language.
The output has productions A -> B C and A -> a, and new_start -> ε exactly
when ε is in the language; new_start appears on no right side.
"""
terminals = set(terminals)
used = set(terminals) | {start}
for a, rhs in productions:
if a in terminals:
raise ValueError(f"terminal {a!r} on a left side")
used.add(a)
used.update(rhs)
s0 = _fresh(start + "0", used)
prods = [(s0, (start,))] + [(a, tuple(r)) for a, r in productions] # @line L1
term_nt = {}
after_term = []
for a, rhs in prods: # @line L2
if len(rhs) >= 2:
new_rhs = []
for x in rhs:
if x in terminals:
if x not in term_nt: # @line L3
term_nt[x] = _fresh("T_" + x, used)
new_rhs.append(term_nt[x])
else:
new_rhs.append(x)
after_term.append((a, tuple(new_rhs)))
else:
after_term.append((a, rhs))
after_term += [(t, (x,)) for x, t in term_nt.items()]
binary = []
for a, rhs in after_term: # @line L4
if len(rhs) <= 2:
binary.append((a, rhs))
continue
cur = a
for i in range(len(rhs) - 2): # @line L5
nxt = _fresh(f"{a}_{i + 1}", used)
binary.append((cur, (rhs[i], nxt)))
cur = nxt
binary.append((cur, (rhs[-2], rhs[-1])))
binary = list(dict.fromkeys(binary))
nullable = nullable_set(binary) # @line L6
no_eps = []
for a, rhs in binary:
if len(rhs) == 2: # @line L7
x, y = rhs
no_eps.append((a, rhs))
if y in nullable:
no_eps.append((a, (x,)))
if x in nullable:
no_eps.append((a, (y,)))
elif rhs: # @line L8
no_eps.append((a, rhs))
if s0 in nullable:
no_eps.append((s0, ()))
no_eps = list(dict.fromkeys(no_eps))
def is_unit(rhs):
return len(rhs) == 1 and rhs[0] not in terminals
unit_succ = defaultdict(list)
non_unit = defaultdict(list)
lhs_order = list(dict.fromkeys(a for a, _ in no_eps))
for a, rhs in no_eps:
if is_unit(rhs):
unit_succ[a].append(rhs[0])
else:
non_unit[a].append(rhs)
out = []
for a in lhs_order:
reach = [a] # @line L9
seen = {a}
k = 0
while k < len(reach):
for b in unit_succ[reach[k]]:
if b not in seen:
seen.add(b)
reach.append(b)
k += 1
for b in reach: # @line L10
for rhs in non_unit[b]:
out.append((a, rhs))
out = list(dict.fromkeys(out))
result = _remove_useless(s0, out, terminals) # @line L11
return s0, result # @line L12
def is_cnf(start, productions, terminals):
"""Check the shape of Chomsky normal form, with start -> ε only and start on no right side."""
terminals = set(terminals)
for a, rhs in productions:
if a in terminals:
return False
if len(rhs) == 0:
if a != start:
return False
elif len(rhs) == 1:
if rhs[0] not in terminals:
return False
elif len(rhs) == 2:
if any(x in terminals or x == start for x in rhs):
return False
else:
return False
return True
def grammar_size(productions):
"""|G|, the sum of 1 + |rhs| over the productions."""
return sum(1 + len(rhs) for _, rhs in productions)
if __name__ == "__main__":
s0, prods = to_cnf("S", [("S", ("a", "S", "b")), ("S", ())], {"a", "b"})
for a, rhs in prods:
print(a, "->", " ".join(rhs) or "ε")
test_chomsky_normal_form_conversion.py 218 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/chomsky-normal-form-conversion/. The authors are listed in prov/P1WQJZ.jsonl.
import itertools
import random
import pytest
from chomsky_normal_form_conversion import grammar_size, is_cnf, nullable_set, to_cnf
def g(text):
"""'S -> a S b | ε ; A -> ...' into (start, productions)."""
prods, start = [], None
for part in text.split(";"):
lhs, rhs = part.split("->")
lhs = lhs.strip()
start = start or lhs
for alt in rhs.split("|"):
prods.append((lhs, tuple(x for x in alt.split() if x != "ε")))
return start, prods
def fixpoint_member(start, prods, w):
"""Oracle for any grammar: the least set of (X, i, j) with X =>* w[i:j], by naive iteration.
It handles ε-productions, unit productions and cycles, and it does not use any normal form.
"""
n = len(w)
terms = {x for _, r in prods for x in r} - {a for a, _ in prods}
derives = {(w[i], i, i + 1) for i in range(n)}
changed = True
while changed:
changed = False
for a, rhs in prods:
for i in range(n + 1):
# all end positions j reachable by matching rhs from i
ends = {i}
for x in rhs:
nxt = set()
for k in ends:
if x in terms:
if k < n and w[k] == x:
nxt.add(k + 1)
else:
for j in range(k, n + 1):
if (x, k, j) in derives:
nxt.add(j)
ends = nxt
for j in ends:
if (a, i, j) not in derives:
derives.add((a, i, j))
changed = True
return (start, 0, n) in derives
def cyk(start, prods, w):
"""Oracle for the output: the CYK algorithm, which is valid only for Chomsky normal form."""
n = len(w)
if n == 0:
return (start, ()) in set(prods)
t = [[set() for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
for a, r in prods:
if r == (w[i],):
t[i][i + 1].add(a)
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length
for k in range(i + 1, j):
for a, r in prods:
if len(r) == 2 and r[0] in t[i][k] and r[1] in t[k][j]:
t[i][j].add(a)
return start in t[0][n]
def words(alphabet, max_len):
for k in range(max_len + 1):
for tup in itertools.product(alphabet, repeat=k):
yield "".join(tup)
def random_grammar(rng, alphabet="ab"):
nts = ["S", "A", "B", "C"][: rng.randint(1, 4)]
prods = set()
for a in nts:
for _ in range(rng.randint(1, 3)):
k = rng.choice([0, 1, 1, 2, 2, 3, 4])
prods.add((a, tuple(rng.choice(nts + list(alphabet)) for _ in range(k))))
return "S", sorted(prods)
def check_equivalent(start, prods, terminals, max_len):
s0, out = to_cnf(start, prods, terminals)
assert is_cnf(s0, out, terminals)
alphabet = sorted(terminals)
count = 0
for w in words(alphabet, max_len):
expected = fixpoint_member(start, prods, w)
assert cyk(s0, out, w) == expected, (prods, w)
assert fixpoint_member(s0, out, w) == expected, (prods, w)
count += 1
return count
def test_example_a_n_b_n():
s0, out = to_cnf(*g("S -> a S b | ε"), {"a", "b"})
assert s0 == "S0"
assert set(out) == {
("S0", ()), ("S0", ("T_a", "S_1")), ("S", ("T_a", "S_1")),
("S_1", ("S", "T_b")), ("S_1", ("b",)), ("T_a", ("a",)), ("T_b", ("b",)),
}
assert grammar_size(out) == 16
def test_example_with_units_and_eps():
start, prods = g("S -> A S A | a B ; A -> B | S ; B -> b | ε")
assert grammar_size(prods) == 14
s0, out = to_cnf(start, prods, {"a", "b"})
assert len(out) == 19 and grammar_size(out) == 50
assert set(p for p in out if p[0] == "A") == {
("A", ("b",)), ("A", ("A", "S_1")), ("A", ("T_a", "B")), ("A", ("S", "A")), ("A", ("a",)),
}
assert nullable_set(prods) == {"A", "B"}
check_equivalent(start, prods, {"a", "b"}, 7)
@pytest.mark.parametrize("text, terminals", [
("S -> ε", "a"),
("S -> S", "a"),
("S -> S S | ε", "a"),
("S -> A ; A -> B ; B -> A | a", "a"),
("S -> A B ; A -> a ; B -> B b", "ab"),
("S -> S a | ε", "ab"),
("E -> E + E | E * E | ( E ) | a", "+*()a"),
("E -> E + T | T ; T -> T * F | F ; F -> ( E ) | a", "+*()a"),
("S -> a S b | S S | ε", "ab"),
("S -> a S a | b S b | a | b | ε", "ab"),
("S -> A A A A ; A -> a | ε", "a"),
])
def test_named_grammars(text, terminals):
start, prods = g(text)
max_len = 5 if len(terminals) <= 2 else 4
check_equivalent(start, prods, set(terminals), max_len)
def test_empty_language():
s0, out = to_cnf(*g("S -> A ; A -> a A"), {"a"})
assert out == []
assert not cyk(s0, out, "") and not cyk(s0, out, "a")
def test_start_on_right_side_and_eps():
s0, out = to_cnf(*g("S -> S S | a | ε"), {"a"})
assert (s0, ()) in out
assert all(s0 not in r for _, r in out)
def test_names_do_not_clash():
start, prods = g("S -> S0 T_a S_1 ; S0 -> a ; T_a -> b ; S_1 -> a S0 | ε")
s0, out = to_cnf(start, prods, {"a", "b"})
assert s0 not in {"S", "S0", "T_a", "S_1"}
check_equivalent(start, prods, {"a", "b"}, 5)
def test_terminal_on_left_side_rejected():
with pytest.raises(ValueError):
to_cnf("S", [("a", ("S",)), ("S", ("a",))], {"a"})
def test_size_family_g_k():
# S -> A1 ... Ak, Ai -> a | ε: the output stays polynomial (DEL after BIN).
sizes = []
for k in (2, 4, 6, 8, 40):
prods = [("S", tuple(f"A{i}" for i in range(1, k + 1)))]
prods += [(f"A{i}", r) for i in range(1, k + 1) for r in (("a",), ())]
s0, out = to_cnf("S", prods, {"a"})
sizes.append(grammar_size(out))
assert sizes[:4] == [10, 33, 68, 115]
assert sizes[4] < 40 * 40 * 3
def test_quadratic_unit_chain():
# A1 -> A2 -> ... -> Ak, and Ak has k binary productions: every Ai receives all k.
k = 30
prods = [("S", tuple(f"A{i}" for i in range(1, k + 1)))]
prods += [(f"A{i}", (f"A{i + 1}",)) for i in range(1, k)]
prods += [(f"A{k}", (f"B{j}", f"B{j}")) for j in range(1, k + 1)]
prods += [(f"B{j}", ("b",)) for j in range(1, k + 1)]
s0, out = to_cnf("S", prods, {"b"})
binary_of_a = [p for p in out if p[0].startswith("A") and "_" not in p[0] and len(p[1]) == 2]
assert len(binary_of_a) == k * k
assert grammar_size(out) <= 60 * grammar_size(prods) ** 2
def test_large_inputs_no_recursion():
n = 5000
prods = [("S", tuple(["a"] * n))] # one long right side
prods += [(f"U{i}", (f"U{i + 1}",)) for i in range(n)] + [(f"U{n}", ("a",))]
prods += [("S", ("U0",))]
s0, out = to_cnf("S", prods, {"a"})
assert is_cnf(s0, out, {"a"})
assert (s0, ("a",)) in out
def test_random_against_oracles():
rng = random.Random(20261106)
grammars = 0
inputs = 0
for _ in range(400):
alphabet = rng.choice(["a", "ab", "ab", "abc"])
start, prods = random_grammar(rng, alphabet)
max_len = {1: 6, 2: 5, 3: 3}[len(alphabet)]
inputs += check_equivalent(start, prods, set(alphabet), max_len)
s0, out = to_cnf(start, prods, set(alphabet))
assert grammar_size(out) <= 60 * grammar_size(prods) ** 2
grammars += 1
assert grammars == 400 and inputs >= 500
What the next level needs
- the tests did not run in this build