Reviewers: marja,
Message:
Committed patchset #1 manually as r17701 (presubmit successful).
Description:
Experimental parser: dump minimal dfa into html
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=17701
Please review this at https://codereview.chromium.org/60733018/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+37, -3 lines):
M tools/lexer_generator/dfa.py
M tools/lexer_generator/generator.py
M tools/lexer_generator/rule_parser.py
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
14a5d6367ff105006f7e122256e5d9756432f9bc..805e6315aa4281f4b00ba77dd52db7b725f399e0
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -243,6 +243,33 @@ class DfaMinimizer:
def __partition_count(partitions):
return len(reduce(lambda acc, p: acc | p.set(), partitions, set()))
+ def __merge_partitions(self, id_map, partitions):
+ mapping = {}
+ name_map = {}
+ for partition in partitions:
+ name_map[partition] = str(partition)
+ alphabet = self.__generate_alphabet()
+ for partition in partitions:
+ state_id = iter(partition).next()
+ state = id_map[state_id]
+ node = {
+ 'transitions' : {},
+ 'terminal' : state in self.__dfa.terminal_set(),
+ 'action' : state.action(),
+ }
+ mapping[str(partition)] = node
+ for key in alphabet:
+ transition_state = state.key_matches(key)
+ if not transition_state:
+ continue
+ transition_id = transition_state.node_number()
+ transition_partition = self.__find_partition(partitions,
transition_id)
+ assert transition_partition
+ node['transitions'][key] = name_map[transition_partition]
+ start_id = self.__dfa.start_state().node_number()
+ start_name = name_map[self.__find_partition(partitions, start_id)]
+ return (start_name, mapping)
+
def minimize(self):
(id_map, partitions) = self.__partition()
node_count = self.__dfa.node_count()
@@ -294,4 +321,5 @@ class DfaMinimizer:
self.__verify_partitions(id_map, partitions)
if len(partitions) == len(id_map):
return self.__dfa
- # merge partitions
+ (start_name, mapping) = self.__merge_partitions(id_map, partitions)
+ return Dfa(start_name, mapping)
Index: tools/lexer_generator/generator.py
diff --git a/tools/lexer_generator/generator.py
b/tools/lexer_generator/generator.py
index
67f144ecab8c2236e49ac5beb8f69dcd4caea8f5..f11531ad7304d803ce7534b7ba61f9fc0fb16978
100644
--- a/tools/lexer_generator/generator.py
+++ b/tools/lexer_generator/generator.py
@@ -69,11 +69,15 @@ def generate_html(rule_processor):
loads = []
for i, (name, automata) in
enumerate(list(rule_processor.automata_iter())):
(nfa, dfa) = (automata.nfa(), automata.dfa())
- (nfa_i, dfa_i) = ("nfa_%d" % i, "dfa_%d" % i)
+ mdfa = None if name == 'default' else automata.minimal_dfa()
+ (nfa_i, dfa_i, mdfa_i) = ("nfa_%d" % i, "dfa_%d" % i, "mdfa_%d" % i)
scripts.append(script_template % (nfa_i, nfa.to_dot()))
- scripts.append(script_template % (dfa_i, dfa.to_dot()))
loads.append(load_template % ("nfa [%s]" % name, nfa_i))
+ scripts.append(script_template % (dfa_i, dfa.to_dot()))
loads.append(load_template % ("dfa [%s]" % name, dfa_i))
+ if mdfa and mdfa != dfa:
+ scripts.append(script_template % (mdfa_i, mdfa.to_dot()))
+ loads.append(load_template % ("mdfa [%s]" % name, mdfa_i))
body = "\n".join(scripts) + (load_outer_template % "\n".join(loads))
return file_template % body
Index: tools/lexer_generator/rule_parser.py
diff --git a/tools/lexer_generator/rule_parser.py
b/tools/lexer_generator/rule_parser.py
index
aebd49936c0edcbadb24ecb5b1039329d237b0b9..1461863b6b00ddd19881669bf1aec7f39fcf33c4
100644
--- a/tools/lexer_generator/rule_parser.py
+++ b/tools/lexer_generator/rule_parser.py
@@ -252,6 +252,8 @@ class RuleProcessor(object):
return self.__dfa
def minimal_dfa(self):
+ if not self.__minimial_dfa:
+ self.__minimial_dfa = self.__dfa.minimize()
return self.__minimial_dfa
def __process_parser_state(self, parser_state, minimize_dfa):
--
--
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.
