Experimental parser: more tests, better key logic

tools/lexer_generator/nfa.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 75 matching lines @@
         self.__add_transition(key, end)
       if not self.__unclosed:
         self.add_epsilon_transition(end)
     self.__unclosed = None
 
   def __matches(self, match_func, value):
     f = lambda acc, (k, vs): acc | vs if match_func(k, value) else acc
     return reduce(f, self.__transitions.items(), set())
 
   def char_matches(self, value):
-    return self.__matches((lambda k, v : k.matches_char(v)), value)
+    return self.__matches(lambda k, v : k.matches_char(v), value)
 
   def key_matches(self, value):
-    return self.__matches((lambda k, v : k.matches_key(v)), value)
+    return self.__matches(lambda k, v : k.matches_key(v), value)
 
   @staticmethod
   def gather_transition_keys(state_set):
     f = lambda acc, state: acc | set(state.__transitions.keys())
-    return TransitionKey.merge_key_set(reduce(f, state_set, set()))
+    return TransitionKey.disjoint_keys(reduce(f, state_set, set()))
 
 class NfaBuilder:
 
   def __init__(self):
     self.__operation_map = {}
     self.__members = getmembers(self)
 
   def __new_state(self):
     node_number = self.node_number
     self.node_number = self.node_number + 1
@@ skipping 47 matching lines @@
   def __not_class(self, graph):
     return self.__key_state(TransitionKey.character_class(True, graph[1]))
 
   def __any(self, graph):
     return self.__key_state(TransitionKey.any())
 
   def __process(self, graph):
     assert type(graph) == TupleType
     method = "_NfaBuilder__" + graph[0].lower()
     if not method in self.__operation_map:
-      matches = filter((lambda (name, func): name == method), self.__members)
+      matches = filter(lambda (name, func): name == method, self.__members)
       assert len(matches) == 1
       self.__operation_map[method] = matches[0][1]
     return self.__operation_map[method](graph)
 
   def __patch_ends(self, ends, new_end):
     for end in ends:
       end.close(new_end)
 
   def nfa(self, graph):
     self.node_number = 0
@@ skipping 63 matching lines @@
     for c in string:
       f = lambda acc, state: acc | state.char_matches(c)
       valid_states = Nfa.__close(reduce(f, valid_states, set()))
       if not valid_states:
         return False
     return self.__end in valid_states
 
   @staticmethod
   def __to_dfa(nfa_state_set, builder):
     nfa_state_set = Nfa.__close(nfa_state_set)
+    assert nfa_state_set
     name = str([x.node_number() for x in nfa_state_set])
     (dfa_nodes, end_nodes, end_node) = builder
     if name in dfa_nodes:
       return name
     dfa_node = {}
     dfa_nodes[name] = dfa_node
     for key in NfaState.gather_transition_keys(nfa_state_set):
       f = lambda acc, state: acc | state.key_matches(key)
       dfa_node[key] = Nfa.__to_dfa(reduce(f, nfa_state_set, set()), builder)
     if end_node in nfa_state_set:
@@ skipping 26 matching lines @@
 digraph finite_state_machine {
   rankdir=LR;
   node [shape = circle, style=filled, bgcolor=lightgrey]; S_%s
   node [shape = doublecircle, style=unfilled]; S_%s
   node [shape = circle];
 %s
 }
     ''' % (self.__start.node_number(),
            self.__end.node_number(),
            "\n".join(node_content))