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 insert(self, index, code):

   143         self.data.insert(index, code)

   144     def append(self, code):

   145         self.data.append(code)

   146     def getwidth(self):

   147         # determine the width (min, max) for this subpattern

   148         if self.width:

   149             return self.width

   150         lo = hi = 0L

   151         UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY)

   152         REPEATCODES = (MIN_REPEAT, MAX_REPEAT)

   153         for op, av in self.data:

   154             if op is BRANCH:

   155                 i = sys.maxint

   156                 j = 0

   157                 for av in av[1]:

   158                     l, h = av.getwidth()

   159                     i = min(i, l)

   160                     j = max(j, h)

   161                 lo = lo + i

   162                 hi = hi + j

   163             elif op is CALL:

   164                 i, j = av.getwidth()

   165                 lo = lo + i

   166                 hi = hi + j

   167             elif op is SUBPATTERN:

   168                 i, j = av[1].getwidth()

   169                 lo = lo + i

   170                 hi = hi + j

   171             elif op in REPEATCODES:

   172                 i, j = av[2].getwidth()

   173                 lo = lo + long(i) * av[0]

   174                 hi = hi + long(j) * av[1]

   175             elif op in UNITCODES:

   176                 lo = lo + 1

   177                 hi = hi + 1

   178             elif op == SUCCESS:

   179                 break

   180         self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint))

   181         return self.width

   182 

   183 class Tokenizer:

   184     def __init__(self, string):

   185         self.string = string

   186         self.index = 0

   187         self.__next()

   188     def __next(self):

   189         if self.index >= len(self.string):

   190             self.next = None

   191             return

   192         char = self.string[self.index]

   193         if char[0] == "\\":

   194             try:

   195                 c = self.string[self.index + 1]

   196             except IndexError:

   197                 raise error, "bogus escape (end of line)"

   198             char = char + c

   199         self.index = self.index + len(char)

   200         self.next = char

   201     def match(self, char, skip=1):

   202         if char == self.next:

   203             if skip:

   204                 self.__next()

   205             return 1

   206         return 0

   207     def get(self):

   208         this = self.next

   209         self.__next()

   210         return this

   211     def tell(self):

   212         return self.index, self.next

   213     def seek(self, index):

   214         self.index, self.next = index

   215 

   216 def isident(char):

   217     return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_"

   218 

   219 def isdigit(char):

   220     return "0" <= char <= "9"

   221 

   222 def isname(name):

   223     # check that group name is a valid string

   224     if not isident(name[0]):

   225         return False

   226     for char in name[1:]:

   227         if not isident(char) and not isdigit(char):

   228             return False

   229     return True

   230 

   231 def _class_escape(source, escape):

   232     # handle escape code inside character class

   233     code = ESCAPES.get(escape)

   234     if code:

   235         return code

   236     code = CATEGORIES.get(escape)

   237     if code:

   238         return code

   239     try:

   240         c = escape[1:2]

   241         if c == "x":

   242             # hexadecimal escape (exactly two digits)

   243             while source.next in HEXDIGITS and len(escape) < 4:

   244                 escape = escape + source.get()

   245             escape = escape[2:]

   246             if len(escape) != 2:

   247                 raise error, "bogus escape: %s" % repr("\\" + escape)

   248             return LITERAL, int(escape, 16) & 0xff

   249         elif c in OCTDIGITS:

   250             # octal escape (up to three digits)

   251             while source.next in OCTDIGITS and len(escape) < 4:

   252                 escape = escape + source.get()

   253             escape = escape[1:]

   254             return LITERAL, int(escape, 8) & 0xff

   255         elif c in DIGITS:

   256             raise error, "bogus escape: %s" % repr(escape)

   257         if len(escape) == 2:

   258             return LITERAL, ord(escape[1])

   259     except ValueError:

   260         pass

   261     raise error, "bogus escape: %s" % repr(escape)

   262 

   263 def _escape(source, escape, state):

   264     # handle escape code in expression

   265     code = CATEGORIES.get(escape)

   266     if code:

   267         return code

   268     code = ESCAPES.get(escape)

   269     if code:

   270         return code

   271     try:

   272         c = escape[1:2]

   273         if c == "x":

   274             # hexadecimal escape

   275             while source.next in HEXDIGITS and len(escape) < 4:

   276                 escape = escape + source.get()

   277             if len(escape) != 4:

   278                 raise ValueError

   279             return LITERAL, int(escape[2:], 16) & 0xff

   280         elif c == "0":

   281             # octal escape

   282             while source.next in OCTDIGITS and len(escape) < 4:

   283                 escape = escape + source.get()

   284             return LITERAL, int(escape[1:], 8) & 0xff

   285         elif c in DIGITS:

   286             # octal escape *or* decimal group reference (sigh)

   287             if source.next in DIGITS:

   288                 escape = escape + source.get()

   289                 if (escape[1] in OCTDIGITS and escape[2] in OCTDIGITS and

   290                     source.next in OCTDIGITS):

   291                     # got three octal digits; this is an octal escape

   292                     escape = escape + source.get()

   293                     return LITERAL, int(escape[1:], 8) & 0xff

   294             # not an octal escape, so this is a group reference

   295             group = int(escape[1:])

   296             if group < state.groups:

   297                 if not state.checkgroup(group):

   298                     raise error, "cannot refer to open group"

   299                 return GROUPREF, group

   300             raise ValueError

   301         if len(escape) == 2:

   302             return LITERAL, ord(escape[1])

   303     except ValueError:

   304         pass

   305     raise error, "bogus escape: %s" % repr(escape)

   306 

   307 def _parse_sub(source, state, nested=1):

   308     # parse an alternation: a|b|c

   309 

   310     items = []

   311     itemsappend = items.append

   312     sourcematch = source.match

   313     while 1:

   314         itemsappend(_parse(source, state))

   315         if sourcematch("|"):

   316             continue

   317         if not nested:

   318             break

   319         if not source.next or sourcematch(")", 0):

   320             break

   321         else:

   322             raise error, "pattern not properly closed"

   323 

   324     if len(items) == 1:

   325         return items[0]

   326 

   327     subpattern = SubPattern(state)

   328     subpatternappend = subpattern.append

   329 

   330     # check if all items share a common prefix

   331     while 1:

   332         prefix = None

   333         for item in items:

   334             if not item:

   335                 break

   336             if prefix is None:

   337                 prefix = item[0]

   338             elif item[0] != prefix:

   339                 break

   340         else:

   341             # all subitems start with a common "prefix".

   342             # move it out of the branch

   343             for item in items:

   344                 del item[0]

   345             subpatternappend(prefix)

   346             continue # check next one

   347         break

   348 

   349     # check if the branch can be replaced by a character set

   350     for item in items:

   351         if len(item) != 1 or item[0][0] != LITERAL:

   352             break

   353     else:

   354         # we can store this as a character set instead of a

   355         # branch (the compiler may optimize this even more)

   356         set = []

   357         setappend = set.append

   358         for item in items:

   359             setappend(item[0])

   360         subpatternappend((IN, set))

   361         return subpattern

   362 

   363     subpattern.append((BRANCH, (None, items)))

   364     return subpattern

   365 

   366 def _parse_sub_cond(source, state, condgroup):

   367     item_yes = _parse(source, state)

   368     if source.match("|"):

   369         item_no = _parse(source, state)

   370         if source.match("|"):

   371             raise error, "conditional backref with more than two branches"

   372     else:

   373         item_no = None

   374     if source.next and not source.match(")", 0):

   375         raise error, "pattern not properly closed"

   376     subpattern = SubPattern(state)

   377     subpattern.append((GROUPREF_EXISTS, (condgroup, item_yes, item_no)))

   378     return subpattern

   379 

   380 _PATTERNENDERS = set("|)")

   381 _ASSERTCHARS = set("=!<")

   382 _LOOKBEHINDASSERTCHARS = set("=!")

   383 _REPEATCODES = set([MIN_REPEAT, MAX_REPEAT])

   384 

   385 def _parse(source, state):

   386     # parse a simple pattern

   387     subpattern = SubPattern(state)

   388 

   389     # precompute constants into local variables

   390     subpatternappend = subpattern.append

   391     sourceget = source.get

   392     sourcematch = source.match

   393     _len = len

   394     PATTERNENDERS = _PATTERNENDERS

   395     ASSERTCHARS = _ASSERTCHARS

   396     LOOKBEHINDASSERTCHARS = _LOOKBEHINDASSERTCHARS

   397     REPEATCODES = _REPEATCODES

   398 

   399     while 1:

   400 

   401         if source.next in PATTERNENDERS:

   402             break # end of subpattern

   403         this = sourceget()

   404         if this is None:

   405             break # end of pattern

   406 

   407         if state.flags & SRE_FLAG_VERBOSE:

   408             # skip whitespace and comments

   409             if this in WHITESPACE:

   410                 continue

   411             if this == "#":

   412                 while 1:

   413                     this = sourceget()

   414                     if this in (None, "\n"):

   415                         break

   416                 continue

   417 

   418         if this and this[0] not in SPECIAL_CHARS:

   419             subpatternappend((LITERAL, ord(this)))

   420 

   421         elif this == "[":

   422             # character set

   423             set = []

   424             setappend = set.append

   425 ##          if sourcematch(":"):

   426 ##              pass # handle character classes

   427             if sourcematch("^"):

   428                 setappend((NEGATE, None))

   429             # check remaining characters

   430             start = set[:]

   431             while 1:

   432                 this = sourceget()

   433                 if this == "]" and set != start:

   434                     break

   435                 elif this and this[0] == "\\":

   436                     code1 = _class_escape(source, this)

   437                 elif this:

   438                     code1 = LITERAL, ord(this)

   439                 else:

   440                     raise error, "unexpected end of regular expression"

   441                 if sourcematch("-"):

   442                     # potential range

   443                     this = sourceget()

   444                     if this == "]":

   445                         if code1[0] is IN:

   446                             code1 = code1[1][0]

   447                         setappend(code1)

   448                         setappend((LITERAL, ord("-")))

   449                         break

   450                     elif this:

   451                         if this[0] == "\\":

   452                             code2 = _class_escape(source, this)

   453                         else:

   454                             code2 = LITERAL, ord(this)

   455                         if code1[0] != LITERAL or code2[0] != LITERAL:

   456                             raise error, "bad character range"

   457                         lo = code1[1]

   458                         hi = code2[1]

   459                         if hi < lo:

   460                             raise error, "bad character range"

   461                         setappend((RANGE, (lo, hi)))

   462                     else:

   463                         raise error, "unexpected end of regular expression"

   464                 else:

   465                     if code1[0] is IN:

   466                         code1 = code1[1][0]

   467                     setappend(code1)

   468 

   469             # XXX: <fl> should move set optimization to compiler!

   470             if _len(set)==1 and set[0][0] is LITERAL:

   471                 subpatternappend(set[0]) # optimization

   472             elif _len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL:

   473                 subpatternappend((NOT_LITERAL, set[1][1])) # optimization

   474             else:

   475                 # XXX: <fl> should add charmap optimization here

   476                 subpatternappend((IN, set))

   477 

   478         elif this and this[0] in REPEAT_CHARS:

   479             # repeat previous item

   480             if this == "?":

   481                 min, max = 0, 1

   482             elif this == "*":

   483                 min, max = 0, MAXREPEAT

   484 

   485             elif this == "+":

   486                 min, max = 1, MAXREPEAT

   487             elif this == "{":

   488                 if source.next == "}":

   489                     subpatternappend((LITERAL, ord(this)))

   490                     continue

   491                 here = source.tell()

   492                 min, max = 0, MAXREPEAT

   493                 lo = hi = ""

   494                 while source.next in DIGITS:

   495                     lo = lo + source.get()

   496                 if sourcematch(","):

   497                     while source.next in DIGITS:

   498                         hi = hi + sourceget()

   499                 else:

   500                     hi = lo

   501                 if not sourcematch("}"):

   502                     subpatternappend((LITERAL, ord(this)))

   503                     source.seek(here)

   504                     continue

   505                 if lo:

   506                     min = int(lo)

   507                 if hi:

   508                     max = int(hi)

   509                 if max < min:

   510                     raise error, "bad repeat interval"

   511             else:

   512                 raise error, "not supported"

   513             # figure out which item to repeat

   514             if subpattern:

   515                 item = subpattern[-1:]

   516             else:

   517                 item = None

   518             if not item or (_len(item) == 1 and item[0][0] == AT):

   519                 raise error, "nothing to repeat"

   520             if item[0][0] in REPEATCODES:

   521                 raise error, "multiple repeat"

   522             if sourcematch("?"):

   523                 subpattern[-1] = (MIN_REPEAT, (min, max, item))

   524             else:

   525                 subpattern[-1] = (MAX_REPEAT, (min, max, item))

   526 

   527         elif this == ".":

   528             subpatternappend((ANY, None))

   529 

   530         elif this == "(":

   531             group = 1

   532             name = None

   533             condgroup = None

   534             if sourcematch("?"):

   535                 group = 0

   536                 # options

   537                 if sourcematch("P"):

   538                     # python extensions

   539                     if sourcematch("<"):

   540                         # named group: skip forward to end of name

   541                         name = ""

   542                         while 1:

   543                             char = sourceget()

   544                             if char is None:

   545                                 raise error, "unterminated name"

   546                             if char == ">":

   547                                 break

   548                             name = name + char

   549                         group = 1

   550                         if not isname(name):

   551                             raise error, "bad character in group name"

   552                     elif sourcematch("="):

   553                         # named backreference

   554                         name = ""

   555                         while 1:

   556                             char = sourceget()

   557                             if char is None:

   558                                 raise error, "unterminated name"

   559                             if char == ")":

   560                                 break

   561                             name = name + char

   562                         if not isname(name):

   563                             raise error, "bad character in group name"

   564                         gid = state.groupdict.get(name)

   565                         if gid is None:

   566                             raise error, "unknown group name"

   567                         subpatternappend((GROUPREF, gid))

   568                         continue

   569                     else:

   570                         char = sourceget()

   571                         if char is None:

   572                             raise error, "unexpected end of pattern"

   573                         raise error, "unknown specifier: ?P%s" % char

   574                 elif sourcematch(":"):

   575                     # non-capturing group

   576                     group = 2

   577                 elif sourcematch("#"):

   578                     # comment

   579                     while 1:

   580                         if source.next is None or source.next == ")":

   581                             break

   582                         sourceget()

   583                     if not sourcematch(")"):

   584                         raise error, "unbalanced parenthesis"

   585                     continue

   586                 elif source.next in ASSERTCHARS:

   587                     # lookahead assertions

   588                     char = sourceget()

   589                     dir = 1

   590                     if char == "<":

   591                         if source.next not in LOOKBEHINDASSERTCHARS:

   592                             raise error, "syntax error"

   593                         dir = -1 # lookbehind

   594                         char = sourceget()

   595                     p = _parse_sub(source, state)

   596                     if not sourcematch(")"):

   597                         raise error, "unbalanced parenthesis"

   598                     if char == "=":

   599                         subpatternappend((ASSERT, (dir, p)))

   600                     else:

   601                         subpatternappend((ASSERT_NOT, (dir, p)))

   602                     continue

   603                 elif sourcematch("("):

   604                     # conditional backreference group

   605                     condname = ""

   606                     while 1:

   607                         char = sourceget()

   608                         if char is None:

   609                             raise error, "unterminated name"

   610                         if char == ")":

   611                             break

   612                         condname = condname + char

   613                     group = 2

   614                     if isname(condname):

   615                         condgroup = state.groupdict.get(condname)

   616                         if condgroup is None:

   617                             raise error, "unknown group name"

   618                     else:

   619                         try:

   620                             condgroup = int(condname)

   621                         except ValueError:

   622                             raise error, "bad character in group name"

   623                 else:

   624                     # flags

   625                     if not source.next in FLAGS:

   626                         raise error, "unexpected end of pattern"

   627                     while source.next in FLAGS:

   628                         state.flags = state.flags | FLAGS[sourceget()]

   629             if group:

   630                 # parse group contents

   631                 if group == 2:

   632                     # anonymous group

   633                     group = None

   634                 else:

   635                     group = state.opengroup(name)

   636                 if condgroup:

   637                     p = _parse_sub_cond(source, state, condgroup)

   638                 else:

   639                     p = _parse_sub(source, state)

   640                 if not sourcematch(")"):

   641                     raise error, "unbalanced parenthesis"

   642                 if group is not None:

   643                     state.closegroup(group)

   644                 subpatternappend((SUBPATTERN, (group, p)))

   645             else:

   646                 while 1:

   647                     char = sourceget()

   648                     if char is None:

   649                         raise error, "unexpected end of pattern"

   650                     if char == ")":

   651                         break

   652                     raise error, "unknown extension"

   653 

   654         elif this == "^":

   655             subpatternappend((AT, AT_BEGINNING))

   656 

   657         elif this == "$":

   658             subpattern.append((AT, AT_END))

   659 

   660         elif this and this[0] == "\\":

   661             code = _escape(source, this, state)

   662             subpatternappend(code)

   663 

   664         else:

   665             raise error, "parser error"

   666 

   667     return subpattern

   668 

   669 def parse(str, flags=0, pattern=None):

   670     # parse 're' pattern into list of (opcode, argument) tuples

   671 

   672     source = Tokenizer(str)

   673 

   674     if pattern is None:

   675         pattern = Pattern()

   676     pattern.flags = flags

   677     pattern.str = str

   678 

   679     p = _parse_sub(source, pattern, 0)

   680 

   681     tail = source.get()

   682     if tail == ")":

   683         raise error, "unbalanced parenthesis"

   684     elif tail:

   685         raise error, "bogus characters at end of regular expression"

   686 

   687     if flags & SRE_FLAG_DEBUG:

   688         p.dump()

   689 

   690     if not (flags & SRE_FLAG_VERBOSE) and p.pattern.flags & SRE_FLAG_VERBOSE:

   691         # the VERBOSE flag was switched on inside the pattern.  to be

   692         # on the safe side, we'll parse the whole thing again...

   693         return parse(str, p.pattern.flags)

   694 

   695     return p

   696 

   697 def parse_template(source, pattern):

   698     # parse 're' replacement string into list of literals and

   699     # group references

   700     s = Tokenizer(source)

   701     sget = s.get

   702     p = []

   703     a = p.append

   704     def literal(literal, p=p, pappend=a):

   705         if p and p[-1][0] is LITERAL:

   706             p[-1] = LITERAL, p[-1][1] + literal

   707         else:

   708             pappend((LITERAL, literal))

   709     sep = source[:0]

   710     if type(sep) is type(""):

   711         makechar = chr

   712     else:

   713         makechar = unichr

   714     while 1:

   715         this = sget()

   716         if this is None:

   717             break # end of replacement string

   718         if this and this[0] == "\\":

   719             # group

   720             c = this[1:2]

   721             if c == "g":

   722                 name = ""

   723                 if s.match("<"):

   724                     while 1:

   725                         char = sget()

   726                         if char is None:

   727                             raise error, "unterminated group name"

   728                         if char == ">":

   729                             break

   730                         name = name + char

   731                 if not name:

   732                     raise error, "bad group name"

   733                 try:

   734                     index = int(name)

   735                     if index < 0:

   736                         raise error, "negative group number"

   737                 except ValueError:

   738                     if not isname(name):

   739                         raise error, "bad character in group name"

   740                     try:

   741                         index = pattern.groupindex[name]

   742                     except KeyError:

   743                         raise IndexError, "unknown group name"

   744                 a((MARK, index))

   745             elif c == "0":

   746                 if s.next in OCTDIGITS:

   747                     this = this + sget()

   748                     if s.next in OCTDIGITS:

   749                         this = this + sget()

   750                 literal(makechar(int(this[1:], 8) & 0xff))

   751             elif c in DIGITS:

   752                 isoctal = False

   753                 if s.next in DIGITS:

   754                     this = this + sget()

   755                     if (c in OCTDIGITS and this[2] in OCTDIGITS and

   756                         s.next in OCTDIGITS):

   757                         this = this + sget()

   758                         isoctal = True

   759                         literal(makechar(int(this[1:], 8) & 0xff))

   760                 if not isoctal:

   761                     a((MARK, int(this[1:])))

   762             else:

   763                 try:

   764                     this = makechar(ESCAPES[this][1])

   765                 except KeyError:

   766                     pass

   767                 literal(this)

   768         else:

   769             literal(this)

   770     # convert template to groups and literals lists

   771     i = 0

   772     groups = []

   773     groupsappend = groups.append

   774     literals = [None] * len(p)

   775     for c, s in p:

   776         if c is MARK:

   777             groupsappend((i, s))

   778             # literal[i] is already None

   779         else:

   780             literals[i] = s

   781         i = i + 1

   782     return groups, literals

   783 

   784 def expand_template(template, match):

   785     g = match.group

   786     sep = match.string[:0]

   787     groups, literals = template

   788     literals = literals[:]

   789     try:

   790         for index, group in groups:

   791             literals[index] = s = g(group)

   792             if s is None:

   793                 raise error, "unmatched group"

   794     except IndexError:

   795         raise error, "invalid group reference"

   796     return sep.join(literals)