Reviewers: marja,
Message:
Committed patchset #1 manually as r19405 (presubmit successful).
Description:
Experimental parser: more verification
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=19405
Please review this at https://codereview.chromium.org/169583003/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+18, -4 lines):
M tools/lexer_generator/dfa.py
M tools/lexer_generator/dfa_minimizer.py
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
be59ac0c27020bf4647e282e6608372d88a2a9a1..9631546e925802ce97d55cbc7cf4d9d03d41aa29
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -89,6 +89,7 @@ class Dfa(Automaton):
name_map[name] = (node, transitions)
if node_data['terminal']:
self.__terminal_set.add(node)
+ all_keys = []
for name, node_data in mapping.items():
(node, transitions) = name_map[name]
inversion = {}
@@ -97,16 +98,32 @@ class Dfa(Automaton):
inversion[state] = []
inversion[state].append(key)
for state, keys in inversion.items():
+ all_keys += keys
merged_key = TransitionKey.merged_key(encoding, keys)
self.__add_transition(transitions, merged_key, name_map[state][0])
self.__start = name_map[start_name][0]
self.__node_count = len(mapping)
+ self.__disjoint_keys = sorted(
+ TransitionKey.disjoint_keys(encoding, all_keys))
self.__verify()
def __verify(self):
assert self.__terminal_set
state_count = self.visit_all_states(lambda state, count: count + 1, 0)
assert self.__node_count == state_count
+ # assert keys are disjoint
+ def f(state, remaining):
+ remaining = set(TransitionKey.disjoint_keys(self.encoding(),
+ state.key_iter()))
+ for key in state.key_iter():
+ to_drop = set(filter(lambda x : key.is_superset_of_key(x),
remaining))
+ assert to_drop
+ remaining -= to_drop
+ assert not remaining
+ self.visit_all_states(f, set(self.disjoint_keys_iter()))
+
+ def disjoint_keys_iter(self):
+ return iter(self.__disjoint_keys)
def node_count(self):
return self.__node_count
Index: tools/lexer_generator/dfa_minimizer.py
diff --git a/tools/lexer_generator/dfa_minimizer.py
b/tools/lexer_generator/dfa_minimizer.py
index
9b42f604ff11cb3b34fd7a710f0dd8dac29de4ea..142ce1a33e4214cc52a85acd0fbfefd4a73095c7
100644
--- a/tools/lexer_generator/dfa_minimizer.py
+++ b/tools/lexer_generator/dfa_minimizer.py
@@ -89,14 +89,12 @@ class DfaMinimizer:
# IDs.
initial_partitions = {}
terminal_set = self.__dfa.terminal_set()
- all_keys = [] # Will contain all TransitionKeys in the dfa.
# f fills in initial_partitions, id_to_state and all_keys.
def f(state, visitor_state):
state_id = len(id_to_state)
id_to_state[state_id] = state
action = state.action()
- all_keys.append(state.key_iter())
if state in terminal_set:
key = ("terminal set", action)
else:
@@ -133,8 +131,7 @@ class DfaMinimizer:
# become clear when we check the transition for TransitionKey [c-d]
(S1 has
# a transition to S2, S3 has a transition to S4).
encoding = self.__dfa.encoding()
- self.__alphabet = list(
- TransitionKey.disjoint_keys(encoding, chain(*all_keys)))
+ self.__alphabet = list(self.__dfa.disjoint_keys_iter())
# For each state and each TransitionKey in the alphabet, find out which
# transition we take from the state with the TransitionKey.
--
--
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.
