Sometimes loops forever, sometimes takes exponential time. Avoiding these problems: """ Regular-expression matching by the Thompson construction. E

Sometimes loops forever, sometimes takes exponential time. Avoiding these problems: """ Regular-expression matching by the Thompson construction. Explained in C at http://swtch.com/~rsc/regexp/regexp1.html """ def match(re, s): return run(prepare(re), s) def run(states, s): for c in s: states = set.union(*[state(c) for state in states]) return accepting_state in states def accepting_state(c): return set() def expecting_state(char, k): return lambda c: k(set()) if c==char else set() def state_node(state): return lambda seen: set([state]) def alt_node(k1, k2): return lambda seen: k1(seen) | k2(seen) def loop_node(k, make_k): def loop(seen): if loop in seen: return set() seen.add(loop) return k(seen) | looping(seen) looping = make_k(loop) return loop def prepare(re): return re(state_node(accepting_state))(set()) def lit(char): return lambda k: state_node(expecting_state(char, k)) def alt(re1, re2): return lambda k: alt_node(re1(k), re2(k)) def many(re): return lambda k: loop_node(k, re) def empty(k): return k def seq(re1, re2): return lambda k: re1(re2(k)) From https://github.com/darius/sketchbook https://github.com/darius/sketchbook I'm not sure how the original comes to 14 lines. btw.