Experimental parser: add catch all rule

tools/lexer_generator/transition_keys.py

 # Copyright 2013 the V8 project authors. All rights reserved.
 # Redistribution and use in source and binary forms, with or without
 # modification, are permitted provided that the following conditions are
 # met:
 #
 #     * Redistributions of source code must retain the above copyright
 #       notice, this list of conditions and the following disclaimer.
 #     * Redistributions in binary form must reproduce the above
 #       copyright notice, this list of conditions and the following
 #       disclaimer in the documentation and/or other materials provided
@@ skipping 24 matching lines @@
     "literal" : (257, 257),
   }
   __lower_bound = 0
   __upper_bound = reduce(lambda acc, (k, v): max(acc, v[1]), __class_bounds.items(), 0)
 
   __cached_keys = {}
 
   __unique_key_counter = -1
 
   @staticmethod
+  def alphabet_iter():
+    for k, (lower, upper) in TransitionKey.__class_bounds.items():
+      for i in range(lower, upper + 1):
+        yield i
+
+  @staticmethod
   def __in_latin_1(char):
     bound = TransitionKey.__class_bounds["latin_1"]
     return (bound[0] <= char and char <= bound[1])
 
   @staticmethod
   def __is_class_range(r):
     return r[0] == r[1] and not TransitionKey.__in_latin_1(r[0])
 
   @staticmethod
   def __is_unique_range(r):
@@ skipping 24 matching lines @@
       assert name == 'epsilon'
       assert not name in TransitionKey.__cached_keys
     else:
       TransitionKey.__verify_ranges(ranges, True)
     key = TransitionKey()
     key.__ranges = tuple(ranges) # immutable
     key.__name = name
     key.__cached_hash = None
     return key
 
+  def __is_unique(self):
+    return len(self.__ranges) == 1 and self.__is_unique_range(self.__ranges[0])
+
   @staticmethod
   def __cached_key(name, bounds_getter):
     if not name in TransitionKey.__cached_keys:
       bounds = bounds_getter(name)
       TransitionKey.__cached_keys[name] = TransitionKey.__create(bounds, name)
     return TransitionKey.__cached_keys[name]
 
   @staticmethod
   def epsilon():
     return TransitionKey.__cached_key("epsilon", lambda name : [])
 
   @staticmethod
   def any():
     return TransitionKey.__cached_key("any",
       lambda name : TransitionKey.__class_bounds.values())
 
   @staticmethod
   def single_char(char):
     char = ord(char)
     assert TransitionKey.__in_latin_1(char)
     return TransitionKey.__create([(char, char)])
 
   @staticmethod
-  def unique_key(name):
+  def unique(name):
     def get_bounds(name):
       bound = TransitionKey.__unique_key_counter
       TransitionKey.__unique_key_counter -= 1
       return [(bound, bound)]
     name = "__" + name
     return TransitionKey.__cached_key(name, get_bounds)
 
   @staticmethod
   def __process_graph(graph, ranges, key_map):
     key = graph[0]
@@ skipping 112 matching lines @@
           to_push.append(v)
         else:
           ranges.append((left, v))
           left = v + 1
       if to_push:
         current = range_map[i + 1]
         range_map[i + 1] = (current[0], sort(current[1] + to_push))
     return ranges
 
   @staticmethod
-  def disjoint_keys(key_set):
-    key_set.discard(TransitionKey.epsilon())
+  def __disjoint_ranges_from_key_set(key_set):
     if not key_set:
       return []
     range_map = {}
     for x in key_set:
+      assert not x.__is_unique()
+      assert x != TransitionKey.epsilon
       for r in x.__ranges:
         if not r[0] in range_map:
           range_map[r[0]] = []
         range_map[r[0]].append(r[1])
     ranges = TransitionKey.__disjoint_keys(range_map)
     TransitionKey.__verify_ranges(ranges, False)
+    return ranges
+
+  @staticmethod
+  def disjoint_keys(key_set):
+    ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
     return map(lambda x : TransitionKey.__create([x]), ranges)
 
   @staticmethod
+  def inverse_key(key_set):
+    ranges = TransitionKey.__disjoint_ranges_from_key_set(key_set)
+    inverse = TransitionKey.__invert_ranges(ranges)
+    if not inverse:
+      return None
+    return TransitionKey.__create(inverse)
+
+  @staticmethod
   def __key_from_ranges(invert, ranges):
     range_map = {}
     for r in ranges:
       if not r[0] in range_map:
         range_map[r[0]] = []
       range_map[r[0]].append(r[1])
     ranges = TransitionKey.__disjoint_keys(range_map)
     ranges = TransitionKey.__merge_ranges(ranges)
     if invert:
       ranges = TransitionKey.__invert_ranges(ranges)
@@ skipping 19 matching lines @@
   @staticmethod
   def merged_key(keys):
     f = lambda acc, key: acc + list(key.__ranges)
     return TransitionKey.__key_from_ranges(False, reduce(f, keys, []))
 
   @staticmethod
   def __invert_ranges(ranges):
     inverted = []
     last = None
     classes = set(TransitionKey.__class_bounds.values())
-    classes.remove(TransitionKey.__class_bounds["latin_1"])
+    latin_1 = TransitionKey.__class_bounds["latin_1"]
+    classes.remove(latin_1)
     for r in ranges:
       assert not TransitionKey.__is_unique_range(r)
       if TransitionKey.__is_class_range(r):
         classes.remove(r)
         continue
       if last == None:
         if r[0] != TransitionKey.__lower_bound:
           inverted.append((TransitionKey.__lower_bound, r[0] - 1))
       elif last[1] + 1 < r[0]:
         inverted.append((last[1] + 1, r[0] - 1))
       last = r
-    upper_bound = TransitionKey.__class_bounds["latin_1"][1]
-    if last != None and last[1] < upper_bound:
+    upper_bound = latin_1[1]
+    if last == None:
+      inverted.append(latin_1)
+    elif last[1] < upper_bound:
       inverted.append((last[1] + 1, upper_bound))
     inverted += list(classes)
     return inverted