Experimental parser: subclass for common code

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
 #       with the distribution.
 #     * Neither the name of Google Inc. nor the names of its
 #       contributors may be used to endorse or promote products derived
 #       from this software without specific prior written permission.
 #
 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 # (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:
+class NfaState(AutomatonState):
 
   def __init__(self, node_number):
+    super(NfaState, self).__init__(node_number)
     self.__transitions = {}
     self.__unclosed = set()
-    self.__node_number = node_number
     self.__epsilon_closure = None
     self.__transition_action = None
 
-  def node_number(self):
-    return self.__node_number
-
   def epsilon_closure(self):
     return self.__epsilon_closure
 
   def set_epsilon_closure(self, closure):
     assert self.is_closed()
     assert self.__epsilon_closure == None
     self.__epsilon_closure = frozenset(closure)
 
   def set_transition_action(self, action):
     assert not self.is_closed()
@@ skipping 48 matching lines @@
     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) + ")"
+    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
@@ skipping 125 matching lines @@
   __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:
+class Nfa(Automaton):
 
   def __init__(self, start, end, nodes_created):
+    super(Nfa, self).__init__()
     self.__start = start
     self.__end = end
     self.__epsilon_closure_computed = False
     self.__verify(nodes_created)
 
-  @staticmethod
-  def __visit_edges(edge, compute_next_edge, visitor, state):
-    visited = set()
-    while edge:
-      f = lambda (next_edge, state), node: (
-        next_edge | compute_next_edge(node),
-        visitor(node, state))
-      (next_edge, state) = reduce(f, edge, (set(), state))
-      visited |= edge
-      edge = next_edge - visited
-    return state
-
   def __visit_all_edges(self, visitor, state):
     edge = set([self.__start])
     next_edge = lambda node: node.next_states(lambda x : True)
-    return Nfa.__visit_edges(edge, next_edge, visitor, state)
+    return self.visit_edges(edge, next_edge, visitor, state)
 
   def __verify(self, nodes_created):
     def f(node, node_list):
       assert node.is_closed()
       node_list.append(node)
       return node_list
     node_list = self.__visit_all_edges(f, [])
     assert len(node_list) == nodes_created
 
   def __compute_epsilon_closures(self):
     if self.__epsilon_closure_computed:
       return
     self.__epsilon_closure_computed = True
     def outer(node, state):
       def inner(node, closure):
         closure.add(node)
         return closure
       is_epsilon = lambda k: k == TransitionKey.epsilon()
       next_edge = lambda node : node.next_states(is_epsilon)
       edge = next_edge(node)
-      closure = Nfa.__visit_edges(edge, next_edge, inner, set())
+      closure = self.visit_edges(edge, next_edge, inner, set())
       node.set_epsilon_closure(closure)
     self.__visit_all_edges(outer, None)
 
   @staticmethod
   def __close(states):
     f = lambda acc, node: acc | node.epsilon_closure()
     return reduce(f, states, set(states))
 
   def matches(self, string):
     self.__compute_epsilon_closures()
@@ skipping 42 matching lines @@
       dfa_nodes[name]['transitions'][key] = (transition_state, action)
     return name
 
   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):
-
-    def f(node, node_content):
-      for key, values in node.transitions().items():
-        if key == TransitionKey.epsilon():
-          key = "ε"
-        key = str(key).replace('\\', '\\\\')
-        for value in values:
-          if value[1]:
-            node_content.append(
-                "  S_%d -> S_%d [ label = \"%s {%s} -> %s\" ];" %
-                (node.node_number(), value[0].node_number(), key, value[1][1],
-                 value[1][2]))
-          else:
-            node_content.append(
-                "  S_%d -> S_%d [ label = \"%s\" ];" %
-                (node.node_number(), value[0].node_number(), key))
-      return node_content
-
-    node_content = self.__visit_all_edges(f, [])
-
-    return '''
-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))
+    iterator = lambda visitor, state: self.__visit_all_edges(visitor, state)
+    return self.generate_dot(self.__start, set([self.__end]), iterator)