Experimental parser: add backtracking

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 120 matching lines @@
 #  |             v
 #  \--[A-Z]---> [s3]
 #
 # We can add a goto from s1 to s2 (after checking for "a"), because the
 # transitions match: with [b-z], both states transition to s2, and with [A-Z],
 # both states transition to s3. Note that [a-z] is a superkey of [b-z], and the
 # transition from s2 is defined for the superkey, but that is ok.
 
 class DfaOptimizer(object):
 
+  @staticmethod
+  def optimize(dfa, log):
+    return DfaOptimizer(dfa, log).__replace_tokens_with_gotos()
+
   def __init__(self, dfa, log):
     self.__dfa = dfa
     self.__log = log
 
   @staticmethod
   def __transistions_match(encoding, incoming_key, incoming_state, state):
     keys = set(state.key_iter())
     keys.add(incoming_key)
     disjoint_keys = TransitionKey.disjoint_keys(encoding, keys)
     for key in disjoint_keys:
       if not incoming_key.is_superset_of_key(key):
         continue
       transition_state = state.transition_state_for_key(key)
       if incoming_state.transition_state_for_key(key) != transition_state:
         return False
     return True
 
   @staticmethod
-  def __build_incoming_transitions(dfa):
-    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 __build_replacement_map(dfa):
     replacements = {}
     encoding = dfa.encoding()
-    incoming_transitions = DfaOptimizer.__build_incoming_transitions(dfa)
-    replacement_targets = set([])
+    incoming_transitions = dfa.build_incoming_transitions_map()
+    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 = state.match_action()
@@ skipping 86 matching lines @@
     counters[new_action.name()] += 1
     # install new match state
     match_state_id = DfaOptimizer.__new_state_name(state) + '_match'
     new_state['transitions'][TransitionKey.omega()] = match_state_id
     match_state = DfaOptimizer.__new_state(False, new_action)
     match_state['transitions'][TransitionKey.omega()] = jump_target + '_tail'
     return match_state
 
   @staticmethod
   def __remove_orphaned_states(states, orphanable, start_name):
-    seen = set([])
+    seen = set()
     def visit(state_id, acc):
       seen.add(state_id)
     def state_iter(state_id):
       return states[state_id]['transitions'].itervalues()
     Automaton.visit_states(set([start_name]), visit, state_iter=state_iter)
     def f(name, state):
       assert name in seen or name in orphanable
       return name in seen
     return {k: v for k, v in states.iteritems() if f(k, v)}
 
@@ skipping 11 matching lines @@
     name = DfaOptimizer.__new_state_name
     counters = {
       'removals' : 0,
       'goto_start' : 0,
       'store_token' : 0,
       'store_harmony_token' : 0,
       'split_state' : 0
       }
     # map the old state to the new state, with fewer transitions and
     # goto actions
-    orphanable = set([])
+    orphanable = set()
     def replace_state(state, acc):
       if state in replacements:
         target_state = replacements[state][0]
         deletions = replacements[state][1]
       else:
         deletions = {}
       # this is a replacement target, so we split the state
       if state in replacement_targets:
         assert not deletions
         (head, tail, match) = DfaOptimizer.__split_target_state(state)
@@ skipping 39 matching lines @@
     # dump stats
     if self.__log:
       print 'goto_start inserted %s' % counters['goto_start']
       print 'store_token inserted %s' % (
         counters['store_token'])
       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()