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