Revision: 17701
Author: [email protected]
Date: Wed Nov 13 15:37:46 2013 UTC
Log: Experimental parser: dump minimal dfa into html
[email protected]
BUG=
Review URL: https://codereview.chromium.org/60733018
http://code.google.com/p/v8/source/detail?r=17701
Modified:
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/generator.py
/branches/experimental/parser/tools/lexer_generator/rule_parser.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Wed Nov 13
15:06:07 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Wed Nov 13
15:37:46 2013 UTC
@@ -243,6 +243,33 @@
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 @@
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)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/generator.py Wed
Nov 13 15:06:07 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/generator.py Wed
Nov 13 15:37:46 2013 UTC
@@ -69,11 +69,15 @@
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
=======================================
--- /branches/experimental/parser/tools/lexer_generator/rule_parser.py Wed
Nov 13 15:06:07 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/rule_parser.py Wed
Nov 13 15:37:46 2013 UTC
@@ -252,6 +252,8 @@
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.
