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