Experimental parser: some support for adding subraphs

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 70 matching lines @@
     self.__add_transition(TransitionKey.epsilon(), None, state)
 
   def is_closed(self):
     return self.__unclosed == None
 
   def close(self, end):
     assert not self.is_closed()
     unclosed, self.__unclosed = self.__unclosed, None
     action, self.__transition_action = self.__transition_action, None
     if end == None:
-      assert not unclosed
-      assert not action
+      assert not unclosed and not action
       return
     for key in unclosed:
       self.__add_transition(key, action, end)
     if not unclosed:
       self.__add_transition(TransitionKey.epsilon(), action, end)
 
   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())
 
@@ skipping 11 matching lines @@
     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 = {}
     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()
@@ skipping 64 matching lines @@
       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 __action(self, graph):
-    result = self.__process(graph[1])
-    for end in result[1]:
-      end.set_transition_action(graph[2])
-    return result
+    incoming = graph[3]
+    (start, ends) = self.__process(graph[1])
+    action = graph[2]
+    if incoming:
+      new_start = self.__new_state()
+      new_start.set_transition_action(action)
+      new_start.close(start)
+      start = new_start
+    else:
+      for end in ends:
+        end.set_transition_action(action)
+    return (start, ends)
 
   def __continue(self, graph):
     (start, ends) = self.__process(graph[1])
-    if not self.__start_node:
-      self.__start_node = self.__new_state()
+    state = self.__peek_state()
+    if not state['start_node']:
+      state['start_node'] = self.__new_state()
     end = self.__new_state()
     self.__patch_ends(ends, end)
     ends = [end]
-    end.add_epsilon_transition(self.__start_node)
+    end.add_epsilon_transition(state['start_node'])
     return (start, ends)
 
+  def __join(self, graph):
+    (graph, name, subgraph) = 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)
+    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 nfa(self, graph):
-    self.__start_node = None
+  def __push_state(self):
+    self.__states.append({
+      'start_node' : None,
+      'subgraphs' : {},
+    })
+
+  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)
-    if self.__start_node:
-      self.__start_node.close(start)
-      start = self.__start_node
+    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()
     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, self.__node_number - start_node_number)
+    return Nfa(start, end, nodes_created)
 
   @staticmethod
   def add_action(graph, action):
-    return ('ACTION', graph, action)
+    return ('ACTION', graph, action, False)
+
+  @staticmethod
+  def add_incoming_action(graph, action):
+    return ('ACTION', graph, action, True)
 
   @staticmethod
   def add_continue(graph):
     return ('CONTINUE', graph)
 
   @staticmethod
+  def join_subgraph(graph, name, subgraph):
+    return ('JOIN', graph, name, subgraph)
+
+  @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',
@@ skipping 95 matching lines @@
 
   def compute_dfa(self):
     self.__compute_epsilon_closures()
     dfa_nodes = {}
     start_name = self.__to_dfa(set([self.__start]), dfa_nodes, self.__end)
     return (start_name, dfa_nodes)
 
   def to_dot(self):
     iterator = lambda visitor, state: self.__visit_all_edges(visitor, state)
     return self.generate_dot(self.__start, set([self.__end]), iterator)