Experimental parser: abstract lexing

tools/lexer_generator/automaton.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 13 matching lines @@
 # 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, ListType
 from itertools import chain
 from transition_keys import TransitionKey
 
 class Action(object):
 
+  @staticmethod
+  def dominant_action(state_set):
+    action = None
+    for state in state_set:
+      if not state.action():
+        continue
+      if not action:
+        action = state.action()
+        continue
+      if state.action().precedence() == action.precedence():
+        assert state.action() == action
+      elif state.action().precedence() < action.precedence():
+        action = state.action()
+    return action
+
   def __init__(self, entry_action, match_action, precedence = -1):
     for action in [entry_action, match_action]:
       if action == None:
         continue
       assert type(action) == TupleType and len(action)
       assert action[0] != None
     assert entry_action or match_action
     self.__entry_action = entry_action
     self.__match_action = match_action
     self.__precedence = precedence
@@ skipping 82 matching lines @@
       next_edge_iters = []
       def f(visit_state, node):
         next_edge_iters.append(state_iter(node))
         return visitor(node, visit_state)
       visit_state = reduce(f, edge, visit_state)
       next_edge = set(chain(*next_edge_iters))
       visited |= edge
       edge = next_edge - visited
     return visit_state
 
+  def start_set(self):
+    return set([self.start_state()])
+
   def visit_all_states(self, visitor, visit_state = None, state_iter = None):
     return self.visit_states(self.start_set(), visitor, visit_state, state_iter)
 
+  # TODO use iters
+  @staticmethod
+  def epsilon_closure(states):
+    f = lambda acc, node: acc | node.epsilon_closure()
+    return reduce(f, states, set(iter(states)))
+
+  @staticmethod
+  def __transition_states_for_char(valid_states, c):
+    f = lambda state : state.transition_state_iter_for_char(c)
+    return set(chain(*map(f, Automaton.epsilon_closure(valid_states))))
+
+  def matches(self, string):
+    valid_states = self.start_set()
+    for c in string:
+      valid_states = Automaton.__transition_states_for_char(valid_states, c)
+      if not valid_states:
+        return False
+    valid_states = self.epsilon_closure(valid_states)
+    return len(self.terminal_set().intersection(valid_states)) > 0
+
+  def lex(self, string):
+    last_position = 0
+    valid_states = self.start_set()
+    for pos, c in enumerate(string):
+      transitions = Automaton.__transition_states_for_char(valid_states, c)
+      if transitions:
+        valid_states = transitions
+        continue
+      action = Action.dominant_action(valid_states)
+      assert action # must invoke default action here
+      yield (action, last_position, pos)
+      last_position = pos
+      # lex next token
+      valid_states = Automaton.__transition_states_for_char(self.start_set(), c)
+      assert valid_states
+    valid_states = self.epsilon_closure(valid_states)
+    action = Action.dominant_action(valid_states)
+    assert action # must invoke default action here
+    yield (action, last_position, len(string))
+
   def to_dot(self):
 
     def escape(v):
       v = str(v)
       v = v.replace('\r', '\\\\r').replace('\t', '\\\\t').replace('\n', '\\\\n')
       v = v.replace('\\', '\\\\').replace('\"', '\\\"')
       return v
 
     def f(node, (node_content, edge_content)):
       if node.action():
@@ skipping 29 matching lines @@
   node [shape = doublecircle, style=unfilled]; %s
   node [shape = circle];
 %s
 %s
 }
     ''' % (start_shape,
            start_number,
            " ".join(terminals),
            "\n".join(edge_content),
            "\n".join(node_content))