我设法使用pyparsing模块解决了这个问题。

import re
import pyparsing

class BoolRegEx(object):

  def Match(self, tags=[], query=""):
    self.tags = tags
    if ' ' not in query:
      return self.Search(query)
    else:
      return pyparsing.operatorPrecedence(
        pyparsing.Word(pyparsing.printables, excludeChars="()"), [
          (pyparsing.Literal("NOT"), 1, pyparsing.opAssoc.RIGHT, self.Not),
          (pyparsing.Literal("OR"),  2, pyparsing.opAssoc.LEFT,  self.Or),
          (pyparsing.Literal("AND"), 2, pyparsing.opAssoc.LEFT,  self.And),
        ]
      ).parseString(query, parseAll=True)[0]

  def Search(self, a):
    try:
      regex = re.compile(a.replace("<<", "#~").replace(">>", "~#").replace(">", ")").replace("<", "(").replace("#~", "<").replace("~#", ">"))
      for tag in self.tags:
        match = regex.match(tag)
        if match and len(match.group(0)) == len(tag):
          return True
      return False
    except:
      raise

  def And(self, t):
    for a in t[0][0::2]:
      if isinstance(a, basestring):
        v = self.Search(a)
      else:
        v = bool(a)
      if not v:
        return False
    return True

  def Or(self, t):
    for a in t[0][0::2]:
      if isinstance(a, basestring):
        v = self.Search(a)
      else:
        v = bool(a)
      if v:
        return True
    return False

  def Not(self, t):
    a = t[0][1]
    if isinstance(a, basestring):
      return not self.Search(a)
    else:
      return not bool(a)

print BoolRegEx().Match(['client/chat', 'user_a', 'limited', 'extraspecial'], "client/.+ AND user_a AND NOT ( limited AND NOT ( .+<r|i>special OR godmode ) )")
# False

print BoolRegEx().Match(['client/chat', 'user_a', 'limited', 'superspecial'], "client/.+ AND user_a AND NOT ( limited AND NOT ( .+<r|i>special OR godmode ) )")
# True

为了避免发生冲突，我必须用<>替换regexp（），但是目前所有这些似乎都是最好的解决方案。