Lib/sre_parse.py

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