A simple regexp impl inspired by http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html

simple_regexp.py

from string import split
import sys

# supports ^, $, |, c (literal), . (wildcard), *, +, ? 
# !supports char classes, escaped specials, grouping

def match(regexp, text):
    if '|' in regexp:
        for r in split(regexp, '|'): 
            if match(r, text): return True

    if regexp[0] == '^': 
        return matchhere(regexp[1:], text)
    for i in xrange(len(text)):
        if matchhere(regexp, text[i:]): return True

    return False

def matchhere(regexp, text):
    if len(regexp) == 0:
        return True
    if regexp[0] == '$' and len(regexp) == 1 and len(text) == 0:
        return True
    if len(regexp) > 1 :
        if regexp[1] == '*':
            return matchstar(regexp[0], regexp[2:], text)
        if  regexp[1] == '?':
            return matchhere(regexp[2:], text[1:]) or matchhere(regexp[2:], text)
        if regexp[1] == '+':
            return matchstar(regexp[0], regexp[2:], text[1:]) and regexp[0] == text[0]
    if len(text) > 0 and (regexp[0] == '.' or regexp[0] == text[0]):
        return matchhere(regexp[1:], text[1:])
    return False
        
def matchstar(st, regexp, text):
    if matchhere(regexp, text): return True

    while len(text) > 0 and (st == '.' or st == text[0]):
        text = text[1:]
        if matchhere(regexp, text): return True

    return False

def main(regexp, text):
    print "regexp: ", regexp
    print "text: ", text
    print

    if match(regexp, text): print "match found"
    else: print "no match"

if __name__ == "__main__":
    regexp, text =  sys.argv[1], sys.argv[2]
    main(regexp, text)

My favorite part of this exercise was seeing just how close C can get to Python in concision and legibility. There's hardly a difference, and in some case working with pointers in C lends the code more elegance.