Experimental parser: support subgraph inlining

tools/lexer_generator/nfa_builder.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 129 matching lines @@
     action = Action.from_term(action_term)
     end = self.__new_state()
     self.__patch_ends(ends, end)
     end.set_action(action)
     # Force all match actions to be terminal.
     if action.match_action():
       global_end = self.__global_end()
       end.add_epsilon_transition(global_end)
     return (start, [end])
 
-  def __continue(self, subtree):
+  def __continue(self, subtree, depth):
     'add an epsilon transitions to the start node of the current subtree'
     (start, ends) = self.__process(subtree)
-    state = self.__peek_state()
+    index = -1 - min(int(depth), len(self.__states) - 1)
+    state = self.__states[index]
     if not state['start_node']:
       state['start_node'] = self.__new_state()
     self.__patch_ends(ends, state['start_node'])
     return (start, [])
 
   def __unique_key(self, name):
     return self.__key_state(TransitionKey.unique(name))
 
   def __join(self, tree, name):
     (subtree_start, subtree_end, nodes_in_subtree) = self.__nfa(name)
-    (start, ends) = self.__process(tree)
-    self.__patch_ends(ends, subtree_start)
+    if tree:
+      (start, ends) = self.__process(tree)
+      self.__patch_ends(ends, subtree_start)
+    else:
+      start = subtree_start
     if subtree_end:
       return (start, [subtree_end])
     else:
       return (start, [])
 
   def __get_method(self, name):
     'lazily build map of all private bound methods and return the one requested'
     if not self.__operation_map:
       prefix = "_NfaBuilder__"
       self.__operation_map = {name[len(prefix):] : f for (name, f) in
@@ skipping 13 matching lines @@
     for state in self.__states:
       assert state['name'] != name, 'recursive subgraph'
     self.__states.append({
       'start_node' : None,
       'name' : name
     })
 
   def __pop_state(self):
     return self.__states.pop()
 
-  def __peek_state(self):
-    return self.__states[-1]
-
   def __nfa(self, name):
     tree = self.__subtree_map[name]
     start_node_number = self.__node_number
     self.__push_state(name)
     (start, ends) = self.__process(tree)
     state = self.__pop_state()
     # move saved start node into start
     if state['start_node']:
       state['start_node'].close(start)
       start = state['start_node']
@@ skipping 52 matching lines @@
     self.__compute_epsilon_closures(start)
     f = lambda node, state: self.__replace_catch_all(self.__encoding, node)
     Automaton.visit_states(set([start]), f)
     return Nfa(self.__encoding, start, global_end_to_return, nodes_created)
 
   @staticmethod
   def add_action(term, action):
     return Term('ACTION', term, action.to_term())
 
   @staticmethod
-  def add_continue(term):
-    return Term('CONTINUE', term)
+  def add_continue(tree, depth):
+    return Term('CONTINUE', tree, depth)
 
   @staticmethod
   def unique_key(name):
     return Term('UNIQUE_KEY', name)
 
   @staticmethod
   def join_subtree(tree, subtree_name):
     return Term('JOIN', tree, subtree_name)
 
   @staticmethod
   def or_terms(terms):
     return reduce(lambda acc, g: Term('OR', acc, g), terms)
 
   @staticmethod
   def cat_terms(terms):
     return reduce(lambda acc, g: Term('CAT', acc, g), terms)
 
   __modifer_map = {
     '+': 'ONE_OR_MORE',
     '?': 'ZERO_OR_ONE',
     '*': 'ZERO_OR_MORE',
   }
 
   @staticmethod
   def apply_modifier(modifier, term):
     return Term(NfaBuilder.__modifer_map[modifier], term)