third_party/cython/src/Cython/Plex/Regexps.py

   1 #=======================================================================
   2 #
   3 #     Python Lexical Analyser
   4 #
   5 #     Regular Expressions
   6 #
   7 #=======================================================================
   8
   9 import types
  10 from sys import maxint as maxint
  11
  12 import Errors
  13
  14 #
  15 #     Constants
  16 #
  17
  18 BOL = 'bol'
  19 EOL = 'eol'
  20 EOF = 'eof'
  21
  22 nl_code = ord('\n')
  23
  24 #
  25 #     Helper functions
  26 #
  27
  28 def chars_to_ranges(s):
  29     """
  30     Return a list of character codes consisting of pairs
  31     [code1a, code1b, code2a, code2b,...] which cover all
  32     the characters in |s|.
  33     """
  34     char_list = list(s)
  35     char_list.sort()
  36     i = 0
  37     n = len(char_list)
  38     result = []
  39     while i < n:
  40         code1 = ord(char_list[i])
  41         code2 = code1 + 1
  42         i = i + 1
  43         while i < n and code2 >= ord(char_list[i]):
  44             code2 = code2 + 1
  45             i = i + 1
  46         result.append(code1)
  47         result.append(code2)
  48     return result
  49
  50 def uppercase_range(code1, code2):
  51     """
  52     If the range of characters from code1 to code2-1 includes any
  53     lower case letters, return the corresponding upper case range.
  54     """
  55     code3 = max(code1, ord('a'))
  56     code4 = min(code2, ord('z') + 1)
  57     if code3 < code4:
  58         d = ord('A') - ord('a')
  59         return (code3 + d, code4 + d)
  60     else:
  61         return None
  62
  63 def lowercase_range(code1, code2):
  64     """
  65     If the range of characters from code1 to code2-1 includes any
  66     upper case letters, return the corresponding lower case range.
  67     """
  68     code3 = max(code1, ord('A'))
  69     code4 = min(code2, ord('Z') + 1)
  70     if code3 < code4:
  71         d = ord('a') - ord('A')
  72         return (code3 + d, code4 + d)
  73     else:
  74         return None
  75
  76 def CodeRanges(code_list):
  77     """
  78     Given a list of codes as returned by chars_to_ranges, return
  79     an RE which will match a character in any of the ranges.
  80     """
  81     re_list = []
  82     for i in xrange(0, len(code_list), 2):
  83         re_list.append(CodeRange(code_list[i], code_list[i + 1]))
  84     return Alt(*re_list)
  85
  86 def CodeRange(code1, code2):
  87     """
  88     CodeRange(code1, code2) is an RE which matches any character
  89     with a code |c| in the range |code1| <= |c| < |code2|.
  90     """
  91     if code1 <= nl_code < code2:
  92         return Alt(RawCodeRange(code1, nl_code),
  93                              RawNewline,
  94                              RawCodeRange(nl_code + 1, code2))
  95     else:
  96         return RawCodeRange(code1, code2)
  97
  98 #
  99 #     Abstract classes
 100 #
 101
 102 class RE(object):
 103     """RE is the base class for regular expression constructors.
 104     The following operators are defined on REs:
 105
 106          re1 + re2         is an RE which matches |re1| followed by |re2|
 107          re1 | re2         is an RE which matches either |re1| or |re2|
 108     """
 109
 110     nullable = 1 # True if this RE can match 0 input symbols
 111     match_nl = 1 # True if this RE can match a string ending with '\n'
 112     str = None     # Set to a string to override the class's __str__ result
 113
 114     def build_machine(self, machine, initial_state, final_state,
 115                                         match_bol, nocase):
 116         """
 117         This method should add states to |machine| to implement this
 118         RE, starting at |initial_state| and ending at |final_state|.
 119         If |match_bol| is true, the RE must be able to match at the
 120         beginning of a line. If nocase is true, upper and lower case
 121         letters should be treated as equivalent.
 122         """
 123         raise NotImplementedError("%s.build_machine not implemented" %
 124             self.__class__.__name__)
 125
 126     def build_opt(self, m, initial_state, c):
 127         """
 128         Given a state |s| of machine |m|, return a new state
 129         reachable from |s| on character |c| or epsilon.
 130         """
 131         s = m.new_state()
 132         initial_state.link_to(s)
 133         initial_state.add_transition(c, s)
 134         return s
 135
 136     def __add__(self, other):
 137         return Seq(self, other)
 138
 139     def __or__(self, other):
 140         return Alt(self, other)
 141
 142     def __str__(self):
 143         if self.str:
 144             return self.str
 145         else:
 146             return self.calc_str()
 147
 148     def check_re(self, num, value):
 149         if not isinstance(value, RE):
 150             self.wrong_type(num, value, "Plex.RE instance")
 151
 152     def check_string(self, num, value):
 153         if type(value) != type(''):
 154             self.wrong_type(num, value, "string")
 155
 156     def check_char(self, num, value):
 157         self.check_string(num, value)
 158         if len(value) != 1:
 159             raise Errors.PlexValueError("Invalid value for argument %d of Plex.%s."
 160                 "Expected a string of length 1, got: %s" % (
 161                     num, self.__class__.__name__, repr(value)))
 162
 163     def wrong_type(self, num, value, expected):
 164         if type(value) == types.InstanceType:
 165                 got = "%s.%s instance" % (
 166                     value.__class__.__module__, value.__class__.__name__)
 167         else:
 168             got = type(value).__name__
 169         raise Errors.PlexTypeError("Invalid type for argument %d of Plex.%s "
 170                                         "(expected %s, got %s" % (
 171                                             num, self.__class__.__name__, expected, got))
 172
 173 #
 174 #     Primitive RE constructors
 175 #     -------------------------
 176 #
 177 #     These are the basic REs from which all others are built.
 178 #
 179
 180 ## class Char(RE):
 181 ##     """
 182 ##     Char(c) is an RE which matches the character |c|.
 183 ##     """
 184
 185 ##     nullable = 0
 186
 187 ##     def __init__(self, char):
 188 ##         self.char = char
 189 ##         self.match_nl = char == '\n'
 190
 191 ##     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 192 ##         c = self.char
 193 ##         if match_bol and c != BOL:
 194 ##             s1 = self.build_opt(m, initial_state, BOL)
 195 ##         else:
 196 ##             s1 = initial_state
 197 ##         if c == '\n' or c == EOF:
 198 ##             s1 = self.build_opt(m, s1, EOL)
 199 ##         if len(c) == 1:
 200 ##             code = ord(self.char)
 201 ##             s1.add_transition((code, code+1), final_state)
 202 ##             if nocase and is_letter_code(code):
 203 ##                 code2 = other_case_code(code)
 204 ##                 s1.add_transition((code2, code2+1), final_state)
 205 ##         else:
 206 ##             s1.add_transition(c, final_state)
 207
 208 ##     def calc_str(self):
 209 ##         return "Char(%s)" % repr(self.char)
 210
 211 def Char(c):
 212     """
 213     Char(c) is an RE which matches the character |c|.
 214     """
 215     if len(c) == 1:
 216         result = CodeRange(ord(c), ord(c) + 1)
 217     else:
 218         result = SpecialSymbol(c)
 219     result.str = "Char(%s)" % repr(c)
 220     return result
 221
 222 class RawCodeRange(RE):
 223     """
 224     RawCodeRange(code1, code2) is a low-level RE which matches any character
 225     with a code |c| in the range |code1| <= |c| < |code2|, where the range
 226     does not include newline. For internal use only.
 227     """
 228     nullable = 0
 229     match_nl = 0
 230     range = None                     # (code, code)
 231     uppercase_range = None # (code, code) or None
 232     lowercase_range = None # (code, code) or None
 233
 234     def __init__(self, code1, code2):
 235         self.range = (code1, code2)
 236         self.uppercase_range = uppercase_range(code1, code2)
 237         self.lowercase_range = lowercase_range(code1, code2)
 238
 239     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 240         if match_bol:
 241             initial_state = self.build_opt(m, initial_state, BOL)
 242         initial_state.add_transition(self.range, final_state)
 243         if nocase:
 244             if self.uppercase_range:
 245                 initial_state.add_transition(self.uppercase_range, final_state)
 246             if self.lowercase_range:
 247                 initial_state.add_transition(self.lowercase_range, final_state)
 248
 249     def calc_str(self):
 250         return "CodeRange(%d,%d)" % (self.code1, self.code2)
 251
 252 class _RawNewline(RE):
 253     """
 254     RawNewline is a low-level RE which matches a newline character.
 255     For internal use only.
 256     """
 257     nullable = 0
 258     match_nl = 1
 259
 260     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 261         if match_bol:
 262             initial_state = self.build_opt(m, initial_state, BOL)
 263         s = self.build_opt(m, initial_state, EOL)
 264         s.add_transition((nl_code, nl_code + 1), final_state)
 265
 266 RawNewline = _RawNewline()
 267
 268
 269 class SpecialSymbol(RE):
 270     """
 271     SpecialSymbol(sym) is an RE which matches the special input
 272     symbol |sym|, which is one of BOL, EOL or EOF.
 273     """
 274     nullable = 0
 275     match_nl = 0
 276     sym = None
 277
 278     def __init__(self, sym):
 279         self.sym = sym
 280
 281     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 282         # Sequences 'bol bol' and 'bol eof' are impossible, so only need
 283         # to allow for bol if sym is eol
 284         if match_bol and self.sym == EOL:
 285             initial_state = self.build_opt(m, initial_state, BOL)
 286         initial_state.add_transition(self.sym, final_state)
 287
 288
 289 class Seq(RE):
 290     """Seq(re1, re2, re3...) is an RE which matches |re1| followed by
 291     |re2| followed by |re3|..."""
 292
 293     def __init__(self, *re_list):
 294         nullable = 1
 295         for i in xrange(len(re_list)):
 296             re = re_list[i]
 297             self.check_re(i, re)
 298             nullable = nullable and re.nullable
 299         self.re_list = re_list
 300         self.nullable = nullable
 301         i = len(re_list)
 302         match_nl = 0
 303         while i:
 304             i = i - 1
 305             re = re_list[i]
 306             if re.match_nl:
 307                 match_nl = 1
 308                 break
 309             if not re.nullable:
 310                 break
 311         self.match_nl = match_nl
 312
 313     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 314         re_list = self.re_list
 315         if len(re_list) == 0:
 316             initial_state.link_to(final_state)
 317         else:
 318             s1 = initial_state
 319             n = len(re_list)
 320             for i in xrange(n):
 321                 if i < n - 1:
 322                     s2 = m.new_state()
 323                 else:
 324                     s2 = final_state
 325                 re = re_list[i]
 326                 re.build_machine(m, s1, s2, match_bol, nocase)
 327                 s1 = s2
 328                 match_bol = re.match_nl or (match_bol and re.nullable)
 329
 330     def calc_str(self):
 331         return "Seq(%s)" % ','.join(map(str, self.re_list))
 332
 333
 334 class Alt(RE):
 335     """Alt(re1, re2, re3...) is an RE which matches either |re1| or
 336     |re2| or |re3|..."""
 337
 338     def __init__(self, *re_list):
 339         self.re_list = re_list
 340         nullable = 0
 341         match_nl = 0
 342         nullable_res = []
 343         non_nullable_res = []
 344         i = 1
 345         for re in re_list:
 346             self.check_re(i, re)
 347             if re.nullable:
 348                 nullable_res.append(re)
 349                 nullable = 1
 350             else:
 351                 non_nullable_res.append(re)
 352             if re.match_nl:
 353                 match_nl = 1
 354             i = i + 1
 355         self.nullable_res = nullable_res
 356         self.non_nullable_res = non_nullable_res
 357         self.nullable = nullable
 358         self.match_nl = match_nl
 359
 360     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 361         for re in self.nullable_res:
 362             re.build_machine(m, initial_state, final_state, match_bol, nocase)
 363         if self.non_nullable_res:
 364             if match_bol:
 365                 initial_state = self.build_opt(m, initial_state, BOL)
 366             for re in self.non_nullable_res:
 367                 re.build_machine(m, initial_state, final_state, 0, nocase)
 368
 369     def calc_str(self):
 370         return "Alt(%s)" % ','.join(map(str, self.re_list))
 371
 372
 373 class Rep1(RE):
 374     """Rep1(re) is an RE which matches one or more repetitions of |re|."""
 375
 376     def __init__(self, re):
 377         self.check_re(1, re)
 378         self.re = re
 379         self.nullable = re.nullable
 380         self.match_nl = re.match_nl
 381
 382     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 383         s1 = m.new_state()
 384         s2 = m.new_state()
 385         initial_state.link_to(s1)
 386         self.re.build_machine(m, s1, s2, match_bol or self.re.match_nl, nocase)
 387         s2.link_to(s1)
 388         s2.link_to(final_state)
 389
 390     def calc_str(self):
 391         return "Rep1(%s)" % self.re
 392
 393
 394 class SwitchCase(RE):
 395     """
 396     SwitchCase(re, nocase) is an RE which matches the same strings as RE,
 397     but treating upper and lower case letters according to |nocase|. If
 398     |nocase| is true, case is ignored, otherwise it is not.
 399     """
 400     re = None
 401     nocase = None
 402
 403     def __init__(self, re, nocase):
 404         self.re = re
 405         self.nocase = nocase
 406         self.nullable = re.nullable
 407         self.match_nl = re.match_nl
 408
 409     def build_machine(self, m, initial_state, final_state, match_bol, nocase):
 410         self.re.build_machine(m, initial_state, final_state, match_bol,
 411                                                     self.nocase)
 412
 413     def calc_str(self):
 414         if self.nocase:
 415             name = "NoCase"
 416         else:
 417             name = "Case"
 418         return "%s(%s)" % (name, self.re)
 419
 420 #
 421 #     Composite RE constructors
 422 #     -------------------------
 423 #
 424 #     These REs are defined in terms of the primitive REs.
 425 #
 426
 427 Empty = Seq()
 428 Empty.__doc__ = \
 429     """
 430     Empty is an RE which matches the empty string.
 431     """
 432 Empty.str = "Empty"
 433
 434 def Str1(s):
 435     """
 436     Str1(s) is an RE which matches the literal string |s|.
 437     """
 438     result = Seq(*tuple(map(Char, s)))
 439     result.str = "Str(%s)" % repr(s)
 440     return result
 441
 442 def Str(*strs):
 443     """
 444     Str(s) is an RE which matches the literal string |s|.
 445     Str(s1, s2, s3, ...) is an RE which matches any of |s1| or |s2| or |s3|...
 446     """
 447     if len(strs) == 1:
 448         return Str1(strs[0])
 449     else:
 450         result = Alt(*tuple(map(Str1, strs)))
 451         result.str = "Str(%s)" % ','.join(map(repr, strs))
 452         return result
 453
 454 def Any(s):
 455     """
 456     Any(s) is an RE which matches any character in the string |s|.
 457     """
 458     #result = apply(Alt, tuple(map(Char, s)))
 459     result = CodeRanges(chars_to_ranges(s))
 460     result.str = "Any(%s)" % repr(s)
 461     return result
 462
 463 def AnyBut(s):
 464     """
 465     AnyBut(s) is an RE which matches any character (including
 466     newline) which is not in the string |s|.
 467     """
 468     ranges = chars_to_ranges(s)
 469     ranges.insert(0, -maxint)
 470     ranges.append(maxint)
 471     result = CodeRanges(ranges)
 472     result.str = "AnyBut(%s)" % repr(s)
 473     return result
 474
 475 AnyChar = AnyBut("")
 476 AnyChar.__doc__ = \
 477     """
 478     AnyChar is an RE which matches any single character (including a newline).
 479     """
 480 AnyChar.str = "AnyChar"
 481
 482 def Range(s1, s2 = None):
 483     """
 484     Range(c1, c2) is an RE which matches any single character in the range
 485     |c1| to |c2| inclusive.
 486     Range(s) where |s| is a string of even length is an RE which matches
 487     any single character in the ranges |s[0]| to |s[1]|, |s[2]| to |s[3]|,...
 488     """
 489     if s2:
 490         result = CodeRange(ord(s1), ord(s2) + 1)
 491         result.str = "Range(%s,%s)" % (s1, s2)
 492     else:
 493         ranges = []
 494         for i in range(0, len(s1), 2):
 495             ranges.append(CodeRange(ord(s1[i]), ord(s1[i+1]) + 1))
 496         result = Alt(*ranges)
 497         result.str = "Range(%s)" % repr(s1)
 498     return result
 499
 500 def Opt(re):
 501     """
 502     Opt(re) is an RE which matches either |re| or the empty string.
 503     """
 504     result = Alt(re, Empty)
 505     result.str = "Opt(%s)" % re
 506     return result
 507
 508 def Rep(re):
 509     """
 510     Rep(re) is an RE which matches zero or more repetitions of |re|.
 511     """
 512     result = Opt(Rep1(re))
 513     result.str = "Rep(%s)" % re
 514     return result
 515
 516 def NoCase(re):
 517     """
 518     NoCase(re) is an RE which matches the same strings as RE, but treating
 519     upper and lower case letters as equivalent.
 520     """
 521     return SwitchCase(re, nocase = 1)
 522
 523 def Case(re):
 524     """
 525     Case(re) is an RE which matches the same strings as RE, but treating
 526     upper and lower case letters as distinct, i.e. it cancels the effect
 527     of any enclosing NoCase().
 528     """
 529     return SwitchCase(re, nocase = 0)
 530
 531 #
 532 #     RE Constants
 533 #
 534
 535 Bol = Char(BOL)
 536 Bol.__doc__ = \
 537     """
 538     Bol is an RE which matches the beginning of a line.
 539     """
 540 Bol.str = "Bol"
 541
 542 Eol = Char(EOL)
 543 Eol.__doc__ = \
 544     """
 545     Eol is an RE which matches the end of a line.
 546     """
 547 Eol.str = "Eol"
 548
 549 Eof = Char(EOF)
 550 Eof.__doc__ = \
 551     """
 552     Eof is an RE which matches the end of the file.
 553     """
 554 Eof.str = "Eof"
 555