Experimental lexer generator: First draft of a Python lexer (based on the automata).

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 80 matching lines @@
         yield action
     if state in self.__terminal_set:
       yield ('TERMINATE', )
     else:
       yield ('MISS',)
 
   def matches(self, string):
     actions = list(self.collect_actions(string))
     return actions and actions[-1][0] == 'TERMINATE'
 
+  def lex(self, string):
+    state = self.__start
+    stored_action = None
+    pos = 0
+    while pos < len(string):
+      c = string[pos]
+      next = [s for k, s in state.transitions().items() if k.matches_char(c)]
+      if not next:
+        # Maybe we have a stored action before. Take it and backtrack to the
+        # position where that action was.
+        if stored_action:
+          yield stored_action
+          return
+        # FIXME: Otherwise, use the default rule if this happens at the start
+        # state of the automaton.
+
+      assert len(next) == 1
+      (state, action) = next[0]
+
+      # Special actions: terminate
+      if action and action[2] == 'terminate':
+        if stored_action:
+          yield stored_action
+        yield (action, pos)
+        return
+
+      # Normally we don't know yet whether to take the action - it depends on
+      # what comes next.
+      if action:
+        stored_action = (action, pos)
+
+      pos += 1
+
   def __visit_all_edges(self, visitor, state):
     edge = set([self.__start])
     first = lambda v: set([x[0] for x in v])
     next_edge = lambda node: first(node.transitions().values())
     return self.visit_edges(edge, next_edge, visitor, state)
 
   def to_dot(self):
     iterator = lambda visitor, state: self.__visit_all_edges(visitor, state)
     return self.generate_dot(self.__start, self.__terminal_set, iterator)