regexp.py

import string

def ltot(l):
    def _ltot(l, i):
        if len(l)==i: return ()
        return (l[i], _ltot(l, i+1))
    return _ltot(l, 0)

def symbol(x):
    def parser(txt):
        if len(txt)>0 and txt[0]==x:
            yield (x,txt[1:])
    return parser

def dot(txt):
    if len(txt)>0:
        yield (txt[0],txt[1:])

def seq(s):
    def parser(txt):
        if len(s)==0:
            yield ((), txt)
        else:
            for (obj_1, tail_1) in s[0](txt):
                for (obj_2, tail_2) in seq(s[1])(tail_1):
                    yield ((obj_1, obj_2), tail_2)
    return parser

def star(p):
    def parser(txt):
        for (obj_1, tail_1) in p(txt):
            for (obj_2, tail_2) in star(p)(tail_1):
                yield ((obj_1,obj_2), tail_2)
            yield ((obj_1,()), tail_1)
        yield ((), txt)
    return parser

def choice(s):
    def parser(txt):
        if len(s)>0:
            fail = True
            for (obj, tail) in s[0](txt):
                fail = False
                yield (obj, tail)
            if fail:
                for (obj, tail) in choice(s[1])(txt):
                    yield (obj, tail)
    return parser

def T(p, f):
    def parser(txt):
        for (obj, tail) in p(txt):
            yield (f(obj), tail)
    return parser

def parse(p, txt):
    for (obj, tail) in p(txt):
        if tail=='': return obj
    raise Exception("fails to parse " + str(txt))

d = T(symbol('.'), lambda x: dot)
l = T(choice(ltot(map(symbol, list(string.ascii_lowercase)))), symbol)
s = choice(ltot([d,l]))
a = T(seq(ltot([s, symbol('*')])), lambda obj: star(obj[0]))
p = T(seq(ltot([s, symbol('+')])), lambda obj: seq(ltot([obj[0], star(obj[0])])))
w = choice(ltot([a,p,s]))
r = T(star(w), seq)

def compile(regexp):
    p = parse(r, regexp)
    def is_match(txt):
        try:
            parse(p, txt)
            return True
        except:
            return False
    return is_match

reg = compile("qw.*r.+y")
assert reg("qwerty")
assert reg("qwrey")
assert reg("qwsdgsdfgrstegrrtrtrtrtrty")
assert not reg("qerty")