Experimental parser: split out NfaBuilder

tools/lexer_generator/nfa.py

Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index cbc9a9f301334fa0803708be70a5acd1fb98bed9..bb60ef174876582811a43cb4d72f2f7d5da3385b 100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -25,10 +25,8 @@
 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
-from types import TupleType
 from transition_keys import TransitionKey
 from automaton import *
-from inspect import getmembers
 
 class NfaState(AutomatonState):
 
@@ -128,227 +126,6 @@ class NfaState(AutomatonState):
     keys.discard(TransitionKey.epsilon())
     return TransitionKey.disjoint_keys(keys)
 
-class NfaBuilder:
-
-  def __init__(self):
-    self.__node_number = 0
-    self.__operation_map = {}
-    self.__members = getmembers(self)
-    self.__character_classes = {}
-    self.__states = []
-
-  def set_character_classes(self, classes):
-    self.__character_classes = classes
-
-  def __new_state(self):
-    self.__node_number += 1
-    return NfaState(self.__node_number - 1)
-
-  def __or(self, graph):
-    start = self.__new_state()
-    ends = []
-    for x in [self.__process(graph[1]), self.__process(graph[2])]:
-      start.add_epsilon_transition(x[0])
-      ends += x[1]
-    start.close(None)
-    return (start, ends)
-
-  def __one_or_more(self, graph):
-    (start, ends) = self.__process(graph[1])
-    end =  self.__new_state()
-    end.add_epsilon_transition(start)
-    self.__patch_ends(ends, end)
-    return (start, [end])
-
-  def __zero_or_more(self, graph):
-    (node, ends) = self.__process(graph[1])
-    start =  self.__new_state()
-    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])
-
-  def __literal(self, graph):
-    return self.__key_state(TransitionKey.single_char(graph[1]))
-
-  def __class(self, graph):
-    return self.__key_state(
-      TransitionKey.character_class(graph, self.__character_classes))
-
-  def __not_class(self, graph):
-    return self.__key_state(
-      TransitionKey.character_class(graph, self.__character_classes))
-
-  def __any(self, graph):
-    return self.__key_state(TransitionKey.any())
-
-  def __epsilon(self, graph):
-    start = self.__new_state()
-    end = self.__new_state()
-    start.close(end)
-    return (start, [end])
-
-  def __action(self, graph):
-    (start, ends) = self.__process(graph[1])
-    action = graph[2]
-    end = self.__new_state()
-    self.__patch_ends(ends, end)
-    end.set_action(action)
-    return (start, [end])
-
-  def __continue(self, graph):
-    (start, ends) = self.__process(graph[1])
-    state = self.__peek_state()
-    if not state['start_node']:
-      state['start_node'] = self.__new_state()
-    self.__patch_ends(ends, state['start_node'])
-    return (start, [])
-
-  def __catch_all(self, graph):
-    return self.__key_state(TransitionKey.unique('catch_all'))
-
-  def __join(self, graph):
-    (graph, name, subgraph, modifier) = graph[1:]
-    subgraphs = self.__peek_state()['subgraphs']
-    if not name in subgraphs:
-      subgraphs[name] = self.__nfa(subgraph)
-    (subgraph_start, subgraph_end, nodes_in_subgraph) = subgraphs[name]
-    (start, ends) = self.__process(graph)
-    if modifier:
-      assert modifier == 'ZERO_OR_MORE'
-      for end in ends:
-        end.add_epsilon_transition(subgraph_end)
-    self.__patch_ends(ends, subgraph_start)
-    end = self.__new_state()
-    subgraph_end.add_epsilon_transition(end)
-    return (start, [end])
-
-  def __process(self, graph):
-    assert type(graph) == TupleType
-    method = "_NfaBuilder__" + graph[0].lower()
-    if not method in self.__operation_map:
-      matches = filter(lambda (name, func): name == method, self.__members)
-      assert len(matches) == 1
-      self.__operation_map[method] = matches[0][1]
-    return self.__operation_map[method](graph)
-
-  def __patch_ends(self, ends, new_end):
-    for end in ends:
-      end.close(new_end)
-
-  def __push_state(self):
-    self.__states.append({
-      'start_node' : None,
-      'subgraphs' : {},
-      'unpatched_ends' : [],
-    })
-
-  def __pop_state(self):
-    return self.__states.pop()
-
-  def __peek_state(self):
-    return self.__states[len(self.__states) - 1]
-
-  def __nfa(self, graph):
-    start_node_number = self.__node_number
-    self.__push_state()
-    (start, ends) = self.__process(graph)
-    state = self.__pop_state()
-    if state['start_node']:
-      state['start_node'].close(start)
-      start = state['start_node']
-    for k, subgraph in state['subgraphs'].items():
-      subgraph[1].close(None)
-    end =  self.__new_state()
-    if self.__states:
-      self.__peek_state()['unpatched_ends'] += state['unpatched_ends']
-    else:
-      self.__patch_ends(state['unpatched_ends'], end)
-    self.__patch_ends(ends, end)
-    return (start, end, self.__node_number - start_node_number)
-
-  def nfa(self, graph):
-    (start, end, nodes_created) = self.__nfa(graph)
-    end.close(None)
-    return Nfa(start, end, nodes_created)
-
-  @staticmethod
-  def add_action(graph, action):
-    return ('ACTION', graph, action)
-
-  @staticmethod
-  def add_continue(graph):
-    return ('CONTINUE', graph)
-
-  @staticmethod
-  def catch_all():
-    return ('CATCH_ALL',)
-
-  @staticmethod
-  def epsilon():
-    return ('EPSILON',)
-
-  @staticmethod
-  def join_subgraph(graph, name, subgraph, modifier):
-    if modifier:
-      modifier = NfaBuilder.__modifer_map[modifier]
-    return ('JOIN', graph, name, subgraph, modifier)
-
-  @staticmethod
-  def or_graphs(graphs):
-    return reduce(lambda acc, g: ('OR', acc, g), graphs)
-
-  @staticmethod
-  def cat_graphs(graphs):
-    return reduce(lambda acc, g: ('CAT', acc, g), graphs)
-
-  __modifer_map = {
-    '+': 'ONE_OR_MORE',
-    '?': 'ZERO_OR_ONE',
-    '*': 'ZERO_OR_MORE',
-  }
-
-  @staticmethod
-  def apply_modifier(modifier, graph):
-    return (NfaBuilder.__modifer_map[modifier], graph)
-
 class Nfa(Automaton):
 
   def __init__(self, start, end, nodes_created):