Lib/re.py

#!/usr/bin/env python
# -*- mode: python -*-
# $Id$

import string
import reop

error = 're error'

# compilation flags

IGNORECASE = I = 0x01

MULTILINE = M = 0x02
DOTALL = S = 0x04
VERBOSE = X = 0x08

#
# Initialize syntax table. This information should really come from the
# syntax table in regexpr.c rather than being duplicated here.
#

syntax_table = {}

for char in map(chr, range(0, 256)):
    syntax_table[char] = []

for char in string.lowercase:
    syntax_table[char].append('word')

for char in string.uppercase:
    syntax_table[char].append('word')

for char in string.digits:
    syntax_table[char].append('word')
    syntax_table[char].append('digit')

for char in string.whitespace:
    syntax_table[char].append('whitespace')

syntax_table['_'].append('word')

#
#
#

def match(pattern, string, flags=0):
    return compile(pattern, flags).match(string)

def search(pattern, string, flags=0):
    return compile(pattern, flags).search(string)

def sub(pattern, repl, string, count=0):
    pass

def subn(pattern, repl, string, count=0):
    pass

def split(string, pattern, maxsplit=0):
    pass

#
#
#

class RegexObject:
    def __init__(self, pattern, flags, code, num_regs, groupindex, callouts):
	self.code = code
	self.num_regs = num_regs
	self.flags = flags
	self.pattern = pattern
	self.groupindex = groupindex
	self.callouts = callouts
	self.fastmap = build_fastmap(code)
	if code[0].name == 'bol':
	    self.anchor = 1
	elif code[0].name == 'begbuf':
	    self.anchor = 2
	else:
	    self.anchor = 0
	self.buffer = assemble(code)
    def match(self, string, pos=0):
	regs = reop.match(self.buffer,
			  self.num_regs,
			  self.flags,
			  self.fastmap.can_be_null,
			  self.fastmap.fastmap(),
			  self.anchor,
			  string,
			  pos)
	if regs is None:
	    return None
	return MatchObject(self,
			   string,
			   pos,
			   regs)
    def search(self, string, pos=0):
	regs = reop.search(self.buffer,
			   self.num_regs,
			   self.flags,
			   self.fastmap.can_be_null,
			   self.fastmap.fastmap(),
			   self.anchor,
			   string,
			   pos)
	if regs is None:
	    return None
	return MatchObject(self,
			   string,
			   pos,
			   regs)
    
class MatchObject:
    def __init__(self, re, string, pos, regs):
	self.re = re
	self.string = string
	self.pos = pos
	self.regs = regs
    def start(self, i):
	if type(i) == type(''):
	    try:
		i = self.re.groupindex[i]
	    except (KeyError, TypeError):
		raise IndexError
	return self.regs[i][0]
    def end(self, i):
	if type(i) == type(''):
	    try:
		i = self.re.groupindex[i]
	    except (KeyError, TypeError):
		raise IndexError
	return self.regs[i][1]
    def span(self, i):
	if type(i) == type(''):
	    try:
		i = self.re.groupindex[i]
	    except (KeyError, TypeError):
		raise IndexError
	return self.regs[i]
    def group(i):
	if type(i) == type(''):
	    try:
		i = self.re.groupindex[i]
	    except (KeyError, TypeError):
		raise IndexError
	return self.string[self.regs[i][0]:self.regs[i][1]]

#
# A set of classes to make assembly a bit easier, if a bit verbose.
#

class Instruction:
    def __init__(self, opcode, size=1):
	self.opcode = opcode
	self.size = size
    def assemble(self, position, labels):
	return self.opcode
    def __repr__(self):
	return '%-15s' % (self.name)

class FunctionCallout(Instruction):
    name = 'function'
    def __init__(self, function):
	self.function = function
	Instruction.__init__(self, chr(22), 2 + len(self.function))
    def assemble(self, position, labels):
	return self.opcode + chr(len(self.function)) + self.function
    def __repr__(self):
	return '%-15s %-10s' % (self.name, self.function)
    
class End(Instruction):
    name = 'end'
    def __init__(self):
	Instruction.__init__(self, chr(0))

class Bol(Instruction):
    name = 'bol'
    def __init__(self):
	self.name = 'bol'
	Instruction.__init__(self, chr(1))

class Eol(Instruction):
    name = 'eol'
    def __init__(self):
	Instruction.__init__(self, chr(2))

class Set(Instruction):
    name = 'set'
    def __init__(self, set):
	self.set = set
	Instruction.__init__(self, chr(3), 33)
    def assemble_set(self, position, labels):
	result = self.opcode
	temp = 0
	for i, c in map(lambda x: (x, chr(x)), range(256)):
	    if c in self.set[2]:
		temp = temp | (1 << (i & 7))
	    if (i % 8) == 7:
		result = result + chr(temp)
		temp = 0
	return result
    def __repr__(self):
	result = '%-15s' % (self.name)
	self.set.sort()
	for char in self.set:
	    result = result + `char`
	return result
    
class Exact(Instruction):
    name = 'exact'
    def __init__(self, char):
	self.char = char
	Instruction.__init__(self, chr(4), 2)
    def assemble(self, position, labels):
	return self.opcode + self.char
    def __repr__(self):
	return '%-15s %s' % (self.name, `self.char`)
    
class AnyChar(Instruction):
    name = 'anychar'
    def __init__(self):
	Instruction.__init__(self, chr(5))
    def assemble(self, position, labels):
	return self.opcode

class MemoryInstruction(Instruction):
    def __init__(self, opcode, register):
	self.register = register
	Instruction.__init__(self, opcode, 2)
    def assemble(self, position, labels):
	return self.opcode + chr(self.register)
    def __repr__(self):
	return '%-15s %i' % (self.name, self.register)

class StartMemory(MemoryInstruction):
    name = 'start_memory'
    def __init__(self, register):
	MemoryInstruction.__init__(self, chr(6), register)

class EndMemory(MemoryInstruction):
    name = 'end_memory'
    def __init__(self, register):
	MemoryInstruction.__init__(self, chr(7), register)

class MatchMemory(MemoryInstruction):
    name = 'match_memory'
    def __init__(self, register):
	MemoryInstruction.__init__(self, chr(8), register)

class JumpInstruction(Instruction):
    def __init__(self, opcode, label):
	self.label = label
	Instruction.__init__(self, opcode, 3)
    def compute_offset(self, start, dest):
	return dest - (start + 3)
    def pack_offset(self, offset):
	if offset > 32767:
	    raise error, 'offset out of range (pos)'
	elif offset < -32768:
	    raise error, 'offset out of range (neg)'
	elif offset < 0:
	    offset = offset + 65536
	return chr(offset & 0xff) + chr((offset >> 8) & 0xff)
    def assemble(self, position, labels):
	return self.opcode + \
	       self.pack_offset(self.compute_offset(position,
						    labels[self.label]))
    def __repr__(self):
	return '%-15s %i' % (self.name, self.label)

class Jump(JumpInstruction):
    name = 'jump'
    def __init__(self, label):
	JumpInstruction.__init__(self, chr(9), label)

class StarJump(JumpInstruction):
    name = 'star_jump'
    def __init__(self, label):
	JumpInstruction.__init__(self, chr(10), label)

class FailureJump(JumpInstruction):
    name = 'failure_jump'
    def __init__(self, label):
	JumpInstruction.__init__(self, chr(11), label)

class UpdateFailureJump(JumpInstruction):
    name = 'update_failure_jump'
    def __init__(self, label):
	JumpInstruction.__init__(self, chr(12), label)

class DummyFailureJump(JumpInstruction):
    name = 'update_failure_jump'
    def __init__(self, label):
	JumpInstruction.__init__(self, chr(13), label)
	
class BegBuf(Instruction):
    name = 'begbuf'
    def __init__(self):
	Instruction.__init__(self, chr(14))

class EndBuf(Instruction):
    name = 'endbuf'
    def __init__(self):
	Instruction.__init__(self, chr(15))

class WordBeg(Instruction):
    name = 'wordbeg'
    def __init__(self):
	Instruction.__init__(self, chr(16))

class WordEnd(Instruction):
    name = 'wordend'
    def __init__(self):
	Instruction.__init__(self, chr(17))

class WordBound(Instruction):
    name = 'wordbound'
    def __init__(self):
	Instruction.__init__(self, chr(18))

class NotWordBound(Instruction):
    name = 'notwordbound'
    def __init__(self):
	Instruction.__init__(self, chr(18))

class SyntaxSpec(Instruction):
    name = 'syntaxspec'
    def __init__(self, syntax):
	self.syntax = syntax
	Instruction.__init__(self, chr(20), 2)
    def assemble(self, postition, labels):
	return self.opcode + chr(self.syntax)

class SyntaxSpec(Instruction):
    name = 'notsyntaxspec'
    def __init__(self, syntax):
	self.syntax = syntax
	Instruction.__init__(self, chr(21), 2)
    def assemble(self, postition, labels):
	return self.opcode + chr(self.syntax)

class Label(Instruction):
    name = 'label'
    def __init__(self, label):
	self.label = label
	Instruction.__init__(self, '', 0)
    def __repr__(self):
	return '%-15s %i' % (self.name, self.label)

class OpenParen(Instruction):
    name = '('
    def __init__(self, register):
	self.register = register
	Instruction.__init__(self, '', 0)

class Alternation(Instruction):
    name = '|'
    def __init__(self):
	Instruction.__init__(self, '', 0)

#
#
#

def assemble(instructions):
    labels = {}
    position = 0
    pass1 = []
    for instruction in instructions:
	if instruction.name == 'label':
	    labels[instruction.label] = position
	else:
	    pass1.append((position, instruction))
	    position = position + instruction.size
    pass2 = ''
    for position, instruction in pass1:
	pass2 = pass2 + instruction.assemble(position, labels)
    return pass2

#
#
#

def escape(pattern):
    result = ''
    for char in pattern:
	if 'word' not in syntax_table[char]:
	    result = result + '\\' + char
	else:
	    result = result + char
    return result

#
#
#

def registers_used(instructions):
    result = []
    for instruction in instructions:
	if (instruction.name in ['set_memory', 'end_memory']) and \
	   (instruction.register not in result):
	    result.append(instruction.register)
    return result

#
#
#

class Fastmap:
    def __init__(self):
	self.map = ['\000']*256
	self.can_be_null = 0
    def add(self, char):
	self.map[ord(char)] = '\001'
    def fastmap(self):
	return string.join(self.map, '')
    def __getitem__(self, char):
	return ord(self.map[ord(char)])
    def __repr__(self):
	self.map.sort()
	return 'Fastmap(' + `self.can_be_null` + ', ' + `self.map` + ')'

#
#
#

def find_label(code, label):
    line = 0
    for instruction in code:
	if (instruction.name == 'label') and (instruction.label == label):
	    return line + 1
	line = line + 1
	
def build_fastmap_aux(code, pos, visited, fastmap):
    if visited[pos]:
	return
    while 1:
	instruction = code[pos]
	visited[pos] = 1
	pos = pos + 1
	if instruction.name == 'end':
	    fastmap.can_be_null = 1
	    return
	elif instruction.name == 'syntaxspec':
	    for char in map(chr, range(256)):
		if instruction.syntax in syntax_table[char]:
		    fastmap.add(char)
	    return
	elif instruction.name == 'notsyntaxspec':
	    for char in map(chr, range(256)):
		if instruction.syntax not in syntax_table[char]:
		    fastmap.add(char)
	    return
	elif instruction.name == 'eol':
	    fastmap.add('\n')
	    if fastmap.can_be_null == 0:
		fastmap.can_be_null = 2
	    return
	elif instruction.name == 'set':
	    for char in instruction.set:
		fastmap.add(char)
	    return
	elif instruction.name == 'exact':
	    fastmap.add(instruction.char)
	elif instruction.name == 'anychar':
	    for char in map(chr, range(256)):
		if char != '\n':
		    fastmap.add(char)
	    return
	elif instruction.name == 'match_memory':
	    for char in map(chr, range(256)):
		fastmap.add(char)
	    fastmap.can_be_null = 1
	    return
	elif instruction.name in ['jump', 'dummy_failure_jump', \
				  'update_failure_jump', 'star_jump']:
	    pos = find_label(code, instruction.label)
	    if visited[pos]:
		return
	    visited[pos] = 1
	elif instruction.name  == 'failure_jump':
	    build_fastmap_aux(code,
			      find_label(code, instruction.label),
			      visited,
			      fastmap)
	elif instruction.name == 'function':
	    for char in map(chr, range(256)):
		fastmap.add(char)
	    fastmap.can_be_null = 1
	    return
	
def build_fastmap(code, pos=0):
    visited = [0] * len(code)
    fastmap = Fastmap()
    build_fastmap_aux(code, pos, visited, fastmap)
    return fastmap

#
#
#

def compile(pattern, flags=0):
    stack = []
    index = 0
    label = 0
    register = 1
    groupindex = {}
    callouts = []
    while (index < len(pattern)):
	char = pattern[index]
	index = index + 1
	if char == '\\':
	    if index < len(pattern):
		next = pattern[index]
		index = index + 1
		if next == 't':
		    stack.append([Exact(chr(9))])

		elif next == 'n':
		    stack.append([Exact(chr(10))])

		elif next == 'r':
		    stack.append([Exact(chr(13))])

		elif next == 'f':
		    stack.append([Exact(chr(12))])

		elif next == 'a':
		    stack.append([Exact(chr(7))])

		elif next == 'e':
		    stack.append([Exact(chr(27))])

		elif next in '0123456789':
		    value = next
		    while (index < len(pattern)) and \
			  (pattern[index] in string.digits):
			value = value + pattern[index]
			index = index + 1
		    if (len(value) == 3) or \
		       ((len(value) == 2) and (value[0] == '0')):
			value = string.atoi(value, 8)
			if value > 255:
			    raise error, 'octal char out of range'
			stack.append([Exact(chr(value))])
		    elif value == '0':
			stack.append([Exact(chr(0))])
		    elif len(value) > 3:
			raise error, 'too many digits'
		    else:
			value = string.atoi(value)
			if value >= register:
			    raise error, ('cannot reference a register '
					  'not yet used')
			elif value == 0:
			    raise error, ('register 0 cannot be used '
					  'during match')
			stack.append([MatchMemory(value)])

		elif next == 'x':
		    value = ''
		    while (index < len(pattern)) and \
			  (pattern[index] in string.hexdigits):
			value = value + pattern[index]
			index = index + 1
		    value = string.atoi(value, 16)
		    if value > 255:
			raise error, 'hex char out of range'
		    stack.append([Exact(chr(value))])

		elif next == 'c':
		    if index >= len(pattern):
			raise error, '\\c at end of re'
		    elif pattern[index] in 'abcdefghijklmnopqrstuvwxyz':
			stack.append(Exact(chr(ord(pattern[index]) -
					       ord('a') + 1)))
		    else:
			stack.append(Exact(chr(ord(pattern[index]) ^ 64)))
		    index = index + 1
		    
		elif next == 'A':
		    stack.append([BegBuf()])

		elif next == 'Z':
		    stack.append([EndBuf()])

		elif next == 'b':
		    stack.append([WordBound()])

		elif next == 'B':
		    stack.append([NotWordBound()])

		elif next == 'w':
		    stack.append([SyntaxSpec('word')])

		elif next == 'W':
		    stack.append([NotSyntaxSpec('word')])

		elif next == 's':
		    stack.append([SyntaxSpec('whitespace')])

		elif next == 'S':
		    stack.append([NotSyntaxSpec('whitespace')])

		elif next == 'd':
		    stack.append([SyntaxSpec('digit')])

		elif next == 'D':
		    stack.append([NotSyntaxSpec('digit')])

		elif next in 'GluLUQE':
		    # some perl-isms that we don't support
		    raise error, '\\' + next + ' not supported'
		
		else:
		    stack.append([Exact(pattern[index])])

	    else:
		raise error, 'backslash at the end of a string'

	elif char == '|':
	    if len(stack) == 0:
		raise error, 'nothing to alternate'
	    expr = []
	    while (len(stack) != 0) and \
		  (stack[-1][0].name != '(') and \
		  (stack[-1][0].name != '|'):
		expr = stack[-1] + expr
		del stack[-1]
	    stack.append([FailureJump(label)] + \
			 expr + \
			 [Jump(-1),
			  Label(label)])
	    stack.append([('|',)])
	    label = label + 1

	elif char == '(':
	    if index >= len(pattern):
		raise error, 'no matching close paren'

	    elif pattern[index] == '?':
		# Perl style (?...) extensions
		index = index + 1
		if index >= len(pattern):
		    raise error, 'extension ends prematurely'

		elif pattern[index] == 'P':
		    # Python extensions
		    index = index + 1
		    if index >= len(pattern):
			raise error, 'extension ends prematurely'

		    elif pattern[index] == '<':
			# Handle Python symbolic group names (?<...>...)
			index = index + 1
			end = string.find(pattern, '>', index)
			if end == -1:
			    raise error, 'no end to symbolic group name'
			name = pattern[index:end]
			# XXX check syntax of name
			index = end + 1
			groupindex[name] = register
			stack.append([OpenParen(register)])
			register = register + 1

		    elif pattern[index] == '=':
			# backreference to symbolic group name
			if index >= len(pattern):
			    raise error, '(?P= at the end of the pattern'
			start = index + 1
			end = string.find(pattern, ')', start)
			if end == -1:
			    raise error, 'no ) to end symbolic group name'
			name = pattern[start:end]
			if name not in groupindex:
			    raise error, ('symbolic group name ' + name + \
					  ' has not been used yet')
			stack.append([MatchMemory(groupindex[name])])
			index = end + 1
			
		    elif pattern[index] == '!':
			# function callout
			if index >= len(pattern):
			    raise error, 'no function callout name'
			start = index + 1
			end = string.find(pattern, ')', start)
			if end == -1:
			    raise error, 'no ) to end function callout name'
			name = pattern[start:end]
			if name not in callouts:
			    raise error, ('function callout name not listed '
					  'in callouts dict')
			stack.append([FunctionCallout(name)])

		    else:
			raise error, 'unknown Python extension'
		    
		elif pattern[index] == ':':
		    # grouping, but no registers
		    index = index + 1
		    stack.append([('(', -1)])

		elif pattern[index] == '#':
		    # comment
		    index = index + 1
		    end = string.find(pattern, ')', index)
		    if end == -1:
			raise error, 'no end to comment'
		    index = end + 1

		elif pattern[index] == '=':
		    raise error, ('zero-width positive lookahead '
				  'assertion is unsupported')

		elif pattern[index] == '!':
		    raise error, ('zero-width negative lookahead '
				  'assertion is unsupported')

		elif pattern[index] in 'iImMsSxX':
		    while (index < len(pattern)) and (pattern[index] != ')'):
			if pattern[index] == 'iI':
			    flags = flags | IGNORECASE
			elif pattern[index] == 'mM':
			    flags = flags | MULTILINE
			elif pattern[index] == 'sS':
			    flags = flags | DOTALL
			elif pattern[index] in 'xX':
			    flags = flags | VERBOSE
			else:
			    raise error, 'unknown flag'
			index = index + 1
		    index = index + 1
		    
		else:
		    raise error, 'unknown extension'

	    else:
		stack.append([OpenParen(register)])
		register = register + 1

	elif char == ')':
	    # make one expression out of everything on the stack up to
	    # the marker left by the last parenthesis
	    expr = []
	    while (len(stack) > 0) and (stack[-1][0].name != '('):
		expr = stack[-1] + expr
		del stack[-1]

	    if len(stack) == 0:
		raise error, 'too many close parens'
	    if len(expr) == 0:
		raise error, 'nothing inside parens'

	    # check to see if alternation used correctly
	    if (expr[-1].name == '|'):
		raise error, 'alternation with nothing on the right'

	    # remove markers left by alternation
	    expr = filter(lambda x: x.name != '|', expr)

	    # clean up jumps inserted by alternation
	    need_label = 0
	    for i in range(len(expr)):
		if (expr[i].name == 'jump') and (expr[i].label == -1):
		    expr[i] = JumpOpcode(label)
		    need_label = 1
	    if need_label:
		expr.append(Label(label))
		label = label + 1

	    if stack[-1][0][1] > 0:
		expr = [StartMemory(stack[-1][0].register)] + \
		       expr + \
		       [EndMemory(stack[-1][0].register)]
	    del stack[-1]
	    stack.append(expr)

	elif char == '{':
	    if len(stack) == 0:
		raise error, 'no expression to repeat'
	    end = string.find(pattern, '}', index)
	    if end == -1:
		raise error, ('no close curly bracket to match'
			      ' open curly bracket')

	    fields = map(string.strip,
			 string.split(pattern[index:end], ','))
	    index = end + 1

	    minimal = 0
	    if (index < len(pattern)) and (pattern[index] == '?'):
		minimal = 1
		index = index + 1

	    if len(fields) == 1:
		# {n} or {n}? (there's really no difference)
		try:
		    count = string.atoi(fields[0])
		except ValueError:
		    raise error, ('count must be an integer '
				  'inside curly braces')
		if count > 65535:
		    raise error, 'repeat count out of range'
		expr = []
		while count > 0:
		    expr = expr + stack[-1]
		    count = count - 1
		del stack[-1]
		stack.append(expr)

	    elif len(fields) == 2:
		# {n,} or {n,m}
		if fields[1] == '':
		    # {n,}
		    try:
			min = string.atoi(fields[0])
		    except ValueError:
			raise error, ('minimum must be an integer '
				      'inside curly braces')
		    if min > 65535:
			raise error, 'minimum repeat count out of range'

		    expr = []
		    while min > 0:
			expr = expr + stack[-1]
			min = min - 1
		    registers = registers_used(stack[-1])
		    if minimal:
			expr = expr + \
			       ([Jump(label + 1),
				 Label(label)] + \
				stack[-1] + \
				[Label(label + 1),
				 FailureJump(label, registers)])
		    else:
			expr = expr + \
			       ([Label(label),
				 FailureJump(label + 1, registers)] +
				stack[-1] +
				[StarJump(label),
				 Label(label + 1)])

		    del stack[-1]
		    stack.append(expr)
		    label = label + 2

		else:
		    # {n,m}
		    try:
			min = string.atoi(fields[0])
		    except ValueError:
			raise error, ('minimum must be an integer '
				      'inside curly braces')
		    try:
			max = string.atoi(fields[1])
		    except ValueError:
			raise error, ('maximum must be an integer '
				      'inside curly braces')
		    if min > 65535:
			raise error, ('minumim repeat count out '
				      'of range')
		    if max > 65535:
			raise error, ('maximum repeat count out '
				      'of range')
		    if min > max:
			raise error, ('minimum repeat count must be '
				      'less than the maximum '
				      'repeat count')
		    expr = []
		    while min > 0:
			expr = expr + stack[-1]
			min = min - 1
			max = max - 1
		    if minimal:
			while max > 0:
			    expr = expr + \
				   [FailureJump(label),
				    Jump(label + 1),
				    Label(label)] + \
				   stack[-1] + \
				   [Label(label + 1)]
			    label = label + 2
			del stack[-1]
			stack.append(expr)
		    else:
			while max > 0:
			    expr = expr + \
				   [FailureJump(label)] + \
				   stack[-1]
			    max = max - 1
			del stack[-1]
			stack.append(expr + [Label(label)])
			label = label + 1

	    else:
		raise error, ('there need to be one or two fields '
			      'in a {} expression')
	    index = end + 1

	elif char == '}':
	    raise error, 'unbalanced close curly brace'

	elif char == '*':
	    # Kleene closure
	    if len(stack) == 0:
		raise error, 'the Kleene closure needs something to repeat'
	    registers = registers_used(stack[-1])
	    if (index < len(pattern)) and (pattern[index] == '?'):
		# non-greedy matching
		expr = [JumpInstructions(label + 1),
			Label(label)] + \
		       stack[-1] + \
		       [Label(label + 1),
			FailureJump(label)]
		index = index + 1
	    else:
		# greedy matching
		expr = [Label(label),
			FailureJump(label + 1)] + \
		       stack[-1] + \
		       [StarJump(label),
			Label(label + 1)]
	    del stack[-1]
	    stack.append(expr)
	    label = label + 2

	elif char == '+':
	    # positive closure
	    if len(stack) == 0:
		raise error, 'the positive closure needs something to repeat'
	    registers = registers_used(stack[-1])
	    if (index < len(pattern)) and (pattern[index] == '?'):
		# non-greedy
		expr = [Label(label)] + \
		       stack[-1] + \
		       [FailureJump(label)]
		label = label + 1
		index = index + 1
	    else:
		# greedy
		expr = [DummyFailureJump(label + 1),
			Label(label),
			FailureJump(label + 2),
			Label(label + 1)] + \
		       stack[-1] + \
		       [StarJump(label),
			Label(label + 2)]
		label = label + 3
	    del stack[-1]
	    stack.append(expr)

	elif char == '?':
	    if len(stack) == 0:
		raise error, 'need something to be optional'
	    registers = registers_used(stack[-1])
	    if (index < len(pattern)) and (pattern[index] == '?'):
		# non-greedy matching
		expr = [FailureJump(label),
			Jump(label + 1),
			Label(label)] + \
		       stack[-1] + \
		       [Label(label + 1)]
		label = label + 2
		index = index + 1
	    else:
		# greedy matching
		expr = [FailureJump(label)] + \
		       stack[-1] + \
		       [Label(label)]
		label = label + 1
	    del stack[-1]
	    stack.append(expr)

	elif char == '.':
	    if flags & DOTALL:
		stack.append(Set(map(chr, range(256))))
	    else:
		stack.append([AnyChar()])

	elif char == '^':
	    if flags & MULTILINE:
		stack.append([Bol()])
	    else:
		stack.append([BegBuf()])

	elif char == '$':
	    if flags & MULTILINE:
		stack.append([Eol()])
	    else:
		stack.append([EndBuf()])

	elif char == '#':
	    if flags & VERBOSE:
		# comment
		index = index + 1
		end = string.find(pattern, '\n', index)
		if end == -1:
		    index = len(pattern)
		else:
		    index = end + 1
	    else:
		stack.append([Exact(char)])

	elif char in string.whitespace:
	    if flags & VERBOSE:
		stack.append([Exact(char)])

	elif char == '[':
	    if index >= len(pattern):
		raise error, 'incomplete set'
	    negate = 0
	    last = ''
	    set = []
	    if pattern[index] == '^':
		negate = 1
		index = index + 1
	    if index >= len(pattern):
		raise error, 'incomplete set'
	    if pattern[index] in ']-':
		set.append(pattern[index])
		last = pattern[index]
		index = index + 1
	    while (index < len(pattern)) and (pattern[index] != ']'):
		next = pattern[index]
		index = index + 1
		if next == '-':
		    if (index >= len(pattern)) or (pattern[index] == ']'):
			raise error, 'incomplete range in set'
		    if last > pattern[index]:
			raise error, 'range arguments out of order in set'
		    for next in map(chr, \
				    range(ord(last), \
					  ord(pattern[index]) + 1)):
			if next not in set:
			    set.append(next)
		    last = ''
		    index = index + 1

		elif next == '\\':
		    # expand syntax meta-characters and add to set
		    if index >= len(pattern):
			raise error, 'incomplete set'
		    elif (pattern[index] == ']'):
			raise error, 'backslash at the end of a set'
		    elif pattern[index] == 'w':
			for next in syntax_table.keys():
			    if 'word' in syntax_table[next]:
				set.append(next)
		    elif pattern[index] == 'W':
			for next in syntax_table.keys():
			    if 'word' not in syntax_table[next]:
				set.append(next)
		    elif pattern[index] == 'd':
			for next in syntax_table.keys():
			    if 'digit' in syntax_table[next]:
				set.append(next)
		    elif pattern[index] == 'D':
			for next in syntax_table.keys():
			    if 'digit' not in syntax_table[next]:
				set.append(next)
		    elif pattern[index] == 's':
			for next in syntax_table.keys():
			    if 'whitespace' in syntax_table[next]:
				set.append(next)
		    elif pattern[index] == 'S':
			for next in syntax_table.keys():
			    if 'whitespace' not in syntax_table[next]:
				set.append(next)
		    else:
			raise error, 'unknown meta in set'
		    last = ''
		    index = index + 1

		else:
		    if next not in set:
			set.append(next)
		    last = next

	    if pattern[index] != ']':
		raise error, 'incomplete set'

	    index = index + 1

	    if negate:
		notset = []
		for char in map(chr, range(256)):
		    if char not in set:
			notset.append(char)
		stack.append([Set(notset)])
	    else:
		stack.append([Set(set)])

	else:
	    stack.append([Exact(char)])

    code = []
    while len(stack) > 0:
	if stack[-1][0].name == '(':
	    raise error, 'too many open parens'
	code = stack[-1] + code
	del stack[-1]
    if len(code) == 0:
	raise error, 'no code generated'
    if (code[-1].name == '|'):
	raise error, 'alternation with nothing on the right'
    code = filter(lambda x: x.name != '|', code)
    need_label = 0
    for i in range(len(code)):
	if (code[i].name == 'jump') and (code[i].label == -1):
	    code[i] = Jump(label)
	    need_label = 1
    if need_label:
	code.append(Label(label))
	label = label + 1
    code.append(End())
    return RegexObject(pattern, flags, code, register, groupindex, callouts)

if __name__ == '__main__':
    print compile('a(b)*')
    print compile('a{3}')
    print compile('(a){2}')
    print compile('a{2,4}')
    print compile('a|b')
    print compile('a(b|c)')
    print compile('a*')
    print compile('a+')
    print compile('a|b|c')
    print compile('a(b|c)*')
    print compile('\\n')
    print compile('a(?# huh huh)b')
    print compile('[a-c\\w]')
    print compile('[[]')
    print compile('[]]')
    print compile('(<hello>a)')
    print compile('\Q*\e')
    print compile('a{0,}')