diff options
Diffstat (limited to 'Lib/sre_parse.py')
-rw-r--r-- | Lib/sre_parse.py | 836 |
1 files changed, 418 insertions, 418 deletions
diff --git a/Lib/sre_parse.py b/Lib/sre_parse.py index ec934fe..40f2cb5 100644 --- a/Lib/sre_parse.py +++ b/Lib/sre_parse.py @@ -67,106 +67,106 @@ FLAGS = { class State: def __init__(self): - self.flags = 0 - self.groups = 1 - self.groupdict = {} + self.flags = 0 + self.groups = 1 + self.groupdict = {} def getgroup(self, name=None): - gid = self.groups - self.groups = gid + 1 - if name: - self.groupdict[name] = gid - return gid + gid = self.groups + self.groups = gid + 1 + if name: + self.groupdict[name] = gid + return gid class SubPattern: # a subpattern, in intermediate form def __init__(self, pattern, data=None): - self.pattern = pattern - if not data: - data = [] - self.data = data - self.width = None + self.pattern = pattern + if not data: + data = [] + self.data = data + self.width = None def __repr__(self): - return repr(self.data) + return repr(self.data) def __len__(self): - return len(self.data) + return len(self.data) def __delitem__(self, index): - del self.data[index] + del self.data[index] def __getitem__(self, index): - return self.data[index] + return self.data[index] def __setitem__(self, index, code): - self.data[index] = code + self.data[index] = code def __getslice__(self, start, stop): - return SubPattern(self.pattern, self.data[start:stop]) + return SubPattern(self.pattern, self.data[start:stop]) def insert(self, index, code): - self.data.insert(index, code) + self.data.insert(index, code) def append(self, code): - self.data.append(code) + self.data.append(code) def getwidth(self): - # determine the width (min, max) for this subpattern - if self.width: - return self.width - lo = hi = 0L - for op, av in self.data: - if op is BRANCH: - l = sys.maxint - h = 0 - for av in av[1]: - i, j = av.getwidth() - l = min(l, i) - h = min(h, j) - lo = lo + i - hi = hi + j - elif op is CALL: - i, j = av.getwidth() - lo = lo + i - hi = hi + j - elif op is SUBPATTERN: - i, j = av[1].getwidth() - lo = lo + i - hi = hi + j - elif op in (MIN_REPEAT, MAX_REPEAT): - i, j = av[2].getwidth() - lo = lo + long(i) * av[0] - hi = hi + long(j) * av[1] - elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY): - lo = lo + 1 - hi = hi + 1 - elif op == SUCCESS: - break - self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint)) - return self.width + # determine the width (min, max) for this subpattern + if self.width: + return self.width + lo = hi = 0L + for op, av in self.data: + if op is BRANCH: + l = sys.maxint + h = 0 + for av in av[1]: + i, j = av.getwidth() + l = min(l, i) + h = min(h, j) + lo = lo + i + hi = hi + j + elif op is CALL: + i, j = av.getwidth() + lo = lo + i + hi = hi + j + elif op is SUBPATTERN: + i, j = av[1].getwidth() + lo = lo + i + hi = hi + j + elif op in (MIN_REPEAT, MAX_REPEAT): + i, j = av[2].getwidth() + lo = lo + long(i) * av[0] + hi = hi + long(j) * av[1] + elif op in (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY): + lo = lo + 1 + hi = hi + 1 + elif op == SUCCESS: + break + self.width = int(min(lo, sys.maxint)), int(min(hi, sys.maxint)) + return self.width class Tokenizer: def __init__(self, string): - self.index = 0 - self.string = string - self.next = self.__next() + self.index = 0 + self.string = string + self.next = self.__next() def __next(self): - if self.index >= len(self.string): - return None - char = self.string[self.index] - if char[0] == "\\": - try: - c = self.string[self.index + 1] - except IndexError: - raise error, "bogus escape" - char = char + c - self.index = self.index + len(char) - return char + if self.index >= len(self.string): + return None + char = self.string[self.index] + if char[0] == "\\": + try: + c = self.string[self.index + 1] + except IndexError: + raise error, "bogus escape" + char = char + c + self.index = self.index + len(char) + return char def match(self, char): - if char == self.next: - self.next = self.__next() - return 1 - return 0 + if char == self.next: + self.next = self.__next() + return 1 + return 0 def match_set(self, set): - if self.next and self.next in set: - self.next = self.__next() - return 1 - return 0 + if self.next and self.next in set: + self.next = self.__next() + return 1 + return 0 def get(self): - this = self.next - self.next = self.__next() - return this + this = self.next + self.next = self.__next() + return this def isident(char): return "a" <= char <= "z" or "A" <= char <= "Z" or char == "_" @@ -180,83 +180,83 @@ def isname(name): # expression instead, but I seem to have certain bootstrapping # problems here ;-) if not isident(name[0]): - return 0 + return 0 for char in name: - if not isident(char) and not isdigit(char): - return 0 + if not isident(char) and not isdigit(char): + return 0 return 1 def _group(escape, groups): # check if the escape string represents a valid group try: - group = int(escape[1:]) - if group and group < groups: - return group + group = int(escape[1:]) + if group and group < groups: + return group except ValueError: - pass + pass return None # not a valid group def _class_escape(source, escape): # handle escape code inside character class code = ESCAPES.get(escape) if code: - return code + return code code = CATEGORIES.get(escape) if code: - return code + return code try: - if escape[1:2] == "x": - while source.next in HEXDIGITS: - escape = escape + source.get() - escape = escape[2:] - # FIXME: support unicode characters! - return LITERAL, chr(int(escape[-4:], 16) & 0xff) - elif str(escape[1:2]) in OCTDIGITS: - while source.next in OCTDIGITS: - escape = escape + source.get() - escape = escape[1:] - # FIXME: support unicode characters! - return LITERAL, chr(int(escape[-6:], 8) & 0xff) - if len(escape) == 2: - return LITERAL, escape[1] + if escape[1:2] == "x": + while source.next in HEXDIGITS: + escape = escape + source.get() + escape = escape[2:] + # FIXME: support unicode characters! + return LITERAL, chr(int(escape[-4:], 16) & 0xff) + elif str(escape[1:2]) in OCTDIGITS: + while source.next in OCTDIGITS: + escape = escape + source.get() + escape = escape[1:] + # FIXME: support unicode characters! + return LITERAL, chr(int(escape[-6:], 8) & 0xff) + if len(escape) == 2: + return LITERAL, escape[1] except ValueError: - pass + pass raise error, "bogus escape: %s" % repr(escape) def _escape(source, escape, state): # handle escape code in expression code = CATEGORIES.get(escape) if code: - return code + return code code = ESCAPES.get(escape) if code: - return code + return code try: - if escape[1:2] == "x": - while source.next in HEXDIGITS: - escape = escape + source.get() - escape = escape[2:] - # FIXME: support unicode characters! - return LITERAL, chr(int(escape[-4:], 16) & 0xff) - elif escape[1:2] in DIGITS: - while 1: - group = _group(escape, state.groups) - if group: - if (not source.next or - not _group(escape + source.next, state.groups)): - return GROUP, group - escape = escape + source.get() - elif source.next in OCTDIGITS: - escape = escape + source.get() - else: - break - escape = escape[1:] - # FIXME: support unicode characters! - return LITERAL, chr(int(escape[-6:], 8) & 0xff) - if len(escape) == 2: - return LITERAL, escape[1] + if escape[1:2] == "x": + while source.next in HEXDIGITS: + escape = escape + source.get() + escape = escape[2:] + # FIXME: support unicode characters! + return LITERAL, chr(int(escape[-4:], 16) & 0xff) + elif escape[1:2] in DIGITS: + while 1: + group = _group(escape, state.groups) + if group: + if (not source.next or + not _group(escape + source.next, state.groups)): + return GROUP, group + escape = escape + source.get() + elif source.next in OCTDIGITS: + escape = escape + source.get() + else: + break + escape = escape[1:] + # FIXME: support unicode characters! + return LITERAL, chr(int(escape[-6:], 8) & 0xff) + if len(escape) == 2: + return LITERAL, escape[1] except ValueError: - pass + pass raise error, "bogus escape: %s" % repr(escape) @@ -268,35 +268,35 @@ def _branch(pattern, items): # check if all items share a common prefix while 1: - prefix = None - for item in items: - if not item: - break - if prefix is None: - prefix = item[0] - elif item[0] != prefix: - break - else: - # all subitems start with a common "prefix". - # move it out of the branch - for item in items: - del item[0] - subpattern.append(prefix) - continue # check next one - break + prefix = None + for item in items: + if not item: + break + if prefix is None: + prefix = item[0] + elif item[0] != prefix: + break + else: + # all subitems start with a common "prefix". + # move it out of the branch + for item in items: + del item[0] + subpattern.append(prefix) + continue # check next one + break # check if the branch can be replaced by a character set for item in items: - if len(item) != 1 or item[0][0] != LITERAL: - break + if len(item) != 1 or item[0][0] != LITERAL: + break else: - # we can store this as a character set instead of a - # branch (FIXME: use a range if possible) - set = [] - for item in items: - set.append(item[0]) - subpattern.append((IN, set)) - return subpattern + # we can store this as a character set instead of a + # branch (FIXME: use a range if possible) + set = [] + for item in items: + set.append(item[0]) + subpattern.append((IN, set)) + return subpattern subpattern.append((BRANCH, (None, items))) return subpattern @@ -309,197 +309,197 @@ def _parse(source, state, flags=0): while 1: - if source.next in ("|", ")"): - break # end of subpattern - this = source.get() - if this is None: - break # end of pattern - - if state.flags & SRE_FLAG_VERBOSE: - # skip whitespace and comments - if this in WHITESPACE: - continue - if this == "#": - while 1: - this = source.get() - if this in (None, "\n"): - break - continue - - if this and this[0] not in SPECIAL_CHARS: - subpattern.append((LITERAL, this)) - - elif this == "[": - # character set - set = [] -## if source.match(":"): -## pass # handle character classes - if source.match("^"): - set.append((NEGATE, None)) - # check remaining characters - start = set[:] - while 1: - this = source.get() - if this == "]" and set != start: - break - elif this and this[0] == "\\": - code1 = _class_escape(source, this) - elif this: - code1 = LITERAL, this - else: - raise error, "unexpected end of regular expression" - if source.match("-"): - # potential range - this = source.get() - if this == "]": - set.append(code1) - set.append((LITERAL, "-")) - break - else: - if this[0] == "\\": - code2 = _class_escape(source, this) - else: - code2 = LITERAL, this - if code1[0] != LITERAL or code2[0] != LITERAL: - raise error, "illegal range" - if len(code1[1]) != 1 or len(code2[1]) != 1: - raise error, "illegal range" - set.append((RANGE, (code1[1], code2[1]))) - else: - if code1[0] is IN: - code1 = code1[1][0] - set.append(code1) - - # FIXME: <fl> move set optimization to compiler! - if len(set)==1 and set[0][0] is LITERAL: - subpattern.append(set[0]) # optimization - elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL: - subpattern.append((NOT_LITERAL, set[1][1])) # optimization - else: - # FIXME: <fl> add charmap optimization - subpattern.append((IN, set)) - - elif this and this[0] in REPEAT_CHARS: - # repeat previous item - if this == "?": - min, max = 0, 1 - elif this == "*": - min, max = 0, MAXREPEAT - elif this == "+": - min, max = 1, MAXREPEAT - elif this == "{": - min, max = 0, MAXREPEAT - lo = hi = "" - while source.next in DIGITS: - lo = lo + source.get() - if source.match(","): - while source.next in DIGITS: - hi = hi + source.get() - else: - hi = lo - if not source.match("}"): - raise error, "bogus range" - if lo: - min = int(lo) - if hi: - max = int(hi) - # FIXME: <fl> check that hi >= lo! - else: - raise error, "not supported" - # figure out which item to repeat - if subpattern: - item = subpattern[-1:] - else: - raise error, "nothing to repeat" - if source.match("?"): - subpattern[-1] = (MIN_REPEAT, (min, max, item)) - else: - subpattern[-1] = (MAX_REPEAT, (min, max, item)) - - elif this == ".": - subpattern.append((ANY, None)) - - elif this == "(": - group = 1 - name = None - if source.match("?"): - group = 0 - # options - if source.match("P"): - # python extensions - if source.match("<"): - # named group: skip forward to end of name - name = "" - while 1: - char = source.get() - if char is None: - raise error, "unterminated name" - if char == ">": - break - name = name + char - group = 1 - if not isname(name): - raise error, "illegal character in group name" - elif source.match("="): - # named backreference - raise error, "not yet implemented" - else: - char = source.get() - if char is None: - raise error, "unexpected end of pattern" - raise error, "unknown specifier: ?P%s" % char - elif source.match(":"): - # non-capturing group - group = 2 - elif source.match("#"): - # comment - while 1: - if source.next is None or source.next == ")": - break - source.get() - else: - # flags - while FLAGS.has_key(source.next): - state.flags = state.flags | FLAGS[source.get()] - if group: - # parse group contents - b = [] - if group == 2: - # anonymous group - group = None - else: - group = state.getgroup(name) - while 1: - p = _parse(source, state, flags) - if source.match(")"): - if b: - b.append(p) - p = _branch(state, b) - subpattern.append((SUBPATTERN, (group, p))) - break - elif source.match("|"): - b.append(p) - else: - raise error, "group not properly closed" - else: - while 1: - char = source.get() - if char is None or char == ")": - break - raise error, "unknown extension" - - elif this == "^": - subpattern.append((AT, AT_BEGINNING)) - - elif this == "$": - subpattern.append((AT, AT_END)) - - elif this and this[0] == "\\": - code = _escape(source, this, state) - subpattern.append(code) - - else: - raise error, "parser error" + if source.next in ("|", ")"): + break # end of subpattern + this = source.get() + if this is None: + break # end of pattern + + if state.flags & SRE_FLAG_VERBOSE: + # skip whitespace and comments + if this in WHITESPACE: + continue + if this == "#": + while 1: + this = source.get() + if this in (None, "\n"): + break + continue + + if this and this[0] not in SPECIAL_CHARS: + subpattern.append((LITERAL, this)) + + elif this == "[": + # character set + set = [] +## if source.match(":"): +## pass # handle character classes + if source.match("^"): + set.append((NEGATE, None)) + # check remaining characters + start = set[:] + while 1: + this = source.get() + if this == "]" and set != start: + break + elif this and this[0] == "\\": + code1 = _class_escape(source, this) + elif this: + code1 = LITERAL, this + else: + raise error, "unexpected end of regular expression" + if source.match("-"): + # potential range + this = source.get() + if this == "]": + set.append(code1) + set.append((LITERAL, "-")) + break + else: + if this[0] == "\\": + code2 = _class_escape(source, this) + else: + code2 = LITERAL, this + if code1[0] != LITERAL or code2[0] != LITERAL: + raise error, "illegal range" + if len(code1[1]) != 1 or len(code2[1]) != 1: + raise error, "illegal range" + set.append((RANGE, (code1[1], code2[1]))) + else: + if code1[0] is IN: + code1 = code1[1][0] + set.append(code1) + + # FIXME: <fl> move set optimization to compiler! + if len(set)==1 and set[0][0] is LITERAL: + subpattern.append(set[0]) # optimization + elif len(set)==2 and set[0][0] is NEGATE and set[1][0] is LITERAL: + subpattern.append((NOT_LITERAL, set[1][1])) # optimization + else: + # FIXME: <fl> add charmap optimization + subpattern.append((IN, set)) + + elif this and this[0] in REPEAT_CHARS: + # repeat previous item + if this == "?": + min, max = 0, 1 + elif this == "*": + min, max = 0, MAXREPEAT + elif this == "+": + min, max = 1, MAXREPEAT + elif this == "{": + min, max = 0, MAXREPEAT + lo = hi = "" + while source.next in DIGITS: + lo = lo + source.get() + if source.match(","): + while source.next in DIGITS: + hi = hi + source.get() + else: + hi = lo + if not source.match("}"): + raise error, "bogus range" + if lo: + min = int(lo) + if hi: + max = int(hi) + # FIXME: <fl> check that hi >= lo! + else: + raise error, "not supported" + # figure out which item to repeat + if subpattern: + item = subpattern[-1:] + else: + raise error, "nothing to repeat" + if source.match("?"): + subpattern[-1] = (MIN_REPEAT, (min, max, item)) + else: + subpattern[-1] = (MAX_REPEAT, (min, max, item)) + + elif this == ".": + subpattern.append((ANY, None)) + + elif this == "(": + group = 1 + name = None + if source.match("?"): + group = 0 + # options + if source.match("P"): + # python extensions + if source.match("<"): + # named group: skip forward to end of name + name = "" + while 1: + char = source.get() + if char is None: + raise error, "unterminated name" + if char == ">": + break + name = name + char + group = 1 + if not isname(name): + raise error, "illegal character in group name" + elif source.match("="): + # named backreference + raise error, "not yet implemented" + else: + char = source.get() + if char is None: + raise error, "unexpected end of pattern" + raise error, "unknown specifier: ?P%s" % char + elif source.match(":"): + # non-capturing group + group = 2 + elif source.match("#"): + # comment + while 1: + if source.next is None or source.next == ")": + break + source.get() + else: + # flags + while FLAGS.has_key(source.next): + state.flags = state.flags | FLAGS[source.get()] + if group: + # parse group contents + b = [] + if group == 2: + # anonymous group + group = None + else: + group = state.getgroup(name) + while 1: + p = _parse(source, state, flags) + if source.match(")"): + if b: + b.append(p) + p = _branch(state, b) + subpattern.append((SUBPATTERN, (group, p))) + break + elif source.match("|"): + b.append(p) + else: + raise error, "group not properly closed" + else: + while 1: + char = source.get() + if char is None or char == ")": + break + raise error, "unknown extension" + + elif this == "^": + subpattern.append((AT, AT_BEGINNING)) + + elif this == "$": + subpattern.append((AT, AT_END)) + + elif this and this[0] == "\\": + code = _escape(source, this, state) + subpattern.append(code) + + else: + raise error, "parser error" return subpattern @@ -509,19 +509,19 @@ def parse(pattern, flags=0): state = State() b = [] while 1: - p = _parse(source, state, flags) - tail = source.get() - if tail == "|": - b.append(p) - elif tail == ")": - raise error, "unbalanced parenthesis" - elif tail is None: - if b: - b.append(p) - p = _branch(state, b) - break - else: - raise error, "bogus characters at end of regular expression" + p = _parse(source, state, flags) + tail = source.get() + if tail == "|": + b.append(p) + elif tail == ")": + raise error, "unbalanced parenthesis" + elif tail is None: + if b: + b.append(p) + p = _branch(state, b) + break + else: + raise error, "bogus characters at end of regular expression" return p def parse_template(source, pattern): @@ -531,59 +531,59 @@ def parse_template(source, pattern): p = [] a = p.append while 1: - this = s.get() - if this is None: - break # end of replacement string - if this and this[0] == "\\": - # group - if this == "\\g": - name = "" - if s.match("<"): - while 1: - char = s.get() - if char is None: - raise error, "unterminated group name" - if char == ">": - break - name = name + char - if not name: - raise error, "bad group name" - try: - index = int(name) - except ValueError: - if not isname(name): - raise error, "illegal character in group name" - try: - index = pattern.groupindex[name] - except KeyError: - raise IndexError, "unknown group name" - a((MARK, index)) - elif len(this) > 1 and this[1] in DIGITS: - code = None - while 1: - group = _group(this, pattern.groups+1) - if group: - if (not s.next or - not _group(this + s.next, pattern.groups+1)): - code = MARK, int(group) - break - elif s.next in OCTDIGITS: - this = this + s.get() - else: - break - if not code: - this = this[1:] - # FIXME: support unicode characters! - code = LITERAL, chr(int(this[-6:], 8) & 0xff) - a(code) - else: - try: - a(ESCAPES[this]) - except KeyError: - for c in this: - a((LITERAL, c)) - else: - a((LITERAL, this)) + this = s.get() + if this is None: + break # end of replacement string + if this and this[0] == "\\": + # group + if this == "\\g": + name = "" + if s.match("<"): + while 1: + char = s.get() + if char is None: + raise error, "unterminated group name" + if char == ">": + break + name = name + char + if not name: + raise error, "bad group name" + try: + index = int(name) + except ValueError: + if not isname(name): + raise error, "illegal character in group name" + try: + index = pattern.groupindex[name] + except KeyError: + raise IndexError, "unknown group name" + a((MARK, index)) + elif len(this) > 1 and this[1] in DIGITS: + code = None + while 1: + group = _group(this, pattern.groups+1) + if group: + if (not s.next or + not _group(this + s.next, pattern.groups+1)): + code = MARK, int(group) + break + elif s.next in OCTDIGITS: + this = this + s.get() + else: + break + if not code: + this = this[1:] + # FIXME: support unicode characters! + code = LITERAL, chr(int(this[-6:], 8) & 0xff) + a(code) + else: + try: + a(ESCAPES[this]) + except KeyError: + for c in this: + a((LITERAL, c)) + else: + a((LITERAL, this)) return p def expand_template(template, match): @@ -592,11 +592,11 @@ def expand_template(template, match): p = [] a = p.append for c, s in template: - if c is LITERAL: - a(s) - elif c is MARK: - s = match.group(s) - if s is None: - raise error, "empty group" - a(s) + if c is LITERAL: + a(s) + elif c is MARK: + s = match.group(s) + if s is None: + raise error, "empty group" + a(s) return match.string[:0].join(p) |