home *** CD-ROM | disk | FTP | other *** search
/ PC World 2001 April / PCWorld_2001-04_cd.bin / Software / TemaCD / webclean / !!!python!!! / BeOpen-Python-2.0.exe / SRE_PARSE.PY < prev    next >
Encoding:
Python Source  |  2000-10-07  |  22.7 KB  |  683 lines
  1. #
  2. # Secret Labs' Regular Expression Engine
  3. #
  4. # convert re-style regular expression to sre pattern
  5. #
  6. # Copyright (c) 1998-2000 by Secret Labs AB.  All rights reserved.
  7. #
  8. # See the sre.py file for information on usage and redistribution.
  9. #
  10.  
  11. import string, sys
  12.  
  13. from sre_constants import *
  14.  
  15. SPECIAL_CHARS = ".\\[{()*+?^$|"
  16. REPEAT_CHARS = "*+?{"
  17.  
  18. DIGITS = tuple("0123456789")
  19.  
  20. OCTDIGITS = tuple("01234567")
  21. HEXDIGITS = tuple("0123456789abcdefABCDEF")
  22.  
  23. WHITESPACE = tuple(" \t\n\r\v\f")
  24.  
  25. ESCAPES = {
  26.     r"\a": (LITERAL, 7),
  27.     r"\b": (LITERAL, 8),
  28.     r"\f": (LITERAL, 12),
  29.     r"\n": (LITERAL, 10),
  30.     r"\r": (LITERAL, 13),
  31.     r"\t": (LITERAL, 9),
  32.     r"\v": (LITERAL, 11),
  33.     r"\\": (LITERAL, ord("\\"))
  34. }
  35.  
  36. CATEGORIES = {
  37.     r"\A": (AT, AT_BEGINNING), # start of string
  38.     r"\b": (AT, AT_BOUNDARY),
  39.     r"\B": (AT, AT_NON_BOUNDARY),
  40.     r"\d": (IN, [(CATEGORY, CATEGORY_DIGIT)]),
  41.     r"\D": (IN, [(CATEGORY, CATEGORY_NOT_DIGIT)]),
  42.     r"\s": (IN, [(CATEGORY, CATEGORY_SPACE)]),
  43.     r"\S": (IN, [(CATEGORY, CATEGORY_NOT_SPACE)]),
  44.     r"\w": (IN, [(CATEGORY, CATEGORY_WORD)]),
  45.     r"\W": (IN, [(CATEGORY, CATEGORY_NOT_WORD)]),
  46.     r"\Z": (AT, AT_END), # end of string
  47. }
  48.  
  49. FLAGS = {
  50.     # standard flags
  51.     "i": SRE_FLAG_IGNORECASE,
  52.     "L": SRE_FLAG_LOCALE,
  53.     "m": SRE_FLAG_MULTILINE,
  54.     "s": SRE_FLAG_DOTALL,
  55.     "x": SRE_FLAG_VERBOSE,
  56.     # extensions
  57.     "t": SRE_FLAG_TEMPLATE,
  58.     "u": SRE_FLAG_UNICODE,
  59. }
  60.  
  61. class Pattern:
  62.     # master pattern object.  keeps track of global attributes
  63.     def __init__(self):
  64.         self.flags = 0
  65.         self.groups = 1
  66.         self.groupdict = {}
  67.     def getgroup(self, name=None):
  68.         gid = self.groups
  69.         self.groups = gid + 1
  70.         if name:
  71.             self.groupdict[name] = gid
  72.         return gid
  73.  
  74. class SubPattern:
  75.     # a subpattern, in intermediate form
  76.     def __init__(self, pattern, data=None):
  77.         self.pattern = pattern
  78.         if not data:
  79.             data = []
  80.         self.data = data
  81.         self.width = None
  82.     def dump(self, level=0):
  83.         nl = 1
  84.         for op, av in self.data:
  85.             print level*"  " + op,; nl = 0
  86.             if op == "in":
  87.                 # member sublanguage
  88.                 print; nl = 1
  89.                 for op, a in av:
  90.                     print (level+1)*"  " + op, a
  91.             elif op == "branch":
  92.                 print; nl = 1
  93.                 i = 0
  94.                 for a in av[1]:
  95.                     if i > 0:
  96.                         print level*"  " + "or"
  97.                     a.dump(level+1); nl = 1
  98.                     i = i + 1
  99.             elif type(av) in (type(()), type([])):
  100.                 for a in av:
  101.                     if isinstance(a, SubPattern):
  102.                         if not nl: print
  103.                         a.dump(level+1); nl = 1
  104.                     else:
  105.                         print a, ; nl = 0
  106.             else:
  107.                 print av, ; nl = 0
  108.             if not nl: print
  109.     def __repr__(self):
  110.         return repr(self.data)
  111.     def __len__(self):
  112.         return len(self.data)
  113.     def __delitem__(self, index):
  114.         del self.data[index]
  115.     def __getitem__(self, index):
  116.         return self.data[index]
  117.     def __setitem__(self, index, code):
  118.         self.data[index] = code
  119.     def __getslice__(self, start, stop):
  120.         return SubPattern(self.pattern, self.data[start:stop])
  121.     def insert(self, index, code):
  122.         self.data.insert(index, code)
  123.     def append(self, code):
  124.         self.data.append(code)
  125.     def getwidth(self):
  126.         # determine the width (min, max) for this subpattern
  127.         if self.width:
  128.             return self.width
  129.         lo = hi = 0L
  130.         for op, av in self.data:
  131.             if op is BRANCH:
  132.                 i = sys.maxint
  133.                 j = 0
  134.                 for av in av[1]:
  135.                     l, h = av.getwidth()
  136.                     i = min(i, l)
  137.                     j = max(j, h)
  138.                 lo = lo + i
  139.                 hi = hi + j
  140.             elif op is CALL:
  141.                 i, j = av.getwidth()
  142.                 lo = lo + i
  143.                 hi = hi + j
  144.             elif op is SUBPATTERN:
  145.                 i, j = av[1].getwidth()
  146.                 lo = lo + i
  147.                 hi = hi + j
  148.             elif op in (MIN_REPEAT, MAX_REPEAT):
  149.                 i, j = av[2].getwidth()
  150.                 lo = lo + long(i) * av[0]
  151.                 hi = hi + long(j) * av[1]
  152.             elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY):
  153.                 lo = lo + 1
  154.                 hi = hi + 1
  155.             elif op == SUCCESS:
  156.                 break
  157.         self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))
  158.         return self.width
  159.  
  160. class Tokenizer:
  161.     def __init__(self, string):
  162.         self.string = string
  163.         self.index = 0
  164.         self.__next()
  165.     def __next(self):
  166.         if self.index >= len(self.string):
  167.             self.next = None
  168.             return
  169.         char = self.string[self.index]
  170.         if char[0] == "\\":
  171.             try:
  172.                 c = self.string[self.index + 1]
  173.             except IndexError:
  174.                 raise error, "bogus escape"
  175.             char = char + c
  176.         self.index = self.index + len(char)
  177.         self.next = char
  178.     def match(self, char, skip=1):
  179.         if char == self.next:
  180.             if skip:
  181.                 self.__next()
  182.             return 1
  183.         return 0
  184.     def get(self):
  185.         this = self.next
  186.         self.__next()
  187.         return this
  188.     def tell(self):
  189.         return self.index, self.next
  190.     def seek(self, index):
  191.         self.index, self.next = index
  192.  
  193. def isident(char):
  194.     return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"
  195.  
  196. def isdigit(char):
  197.     return "0" <= char <= "9"
  198.  
  199. def isname(name):
  200.     # check that group name is a valid string
  201.     if not isident(name[0]):
  202.         return 0
  203.     for char in name:
  204.         if not isident(char) and not isdigit(char):
  205.             return 0
  206.     return 1
  207.  
  208. def _group(escape, groups):
  209.     # check if the escape string represents a valid group
  210.     try:
  211.         gid = int(escape[1:])
  212.         if gid and gid < groups:
  213.             return gid
  214.     except ValueError:
  215.         pass
  216.     return None # not a valid group
  217.  
  218. def _class_escape(source, escape):
  219.     # handle escape code inside character class
  220.     code = ESCAPES.get(escape)
  221.     if code:
  222.         return code
  223.     code = CATEGORIES.get(escape)
  224.     if code:
  225.         return code
  226.     try:
  227.         if escape[1:2] == "x":
  228.             # hexadecimal escape (exactly two digits)
  229.             while source.next in HEXDIGITS and len(escape) < 4:
  230.                 escape = escape + source.get()
  231.             escape = escape[2:]
  232.             if len(escape) != 2:
  233.                 raise error, "bogus escape: %s" % repr("\\" + escape)
  234.             return LITERAL, int(escape, 16) & 0xff
  235.         elif str(escape[1:2]) in OCTDIGITS:
  236.             # octal escape (up to three digits)
  237.             while source.next in OCTDIGITS and len(escape) < 5:
  238.                 escape = escape + source.get()
  239.             escape = escape[1:]
  240.             return LITERAL, int(escape, 8) & 0xff
  241.         if len(escape) == 2:
  242.             return LITERAL, ord(escape[1])
  243.     except ValueError:
  244.         pass
  245.     raise error, "bogus escape: %s" % repr(escape)
  246.  
  247. def _escape(source, escape, state):
  248.     # handle escape code in expression
  249.     code = CATEGORIES.get(escape)
  250.     if code:
  251.         return code
  252.     code = ESCAPES.get(escape)
  253.     if code:
  254.         return code
  255.     try:
  256.         if escape[1:2] == "x":
  257.             # hexadecimal escape
  258.             while source.next in HEXDIGITS and len(escape) < 4:
  259.                 escape = escape + source.get()
  260.             if len(escape) != 4:
  261.                 raise ValueError
  262.             return LITERAL, int(escape[2:], 16) & 0xff
  263.         elif escape[1:2] == "0":
  264.             # octal escape
  265.             while source.next in OCTDIGITS and len(escape) < 4:
  266.                 escape = escape + source.get()
  267.             return LITERAL, int(escape[1:], 8) & 0xff
  268.         elif escape[1:2] in DIGITS:
  269.             # octal escape *or* decimal group reference (sigh)
  270.             here = source.tell()
  271.             if source.next in DIGITS:
  272.                 escape = escape + source.get()
  273.                 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and
  274.                     source.next in OCTDIGITS):
  275.                     # got three octal digits; this is an octal escape
  276.                     escape = escape + source.get()
  277.                     return LITERAL, int(escape[1:], 8) & 0xff
  278.             # got at least one decimal digit; this is a group reference
  279.             group = _group(escape, state.groups)
  280.             if group:
  281.                 return GROUPREF, group
  282.             raise ValueError
  283.         if len(escape) == 2:
  284.             return LITERAL, ord(escape[1])
  285.     except ValueError:
  286.         pass
  287.     raise error, "bogus escape: %s" % repr(escape)
  288.  
  289. def _parse_sub(source, state, nested=1):
  290.     # parse an alternation: a|b|c
  291.  
  292.     items = []
  293.     while 1:
  294.         items.append(_parse(source, state))
  295.         if source.match("|"):
  296.             continue
  297.         if not nested:
  298.             break
  299.         if not source.next or source.match(")", 0):
  300.             break
  301.         else:
  302.             raise error, "pattern not properly closed"
  303.  
  304.     if len(items) == 1:
  305.         return items[0]
  306.  
  307.     subpattern = SubPattern(state)
  308.  
  309.     # check if all items share a common prefix
  310.     while 1:
  311.         prefix = None
  312.         for item in items:
  313.             if not item:
  314.                 break
  315.             if prefix is None:
  316.                 prefix = item[0]
  317.             elif item[0] != prefix:
  318.                 break
  319.         else:
  320.             # all subitems start with a common "prefix".
  321.             # move it out of the branch
  322.             for item in items:
  323.                 del item[0]
  324.             subpattern.append(prefix)
  325.             continue # check next one
  326.         break
  327.  
  328.     # check if the branch can be replaced by a character set
  329.     for item in items:
  330.         if len(item) != 1 or item[0][0] != LITERAL:
  331.             break
  332.     else:
  333.         # we can store this as a character set instead of a
  334.         # branch (the compiler may optimize this even more)
  335.         set = []
  336.         for item in items:
  337.             set.append(item[0])
  338.         subpattern.append((IN, set))
  339.         return subpattern
  340.  
  341.     subpattern.append((BRANCH, (None, items)))
  342.     return subpattern
  343.  
  344. def _parse(source, state):
  345.     # parse a simple pattern
  346.  
  347.     subpattern = SubPattern(state)
  348.  
  349.     while 1:
  350.  
  351.         if source.next in ("|", ")"):
  352.             break # end of subpattern
  353.         this = source.get()
  354.         if this is None:
  355.             break # end of pattern
  356.  
  357.         if state.flags & SRE_FLAG_VERBOSE:
  358.             # skip whitespace and comments
  359.             if this in WHITESPACE:
  360.                 continue
  361.             if this == "#":
  362.                 while 1:
  363.                     this = source.get()
  364.                     if this in (None, "\n"):
  365.                         break
  366.                 continue
  367.  
  368.         if this and this[0] not in SPECIAL_CHARS:
  369.             subpattern.append((LITERAL, ord(this)))
  370.  
  371.         elif this == "[":
  372.             # character set
  373.             set = []
  374. ##          if source.match(":"):
  375. ##              pass # handle character classes
  376.             if source.match("^"):
  377.                 set.append((NEGATE, None))
  378.             # check remaining characters
  379.             start = set[:]
  380.             while 1:
  381.                 this = source.get()
  382.                 if this == "]" and set != start:
  383.                     break
  384.                 elif this and this[0] == "\\":
  385.                     code1 = _class_escape(source, this)
  386.                 elif this:
  387.                     code1 = LITERAL, ord(this)
  388.                 else:
  389.                     raise error, "unexpected end of regular expression"
  390.                 if source.match("-"):
  391.                     # potential range
  392.                     this = source.get()
  393.                     if this == "]":
  394.                         if code1[0] is IN:
  395.                             code1 = code1[1][0]
  396.                         set.append(code1)
  397.                         set.append((LITERAL, ord("-")))
  398.                         break
  399.                     else:
  400.                         if this[0] == "\\":
  401.                             code2 = _class_escape(source, this)
  402.                         else:
  403.                             code2 = LITERAL, ord(this)
  404.                         if code1[0] != LITERAL or code2[0] != LITERAL:
  405.                             raise error, "illegal range"
  406.                         lo = code1[1]
  407.                         hi = code2[1]
  408.                         if hi < lo:
  409.                             raise error, "illegal range"
  410.                         set.append((RANGE, (lo, hi)))
  411.                 else:
  412.                     if code1[0] is IN:
  413.                         code1 = code1[1][0]
  414.                     set.append(code1)
  415.  
  416.             # FIXME: <fl> move set optimization to compiler!
  417.             if len(set)==1 and set[0][0] is LITERAL:
  418.                 subpattern.append(set[0]) # optimization
  419.             elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:
  420.                 subpattern.append((NOT_LITERAL, set[1][1])) # optimization
  421.             else:
  422.                 # FIXME: <fl> add charmap optimization
  423.                 subpattern.append((IN, set))
  424.  
  425.         elif this and this[0] in REPEAT_CHARS:
  426.             # repeat previous item
  427.             if this == "?":
  428.                 min, max = 0, 1
  429.             elif this == "*":
  430.                 min, max = 0, MAXREPEAT
  431.             elif this == "+":
  432.                 min, max = 1, MAXREPEAT
  433.             elif this == "{":
  434.                 here = source.tell()
  435.                 min, max = 0, MAXREPEAT
  436.                 lo = hi = ""
  437.                 while source.next in DIGITS:
  438.                     lo = lo + source.get()
  439.                 if source.match(","):
  440.                     while source.next in DIGITS:
  441.                         hi = hi + source.get()
  442.                 else:
  443.                     hi = lo
  444.                 if not source.match("}"):
  445.                     subpattern.append((LITERAL, ord(this)))
  446.                     source.seek(here)
  447.                     continue
  448.                 if lo:
  449.                     min = int(lo)
  450.                 if hi:
  451.                     max = int(hi)
  452.                 # FIXME: <fl> check that hi >= lo!
  453.             else:
  454.                 raise error, "not supported"
  455.             # figure out which item to repeat
  456.             if subpattern:
  457.                 item = subpattern[-1:]
  458.             else:
  459.                 raise error, "nothing to repeat"
  460.             if source.match("?"):
  461.                 subpattern[-1] = (MIN_REPEAT, (min, max, item))
  462.             else:
  463.                 subpattern[-1] = (MAX_REPEAT, (min, max, item))
  464.  
  465.         elif this == ".":
  466.             subpattern.append((ANY, None))
  467.  
  468.         elif this == "(":
  469.             group = 1
  470.             name = None
  471.             if source.match("?"):
  472.                 group = 0
  473.                 # options
  474.                 if source.match("P"):
  475.                     # python extensions
  476.                     if source.match("<"):
  477.                         # named group: skip forward to end of name
  478.                         name = ""
  479.                         while 1:
  480.                             char = source.get()
  481.                             if char is None:
  482.                                 raise error, "unterminated name"
  483.                             if char == ">":
  484.                                 break
  485.                             name = name + char
  486.                         group = 1
  487.                         if not isname(name):
  488.                             raise error, "illegal character in group name"
  489.                     elif source.match("="):
  490.                         # named backreference
  491.                         name = ""
  492.                         while 1:
  493.                             char = source.get()
  494.                             if char is None:
  495.                                 raise error, "unterminated name"
  496.                             if char == ")":
  497.                                 break
  498.                             name = name + char
  499.                         if not isname(name):
  500.                             raise error, "illegal character in group name"
  501.                         gid = state.groupdict.get(name)
  502.                         if gid is None:
  503.                             raise error, "unknown group name"
  504.                         subpattern.append((GROUPREF, gid))
  505.                         continue
  506.                     else:
  507.                         char = source.get()
  508.                         if char is None:
  509.                             raise error, "unexpected end of pattern"
  510.                         raise error, "unknown specifier: ?P%s" % char
  511.                 elif source.match(":"):
  512.                     # non-capturing group
  513.                     group = 2
  514.                 elif source.match("#"):
  515.                     # comment
  516.                     while 1:
  517.                         if source.next is None or source.next == ")":
  518.                             break
  519.                         source.get()
  520.                     if not source.match(")"):
  521.                         raise error, "unbalanced parenthesis"
  522.                     continue
  523.                 elif source.next in ("=", "!", "<"):
  524.                     # lookahead assertions
  525.                     char = source.get()
  526.                     dir = 1
  527.                     if char == "<":
  528.                         if source.next not in ("=", "!"):
  529.                             raise error, "syntax error"
  530.                         dir = -1 # lookbehind
  531.                         char = source.get()
  532.                     p = _parse_sub(source, state)
  533.                     if not source.match(")"):
  534.                         raise error, "unbalanced parenthesis"
  535.                     if char == "=":
  536.                         subpattern.append((ASSERT, (dir, p)))
  537.                     else:
  538.                         subpattern.append((ASSERT_NOT, (dir, p)))
  539.                     continue
  540.                 else:
  541.                     # flags
  542.                     while FLAGS.has_key(source.next):
  543.                         state.flags = state.flags | FLAGS[source.get()]
  544.             if group:
  545.                 # parse group contents
  546.                 if group == 2:
  547.                     # anonymous group
  548.                     group = None
  549.                 else:
  550.                     group = state.getgroup(name)
  551.                 p = _parse_sub(source, state)
  552.                 if not source.match(")"):
  553.                     raise error, "unbalanced parenthesis"
  554.                 subpattern.append((SUBPATTERN, (group, p)))
  555.             else:
  556.                 while 1:
  557.                     char = source.get()
  558.                     if char is None or char == ")":
  559.                         break
  560.                     raise error, "unknown extension"
  561.  
  562.         elif this == "^":
  563.             subpattern.append((AT, AT_BEGINNING))
  564.  
  565.         elif this == "$":
  566.             subpattern.append((AT, AT_END))
  567.  
  568.         elif this and this[0] == "\\":
  569.             code = _escape(source, this, state)
  570.             subpattern.append(code)
  571.  
  572.         else:
  573.             raise error, "parser error"
  574.  
  575.     return subpattern
  576.  
  577. def parse(str, flags=0, pattern=None):
  578.     # parse 're' pattern into list of (opcode, argument) tuples
  579.  
  580.     source = Tokenizer(str)
  581.  
  582.     if pattern is None:
  583.         pattern = Pattern()
  584.     pattern.flags = flags
  585.  
  586.     p = _parse_sub(source, pattern, 0)
  587.  
  588.     tail = source.get()
  589.     if tail == ")":
  590.         raise error, "unbalanced parenthesis"
  591.     elif tail:
  592.         raise error, "bogus characters at end of regular expression"
  593.  
  594.     # p.dump()
  595.  
  596.     if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:
  597.         # the VERBOSE flag was switched on inside the pattern.  to be
  598.         # on the safe side, we'll parse the whole thing again...
  599.         return parse(str, p.pattern.flags)
  600.  
  601.     return p
  602.  
  603. def parse_template(source, pattern):
  604.     # parse 're' replacement string into list of literals and
  605.     # group references
  606.     s = Tokenizer(source)
  607.     p = []
  608.     a = p.append
  609.     while 1:
  610.         this = s.get()
  611.         if this is None:
  612.             break # end of replacement string
  613.         if this and this[0] == "\\":
  614.             # group
  615.             if this == "\\g":
  616.                 name = ""
  617.                 if s.match("<"):
  618.                     while 1:
  619.                         char = s.get()
  620.                         if char is None:
  621.                             raise error, "unterminated group name"
  622.                         if char == ">":
  623.                             break
  624.                         name = name + char
  625.                 if not name:
  626.                     raise error, "bad group name"
  627.                 try:
  628.                     index = int(name)
  629.                 except ValueError:
  630.                     if not isname(name):
  631.                         raise error, "illegal character in group name"
  632.                     try:
  633.                         index = pattern.groupindex[name]
  634.                     except KeyError:
  635.                         raise IndexError, "unknown group name"
  636.                 a((MARK, index))
  637.             elif len(this) > 1 and this[1] in DIGITS:
  638.                 code = None
  639.                 while 1:
  640.                     group = _group(this, pattern.groups+1)
  641.                     if group:
  642.                         if (s.next not in DIGITS or
  643.                             not _group(this + s.next, pattern.groups+1)):
  644.                             code = MARK, int(group)
  645.                             break
  646.                     elif s.next in OCTDIGITS:
  647.                         this = this + s.get()
  648.                     else:
  649.                         break
  650.                 if not code:
  651.                     this = this[1:]
  652.                     code = LITERAL, int(this[-6:], 8) & 0xff
  653.                 a(code)
  654.             else:
  655.                 try:
  656.                     a(ESCAPES[this])
  657.                 except KeyError:
  658.                     for c in this:
  659.                         a((LITERAL, ord(c)))
  660.         else:
  661.             a((LITERAL, ord(this)))
  662.     return p
  663.  
  664. def expand_template(template, match):
  665.     # FIXME: <fl> this is sooooo slow.  drop in the slicelist
  666.     # code instead
  667.     p = []
  668.     a = p.append
  669.     sep = match.string[:0]
  670.     if type(sep) is type(""):
  671.         char = chr
  672.     else:
  673.         char = unichr
  674.     for c, s in template:
  675.         if c is LITERAL:
  676.             a(char(s))
  677.         elif c is MARK:
  678.             s = match.group(s)
  679.             if s is None:
  680.                 raise error, "empty group"
  681.             a(s)
  682.     return string.join(p, sep)
  683.