Experimental parser: always apply default transitions

tools/lexer_generator/dfa_optimizer.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 149 matching lines @@
     incoming_transitions = {}
     def f(state, visitor_state):
       for key, transition_state in state.key_state_iter():
         if not transition_state in incoming_transitions:
           incoming_transitions[transition_state] = []
         incoming_transitions[transition_state].append((key, state))
     dfa.visit_all_states(f)
     return incoming_transitions
 
   @staticmethod
-  def __match_action(state):
-    state = state.omega_transition()
-    state = state if state and state.transition_count() == 0 else None
-    return Action.empty_action() if not state else state.action()
-
-  @staticmethod
   def __build_replacement_map(dfa):
     replacements = {}
     encoding = dfa.encoding()
     incoming_transitions = DfaOptimizer.__build_incoming_transitions(dfa)
     replacement_targets = set([])
     # TODO(dcarney): this should be an ordered walk
     for state, incoming in incoming_transitions.items():
       if len(incoming) < 10:
         continue
       # the states action will be replaced, so we just don't optimize if there
       # is one
       if state.action():  # TODO(dcarney): allow this via action chaining
         continue
       # We only perform this optimization on 'token' actions
-      match_action = DfaOptimizer.__match_action(state)
+      match_action = state.match_action()
       if not match_action.name() == 'token':
         continue
       assert state.omega_transition() in dfa.terminal_set()
       # we can drop incoming edges for states with a match action
       # of either 'token' or 'harmony_token'
       def is_replacement_candidate(state):
-        action = DfaOptimizer.__match_action(state)
+        action = state.match_action()
         return action.name() == 'token' or action.name() == 'harmony_token'
       for (incoming_key, incoming_state) in incoming:
         # check to see if incoming edges are matched by an outgoing edge
         if (incoming_state == state or  # drop self edges
             incoming_key == TransitionKey.omega() or
             not is_replacement_candidate(incoming_state) or
             not DfaOptimizer.__transistions_match(
               encoding, incoming_key, incoming_state, state)):
           continue
         assert (not incoming_state in replacements or
@@ skipping 21 matching lines @@
         'action' : action,
       }
 
   @staticmethod
   def __new_state_name(state):
     return str(state.node_number())
 
   @staticmethod
   def __split_target_state(state):
     old_name = DfaOptimizer.__new_state_name(state)
-    old_match_action = DfaOptimizer.__match_action(state)
+    old_match_action = state.match_action()
     assert old_match_action.name() == 'token', 'unimplemented'
     precedence = old_match_action.precedence()
     match_action = Action(Term('do_stored_token'), precedence)
-    head_action = Action(
-      Term('store_token', old_match_action.term().args()[0]), precedence)
-    tail_action = Action(Term('no_op'), precedence)
+    stored_token = old_match_action.term().args()[0]
+    head_action = Action(Term('store_token', stored_token), precedence)
+    tail_action = Action(Term('no_op', stored_token), precedence)
     head = DfaOptimizer.__new_state(False, head_action)
     tail = DfaOptimizer.__new_state(False, tail_action)
     match = DfaOptimizer.__new_state(True, match_action)
     head['transitions'][TransitionKey.omega()] = old_name + '_tail'
     tail['transitions'][TransitionKey.omega()] = old_name + '_match'
     return (head, tail, match)
 
   # generate a store action to replace an existing action
   @staticmethod
   def __replacement_action(state, transition_state):
-    old_action = DfaOptimizer.__match_action(state)
+    old_action = state.match_action()
     assert old_action
-    transition_action = DfaOptimizer.__match_action(transition_state).term()
+    transition_action = transition_state.match_action().term()
     if old_action.term() == transition_action:
       # no need to store token
       return Action.empty_action()
     new_name = 'store_' + old_action.name()
     return Action(
       Term(new_name, *old_action.term().args()), old_action.precedence())
 
   @staticmethod
   def __apply_jump(counters, state, new_state, target_state):
     # generate a new action for the new omega transition
@@ skipping 105 matching lines @@
       print 'store_harmony_token %s' % (
         counters['store_harmony_token'])
       print 'transitions removed %s' % counters['removals']
       print 'states split %s' % counters['split_state']
     return Dfa(self.__dfa.encoding(), start_name, states)
 
   @staticmethod
   def optimize(dfa, log):
     optimizer = DfaOptimizer(dfa, log)
     return optimizer.__replace_tokens_with_gotos()