Revision: 17438
Author: [email protected]
Date: Thu Oct 31 07:24:53 2013 UTC
Log: Experimental parser: cleanup
[email protected]
BUG=
Review URL: https://codereview.chromium.org/54223002
http://code.google.com/p/v8/source/detail?r=17438
Modified:
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
/branches/experimental/parser/tools/lexer_generator/transition_keys.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Wed Oct 30
13:39:57 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Thu Oct 31
07:24:53 2013 UTC
@@ -56,7 +56,7 @@
for name in mapping.keys():
dfa_state = DfaState(name, offset)
name_map[name] = dfa_state
- offset = offset + 1
+ offset += 1
if name in end_names:
self.__terminal_set.add(dfa_state)
for name, values in mapping.items():
@@ -66,14 +66,14 @@
assert self.__terminal_set
@staticmethod
- def __visit_edges(start, function, state):
+ def __visit_edges(start, visitor, state):
edge = set([start])
visited = set()
while edge:
- next_edge = set()
- for node in edge:
- next_edge |= set(node.transitions().values())
- state = function(node, state)
+ f = lambda (next_edge, state), node: (
+ next_edge | set(node.transitions().values()),
+ visitor(node, state))
+ (next_edge, state) = reduce(f, edge, (set(), state))
visited |= edge
edge = next_edge - visited
return state
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Wed Oct 30
13:39:57 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Thu Oct 31
07:24:53 2013 UTC
@@ -54,7 +54,7 @@
def get_epsilon_transitions(self):
key = TransitionKey.epsilon();
- if not self.__transitions.has_key(key): return frozenset()
+ if not key in self.__transitions: return frozenset()
return frozenset(self.__transitions[key])
def __add_transition(self, key, value):
@@ -62,7 +62,7 @@
assert not self.is_closed(), "already closed"
self.__unclosed.add(key)
return
- if not self.__transitions.has_key(key):
+ if not key in self.__transitions:
self.__transitions[key] = set()
self.__transitions[key].add(value)
@@ -89,11 +89,8 @@
self.__unclosed = None
def __matches(self, match_func, value):
- matches = set()
- for key, values in self.__transitions.items():
- if match_func(key, value):
- matches |= values
- return matches
+ 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)
@@ -103,10 +100,8 @@
@staticmethod
def gather_transition_keys(state_set):
- keys = set()
- for state in state_set:
- keys |= set(state.__transitions.keys())
- return TransitionKey.merge_key_set(keys)
+ f = lambda acc, state: acc | set(state.__transitions.keys())
+ return TransitionKey.merge_key_set(reduce(f, state_set, set()))
class NfaBuilder:
@@ -173,10 +168,10 @@
def __process(self, graph):
assert type(graph) == TupleType
method = "_NfaBuilder__" + graph[0].lower()
- if (not self.__operation_map.has_key(method)):
- matches = [func for (name, func) in self.__members if name == method]
+ if not method in self.__operation_map:
+ matches = filter((lambda (name, func): name == method),
self.__members)
assert len(matches) == 1
- self.__operation_map[method] = matches[0]
+ self.__operation_map[method] = matches[0][1]
return self.__operation_map[method](graph)
def __patch_ends(self, ends, new_end):
@@ -203,22 +198,20 @@
def __visit_edges(edge, compute_next_edge, visitor, state):
visited = set()
while edge:
- next_edge = set()
- for node in edge:
- next_edge |= compute_next_edge(node)
- state = visitor(node, state)
+ f = lambda (next_edge, state), node: (
+ next_edge | compute_next_edge(node),
+ visitor(node, state))
+ (next_edge, state) = reduce(f, edge, (set(), state))
visited |= edge
edge = next_edge - visited
return state
- def __visit_all_edges(self, function, state):
+ def __visit_all_edges(self, visitor, state):
edge = set([self.__start])
def next_edge(node):
- next = set()
- for values in node.transitions().values():
- next |= values
- return next
- return Nfa.__visit_edges(edge, next_edge, function, state)
+ f = lambda acc, values: acc | values
+ return reduce(f, node.transitions().values(), set())
+ return Nfa.__visit_edges(edge, next_edge, visitor, state)
def __verify(self, nodes_created):
def f(node, node_list):
@@ -244,37 +237,31 @@
@staticmethod
def __close(states):
- closure = set(states)
- for node in states:
- closure |= node.epsilon_closure()
- return closure
+ f = lambda acc, node: acc | node.epsilon_closure()
+ return reduce(f, states, set(states))
def matches(self, string):
self.__compute_epsilon_closures()
valid_states = Nfa.__close(set([self.__start]))
for c in string:
- next_valid_states = set()
- for valid_state in valid_states:
- next_valid_states |= valid_state.char_matches(c)
- valid_states = Nfa.__close(next_valid_states)
+ f = lambda acc, state: acc | state.char_matches(c)
+ valid_states = Nfa.__close(reduce(valid_states, f, set()))
if not valid_states:
return False
return self.__end in valid_states
@staticmethod
- def __to_dfa(nfa_state_set, dfa_builder):
+ def __to_dfa(nfa_state_set, builder):
nfa_state_set = Nfa.__close(nfa_state_set)
name = str([x.node_number() for x in nfa_state_set])
- (dfa_nodes, end_nodes, end_node) = dfa_builder
- if dfa_nodes.has_key(name):
+ (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):
- reachable_set = set()
- for nfa_state in nfa_state_set:
- reachable_set |= nfa_state.key_matches(key)
- dfa_node[key] = Nfa.__to_dfa(reachable_set, dfa_builder)
+ 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:
end_nodes.add(name)
return name
=======================================
--- /branches/experimental/parser/tools/lexer_generator/transition_keys.py
Wed Oct 30 13:39:57 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/transition_keys.py
Thu Oct 31 07:24:53 2013 UTC
@@ -25,79 +25,86 @@
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
class TransitionKey:
- __single_char_type = 0
- __epsilon_type = 1
- __any_type = 2
- __class_type = 3
+ __lower_bound = 0
+ __latin_1_upper_bound = 255
+ __unicode_whitespace_bounds = (256, 256)
+ __unicode_literal_bounds = (257, 257)
+ __upper_bound = 257
@staticmethod
- def __create(key_type, value):
+ def __create(ranges):
+ # TODO - verify ranges
key = TransitionKey()
- key.__type = key_type
- key.__value = value
+ key.__ranges = ranges
+ key.__cached_hash = None
return key
+ __cached_epsilon = None
@staticmethod
def epsilon():
- return TransitionKey.__create(TransitionKey.__epsilon_type, None)
+ if (TransitionKey.__cached_epsilon == None):
+ TransitionKey.__cached_epsilon = TransitionKey.__create([])
+ return TransitionKey.__cached_epsilon
+ __cached_any = None
@staticmethod
def any():
- return TransitionKey.__create(TransitionKey.__any_type, None)
+ if (TransitionKey.__cached_any == None):
+ bounds = [(TransitionKey.__lower_bound, TransitionKey.__upper_bound)]
+ TransitionKey.__cached_any = TransitionKey.__create(bounds)
+ return TransitionKey.__cached_any
@staticmethod
def single_char(char):
- return TransitionKey.__create(TransitionKey.__single_char_type, char)
+ char = ord(char)
+ assert (TransitionKey.__lower_bound <= char and
+ char <= TransitionKey.__latin_1_upper_bound)
+ return TransitionKey.__create([(char, char)])
@staticmethod
def character_class(invert, graph):
# TODO
- return TransitionKey.__create(TransitionKey.__class_type, (invert,
graph))
-
- @staticmethod
- def __class_match(class_graph, char):
- assert False
-
- __char_matchers = {
- __single_char_type: (lambda x, y : x == y),
- __epsilon_type: (lambda x, y : False),
- __any_type: (lambda x, y : True),
- __class_type: __class_match,
- }
+ return TransitionKey.__create([(129, 129)])
def matches_char(self, char):
- return TransitionKey.__char_matchers[self.__type](self.__value, char)
+ for r in self.__ranges:
+ if r[0] <= char and char <= r[1]: return True
+ return False
def matches_key(self, key):
+ assert isinstance(key, self.__class__)
assert key != TransitionKey.epsilon()
- assert self != TransitionKey.epsilon()
- if (key == self): return True
- # TODO need to test intersection/symmetric diff
- assert self != TransitionKey.any()
+ if self == key: return True
+ if self == TransitionKey.epsilon(): return False
+ # TODO
return False
def __hash__(self):
- if self.__value == None:
- return hash(self.__type)
- return hash(self.__type) ^ hash(self.__value)
+ if self.__cached_hash == None:
+ initial_hash = hash((-1, TransitionKey.__upper_bound + 1))
+ f = lambda acc, r: acc ^ hash(r)
+ self.__cached_hash = reduce(f, self.__ranges, initial_hash)
+ return self.__cached_hash
def __eq__(self, other):
- return (
- isinstance(other, self.__class__) and
- self.__type == other.__type and
- self.__value == other.__value)
+ return isinstance(other, self.__class__) and self.__ranges ==
other.__ranges
+
+ @staticmethod
+ def __print_range(r):
+ if r[0] == r[1]:
+ return "'%s'" % chr(r[0])
+ else:
+ return "['%s'-'%s']" % (chr(r[0]), chr(r[1]))
def __str__(self):
- if self.__type == self.__single_char_type:
- return "'%s'" % self.__value
- if self.__type == self.__epsilon_type:
+ if self == self.epsilon():
return "epsilon"
- if self.__type == self.__any_type:
+ if self == self.any():
return "any"
- # TODO
- return "class"
+ return ", ".join(TransitionKey.__print_range(x) for x in self.__ranges)
@staticmethod
def merge_key_set(key_set):
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
