Experimental parser: add catch all rule

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 88 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 replace_catch_all(self):
+    catch_all = TransitionKey.unique('catch_all')
+    if not catch_all in self.__transitions:
+      return
+    f = lambda acc, state: acc | state.__epsilon_closure
+    reachable_states = reduce(f, self.__transitions[catch_all], set())
+    f = lambda acc, state: acc | set(state.__transitions.keys())
+    keys = reduce(f, reachable_states, set())
+    keys.discard(TransitionKey.epsilon())
+    keys.discard(catch_all)
+    inverse_key = TransitionKey.inverse_key(keys)
+    if inverse_key:
+      self.__transitions[inverse_key] = self.__transitions[catch_all]
+    del self.__transitions[catch_all]
+
   @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()))
+    keys = reduce(f, state_set, set())
+    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 = []
 
@@ skipping 72 matching lines @@
     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()
-    end = self.__new_state()
-    self.__patch_ends(ends, end)
-    ends = [end]
-    end.add_epsilon_transition(state['start_node'])
-    return (start, ends)
+    self.__patch_ends(ends, state['start_node'])
+    return (start, [])
 
-  def __break(self, graph):
-    (start, ends) = self.__process(graph[1])
-    self.__peek_state()['unpatched_ends'] += ends
-    new_end = self.__new_state()
-    for end in ends:
-      end.add_epsilon_transition(new_end)
-    return (start, [new_end])
+  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'
@@ skipping 55 matching lines @@
 
   @staticmethod
   def add_action(graph, action):
     return ('ACTION', graph, action)
 
   @staticmethod
   def add_continue(graph):
     return ('CONTINUE', graph)
 
   @staticmethod
-  def add_break(graph):
-    return ('BREAK', graph)
+  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)
@@ skipping 88 matching lines @@
       match_states = set()
       f = lambda acc, state: acc | state.key_matches(key)
       for state in reduce(f, nfa_state_set, set()):
         match_states.add(state)
       transition_state = Nfa.__to_dfa(match_states, dfa_nodes, end_node)
       dfa_nodes[name]['transitions'][key] = transition_state
     return name
 
   def compute_dfa(self):
     self.__compute_epsilon_closures()
+    self.__visit_all_edges(lambda node, state: node.replace_catch_all(), None)
     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)
     state_iterator = lambda x : x
     return self.generate_dot(self.__start, set([self.__end]), iterator, state_iterator)