#!/usr/bin/python
"""Full backtracking regexp matcher in 11 LoC.

Prompted by a remark of Dave Long.

A regular expression is either:
- a catenation of two regular expressions HT, which matches strings
  made up of two catenated parts that match H and T;
- an alternation of two regular expressions A|B, which matches
  everything either A or B matches;
- a Kleene-star of a regular expression R*, which matches the empty
  string and everything RR* matches;
- or a literal string S, which matches only itself.

This code directly implements that definition.

"""
from collections import namedtuple

class Cat(namedtuple("Cat", ("h", "t"))):
    matches = lambda self, s: any(self.h.matches(h) and self.t.matches(t)
                                  for h, t in splits(s))

class Alt(namedtuple("Alt", ("a", "b"))):
    matches = lambda self, s: self.a.matches(s) or self.b.matches(s)

class Star(namedtuple("Star", ("r"))):
    matches = lambda self, s: not s or Cat(self.r, self).matches(s)

class Lit(namedtuple("Lit", ("s"))):
    matches = lambda self, s: s == self.s

splits = lambda s: ((s[:i], s[i:]) for i in range(len(s)+1))