Experimental lexer generator: parse {} in regexps.

tools/lexer_generator/nfa.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 90 matching lines @@
   def __matches(self, match_func, value):
     f = lambda acc, (k, vs): acc | vs if match_func(k, value) else acc
     return reduce(f, self.__transitions.items(), set())
 
   def char_matches(self, value):
     return self.__matches(lambda k, v : k.matches_char(v), value)
 
   def key_matches(self, value):
     return self.__matches(lambda k, v : k.matches_key(v), value)
 
+  def __str__(self):
+    return "NfaState(" + str(self.__node_number) + ")"
+
   @staticmethod
   def gather_transition_keys(state_set):
     f = lambda acc, state: acc | set(state.__transitions.keys())
     return TransitionKey.disjoint_keys(reduce(f, state_set, set()))
 
 class NfaBuilder:
 
   def __init__(self):
     self.__node_number = 0
     self.__operation_map = {}
@@ skipping 25 matching lines @@
     start.add_epsilon_transition(node)
     self.__patch_ends(ends, start)
     return (start, [start])
 
   def __zero_or_one(self, graph):
     (node, ends) = self.__process(graph[1])
     start =  self.__new_state()
     start.add_epsilon_transition(node)
     return (start, ends + [start])
 
+  def __repeat(self, graph):
+    param_min = int(graph[1])
+    param_max = int(graph[2])
+    subgraph = graph[3]
+    (start, ends) = self.__process(subgraph)
+    for i in xrange(1, param_min):
+      (start2, ends2) = self.__process(subgraph)
+      self.__patch_ends(ends, start2)
+      ends = ends2
+    if param_min == param_max:
+      return (start, ends)
+
+    midpoints = []
+    for i in xrange(param_min, param_max):
+      midpoint =  self.__new_state()
+      self.__patch_ends(ends, midpoint)
+      (start2, ends) = self.__process(subgraph)
+      midpoint.add_epsilon_transition(start2)
+      midpoints.append(midpoint)
+
+    return (start, ends + midpoints)
+
   def __cat(self, graph):
     (left, right) = (self.__process(graph[1]), self.__process(graph[2]))
     self.__patch_ends(left[1], right[0])
     return (left[0], right[1])
 
   def __key_state(self, key):
     state =  self.__new_state()
     state.add_unclosed_transition(key)
     return (state, [state])
 
@@ skipping 172 matching lines @@
 digraph finite_state_machine {
   rankdir=LR;
   node [shape = circle, style=filled, bgcolor=lightgrey]; S_%s
   node [shape = doublecircle, style=unfilled]; S_%s
   node [shape = circle];
 %s
 }
     ''' % (self.__start.node_number(),
            self.__end.node_number(),
            "\n".join(node_content))