grep in Python
Program that prints lines matching a regular expression, by simulating a nondeterministic finite automaton built from the pattern.
- File
grep.py, 128 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/grep/. The authors are listed in prov/B1JFJE.jsonl.
"""Line search with a regular expression, by NFA simulation.
A regular expression is a tuple:
("empty",) for the empty language, ("eps",) for the empty string,
("sym", a) for one symbol, ("alt", r, s), ("cat", r, s) and ("star", r).
"""
from __future__ import annotations
from collections.abc import Iterable
from typing import Any
Regex = tuple[Any, ...]
class NFA:
"""A Thompson NFA: each state has at most one symbol move and some epsilon-moves."""
def __init__(self) -> None:
self.sym: list[tuple[str, int] | None] = []
self.eps: list[list[int]] = []
self.start = 0
self.accept = 0
def new_state(self) -> int:
self.sym.append(None)
self.eps.append([])
return len(self.eps) - 1
def thompson(regex: Regex) -> NFA:
"""Build a Thompson NFA for `regex` with at most 2m states for m nodes.
The tree is walked in postorder with an explicit stack, so deep
expressions need no recursion. Cost: O(m) time and space.
"""
nfa = NFA()
frags: list[tuple[int, int]] = []
todo: list[tuple[Regex, bool]] = [(regex, False)]
while todo:
node, ready = todo.pop()
tag = node[0]
if not ready and tag in ("alt", "cat", "star"):
todo.append((node, True))
for child in reversed(node[1:]):
todo.append((child, False))
continue
s, f = nfa.new_state(), nfa.new_state()
if tag == "empty":
pass
elif tag == "eps":
nfa.eps[s].append(f)
elif tag == "sym":
nfa.sym[s] = (node[1], f)
elif tag == "alt":
s2, f2 = frags.pop()
s1, f1 = frags.pop()
nfa.eps[s] += [s1, s2]
nfa.eps[f1].append(f)
nfa.eps[f2].append(f)
elif tag == "cat":
s2, f2 = frags.pop()
s1, f1 = frags.pop()
nfa.eps[s].append(s1)
nfa.eps[f1].append(s2)
nfa.eps[f2].append(f)
elif tag == "star":
s1, f1 = frags.pop()
nfa.eps[s] += [s1, f]
nfa.eps[f1] += [s1, f]
else:
raise ValueError(f"unknown node {node!r}")
frags.append((s, f))
nfa.start, nfa.accept = frags.pop()
return nfa
def _close(nfa: NFA, states: Iterable[int]) -> set[int]:
closed = set(states)
stack = list(closed)
while stack:
q = stack.pop()
for r in nfa.eps[q]:
if r not in closed:
closed.add(r)
stack.append(r)
return closed
def line_matches(nfa: NFA, line: str) -> bool:
"""Decide whether some substring of `line` is in the language of the NFA.
Cost: O(len(line) * number of states) time, O(number of states) space.
"""
s = _close(nfa, [nfa.start]) # @line L3
matched = nfa.accept in s # @line L4
i = 0 # @line L5
while not matched and i < len(line): # @line L6
c = line[i] # @line L7
i += 1
t = [] # @line L8
for q in s:
move = nfa.sym[q]
if move is not None and move[0] == c:
t.append(move[1])
t.append(nfa.start)
s = _close(nfa, t) # @line L9
matched = nfa.accept in s # @line L10
return matched
def grep(regex: Regex, lines: Iterable[str], invert: bool = False) -> list[str]:
"""Return the lines that contain a substring in the language of `regex`.
With invert=True, return the lines that contain no such substring, as grep -v.
Precondition: `regex` is built from the tuples above.
Cost: O(m) to build the NFA, then O(m) time per character, for m nodes of
the expression; O(m) extra space.
"""
nfa = thompson(regex) # @line L1
out = []
for line in lines: # @line L2
if line_matches(nfa, line) != invert: # @line L11
out.append(line)
return out
test_grep.py 168 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/grep/. The authors are listed in prov/B1JFJE.jsonl.
import itertools
import random
from grep import NFA, grep, line_matches, thompson
EMPTY = ("empty",)
EPS = ("eps",)
def parse(text):
"""Parse | , concatenation, *, parentheses, ε and ∅ into the tuple form."""
pos = 0
def peek():
return text[pos] if pos < len(text) else None
def p_alt():
nonlocal pos
r = p_cat()
while peek() == "|":
pos += 1
r = ("alt", r, p_cat())
return r
def p_cat():
items = []
while peek() is not None and peek() not in "|)":
items.append(p_rep())
if not items:
return EPS
r = items[0]
for x in items[1:]:
r = ("cat", r, x)
return r
def p_rep():
nonlocal pos
r = p_atom()
while peek() == "*":
pos += 1
r = ("star", r)
return r
def p_atom():
nonlocal pos
c = peek()
pos += 1
if c == "(":
r = p_alt()
assert peek() == ")"
pos += 1
return r
if c == "ε":
return EPS
if c == "∅":
return EMPTY
return ("sym", c)
r = p_alt()
assert pos == len(text)
return r
def language(r, bound):
"""All strings of L(r) of length at most bound, by enumeration."""
t = r[0]
if t == "empty":
return set()
if t == "eps":
return {""}
if t == "sym":
return {r[1]} if bound >= 1 else set()
if t == "alt":
return language(r[1], bound) | language(r[2], bound)
if t == "cat":
a, b = language(r[1], bound), language(r[2], bound)
return {x + y for x in a for y in b if len(x) + len(y) <= bound}
body = language(r[1], bound) - {""}
result, frontier = {""}, {""}
while frontier:
frontier = {x + y for x in frontier for y in body if len(x) + len(y) <= bound} - result
result |= frontier
return result
def words(alphabet, bound):
for k in range(bound + 1):
for t in itertools.product(alphabet, repeat=k):
yield "".join(t)
def has_substring_in(line, lang):
n = len(line)
return any(line[i:j] in lang for i in range(n + 1) for j in range(i, n + 1))
def random_regex(rng, alphabet, depth):
if depth == 0 or rng.random() < 0.25:
x = rng.random()
if x < 0.08:
return EMPTY
if x < 0.18:
return EPS
return ("sym", rng.choice(alphabet))
k = rng.random()
if k < 0.35:
return ("alt", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
if k < 0.75:
return ("cat", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
return ("star", random_regex(rng, alphabet, depth - 1))
def test_example_from_the_page():
nfa = NFA()
for _ in range(3):
nfa.new_state()
nfa.sym[0] = ("a", 1)
nfa.eps[1] = []
nfa.start, nfa.accept = 0, 2
# On the page, state 1 has moves on b and on c. This NFA class allows one
# symbol move per state, so state 1 reaches one state for each by epsilon-moves.
b_state = nfa.new_state()
c_state = nfa.new_state()
nfa.eps[1] = [b_state, c_state]
nfa.sym[b_state] = ("b", 1)
nfa.sym[c_state] = ("c", 2)
assert line_matches(nfa, "xabbcx")
assert not line_matches(nfa, "abab")
assert line_matches(nfa, "ac")
lines = ["xabbcx", "abab", "ac"]
assert grep(parse("ab*c"), lines) == ["xabbcx", "ac"]
assert grep(parse("ab*c"), lines, invert=True) == ["abab"]
def test_no_exponential_case():
r = parse("(a|a)*b")
assert len(thompson(r).eps) == 12
assert grep(r, ["a" * 20, "a" * 5000, "a" * 20 + "b"]) == ["a" * 20 + "b"]
def test_edge_cases():
assert grep(EMPTY, ["", "a", "ab"]) == []
assert grep(EPS, ["", "a", "ab"]) == ["", "a", "ab"]
assert grep(parse("a*"), ["", "b", "c"]) == ["", "b", "c"]
assert grep(("star", EMPTY), ["", "z"]) == ["", "z"]
assert grep(parse("a"), ["", "b", "ba"]) == ["ba"]
assert grep(parse("((a*)*b)*c"), ["xc", "abab", "aabbc"]) == ["xc", "aabbc"]
assert grep(parse("ab"), []) == []
deep = ("sym", "a")
for _ in range(3000):
deep = ("cat", EPS, ("star", deep)) if _ % 2 else ("alt", EMPTY, deep)
assert grep(deep, ["", "b"]) == ["", "b"]
def test_random_against_brute_force():
rng = random.Random(20261106)
for trial in range(800):
alphabet = "ab" if trial % 2 else "abc"
bound = 6 if alphabet == "ab" else 4
r = random_regex(rng, alphabet, rng.randint(0, 5))
lang = language(r, bound)
lines = list(words(alphabet, bound))
expected = [x for x in lines if has_substring_in(x, lang)]
assert grep(r, lines) == expected
assert grep(r, lines, invert=True) == [x for x in lines if x not in set(expected)]
What the next level needs
- the tests did not run in this build