Experimental parser: dump minimal dfa into html

tools/lexer_generator/dfa.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 225 matching lines @@
             s = self.__find_partition(partitions, s.node_number())
           if first:
             first = False
             mapped_partition = s
           assert mapped_partition == s
 
   @staticmethod
   def __partition_count(partitions):
     return len(reduce(lambda acc, p: acc | p.set(), partitions, set()))
 
+  def __merge_partitions(self, id_map, partitions):
+    mapping = {}
+    name_map = {}
+    for partition in partitions:
+      name_map[partition] = str(partition)
+    alphabet = self.__generate_alphabet()
+    for partition in partitions:
+      state_id = iter(partition).next()
+      state = id_map[state_id]
+      node = {
+        'transitions' : {},
+        'terminal' : state in self.__dfa.terminal_set(),
+        'action' : state.action(),
+      }
+      mapping[str(partition)] = node
+      for key in alphabet:
+        transition_state = state.key_matches(key)
+        if not transition_state:
+          continue
+        transition_id = transition_state.node_number()
+        transition_partition = self.__find_partition(partitions, transition_id)
+        assert transition_partition
+        node['transitions'][key] = name_map[transition_partition]
+    start_id = self.__dfa.start_state().node_number()
+    start_name = name_map[self.__find_partition(partitions, start_id)]
+    return (start_name, mapping)
+
   def minimize(self):
     (id_map, partitions) = self.__partition()
     node_count = self.__dfa.node_count()
     assert self.__partition_count(partitions) == node_count
     if len(partitions) == 1:
       return self.__dfa
     working_set = set(partitions)
     alphabet = self.__generate_alphabet()
     all_state_ids = set(id_map.keys())
     while working_set:
@@ skipping 31 matching lines @@
             working_set.add(intersection)
             working_set.add(difference)
           elif len(intersection) <= len(difference):
             working_set.add(intersection)
           else:
             working_set.add(difference)
         partitions = new_partitions
     self.__verify_partitions(id_map, partitions)
     if len(partitions) == len(id_map):
       return self.__dfa
-    # merge partitions
+    (start_name, mapping) = self.__merge_partitions(id_map, partitions)
+    return Dfa(start_name, mapping)