Reviewers: marja,
Message:
Committed patchset #1 manually as r17678.
Description:
Experimental parser: cleanup rule processing result
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=17678
Please review this at https://codereview.chromium.org/61003003/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+37, -17 lines):
M tools/lexer_generator/action_test.py
M tools/lexer_generator/code_generator_test.py
M tools/lexer_generator/dfa.py
M tools/lexer_generator/generator.py
M tools/lexer_generator/rule_parser.py
Index: tools/lexer_generator/action_test.py
diff --git a/tools/lexer_generator/action_test.py
b/tools/lexer_generator/action_test.py
index
66b93d2fbdcc7384bb769551ac05cf22c1287b7a..5ff4498a0c29d72ab347d2f4453055ef5bcd4cee
100644
--- a/tools/lexer_generator/action_test.py
+++ b/tools/lexer_generator/action_test.py
@@ -51,7 +51,7 @@ class ActionTestCase(unittest.TestCase):
automata_for_conditions = process_rules(rules)
self.assertEqual(len(automata_for_conditions), 1)
self.assertTrue('default' in automata_for_conditions)
- (nfa, dfa) = automata_for_conditions['default']
+ dfa = automata_for_conditions['default'].dfa()
self.__verify_last_action(dfa, 'foo', 'ID')
self.__verify_last_action(dfa, 'key', 'KEYWORD')
@@ -66,7 +66,7 @@ class ActionTestCase(unittest.TestCase):
automata_for_conditions = process_rules(rules)
self.assertEqual(len(automata_for_conditions), 1)
self.assertTrue('default' in automata_for_conditions)
- (nfa, dfa) = automata_for_conditions['default']
+ dfa = automata_for_conditions['default'].dfa()
# The keyword is not recognized because of the rule preference order
(ID
# is preferred over KEYWORD).
Index: tools/lexer_generator/code_generator_test.py
diff --git a/tools/lexer_generator/code_generator_test.py
b/tools/lexer_generator/code_generator_test.py
index
92ed6f971228b37e3baf0dd5842807c800f0d9ac..1a5b95854a87487f4867e5c45a505d9598575e21
100644
--- a/tools/lexer_generator/code_generator_test.py
+++ b/tools/lexer_generator/code_generator_test.py
@@ -40,5 +40,5 @@ class CodeGeneratorTestCase(unittest.TestCase):
"foo" { FOO }
eof <<terminate>>'''
rule_processor = RuleProcessor.parse(rules)
- (nfa, dfa) = rule_processor.default_automata()
+ dfa = rule_processor.default_automata().dfa()
CodeGenerator.dfa_to_code(dfa)
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
80b0c1ab94bee687d107f0f1dd2dc227892fafb5..a7b388c1a78bb4338789b5b5f8814c6e0598c3ce
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -26,7 +26,6 @@
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
from automaton import *
-from nfa import Nfa
from transition_keys import TransitionKey
class DfaState(AutomatonState):
@@ -58,14 +57,14 @@ class Dfa(Automaton):
def __init__(self, start_name, mapping):
super(Dfa, self).__init__()
self.__terminal_set = set()
- self.__name_map = {}
+ name_map = {}
for name, node_data in mapping.items():
node = DfaState(name, node_data['action'])
- self.__name_map[name] = node
+ name_map[name] = node
if node_data['terminal']:
self.__terminal_set.add(node)
for name, node_data in mapping.items():
- node = self.__name_map[name]
+ node = name_map[name]
inversion = {}
for key, state in node_data['transitions'].items():
if not state in inversion:
@@ -73,9 +72,15 @@ class Dfa(Automaton):
inversion[state].append(key)
for state, keys in inversion.items():
merged_key = TransitionKey.merged_key(keys)
- node.add_transition(merged_key, self.__name_map[state])
- self.__start = self.__name_map[start_name]
+ node.add_transition(merged_key, name_map[state])
+ self.__start = name_map[start_name]
+ self.__node_count = len(mapping)
+ 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
def start_state(self):
return self.__start
@@ -87,7 +92,7 @@ class Dfa(Automaton):
return set(self.__terminal_set)
def all_states_iter(self):
- return iter(self.__name_map.values())
+ return self.__start.state_iter()
@staticmethod
def __match_char(state, char):
Index: tools/lexer_generator/generator.py
diff --git a/tools/lexer_generator/generator.py
b/tools/lexer_generator/generator.py
index
e8f293b184cf0b2d227424d4ae0ceebf6a37fc87..d6038f08d8c5ee65ddc4123ae7c7ebe0e1f3359d
100644
--- a/tools/lexer_generator/generator.py
+++ b/tools/lexer_generator/generator.py
@@ -67,8 +67,8 @@ load_outer_template = ''' <script>
def generate_html(rule_processor):
scripts = []
loads = []
- for i, (name, (nfa, dfa)) in
enumerate(list(rule_processor.automata_iter())):
- if name == 'Normal': continue
+ 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)
scripts.append(script_template % (nfa_i, nfa.to_dot()))
scripts.append(script_template % (dfa_i, dfa.to_dot()))
@@ -78,7 +78,7 @@ def generate_html(rule_processor):
return file_template % body
def generate_code(rule_processor):
- (nfa, dfa) = rule_processor.default_automata()
+ dfa = rule_processor.default_automata().dfa()
return CodeGenerator.dfa_to_code(dfa)
def lex(rule_processor, string):
Index: tools/lexer_generator/rule_parser.py
diff --git a/tools/lexer_generator/rule_parser.py
b/tools/lexer_generator/rule_parser.py
index
f9787f7ba95d8d1f4812c33901ef398a4a88a2a8..f81444ca150c4c27af391a19650d279983e58ac3
100644
--- a/tools/lexer_generator/rule_parser.py
+++ b/tools/lexer_generator/rule_parser.py
@@ -234,9 +234,26 @@ class RuleProcessor(object):
return self.__automata['default']
def lex(self, string):
- (nfa, dfa) = self.default_automata()
+ dfa = self.default_automata().dfa()
return dfa.lex(string)
+ class Automata(object):
+
+ def __init__(self, nfa):
+ (start, dfa_nodes) = nfa.compute_dfa()
+ self.__nfa = nfa
+ self.__dfa = Dfa(start, dfa_nodes)
+ self.__minimial_dfa = self.__dfa.minimize()
+
+ def nfa(self):
+ return self.__dfa
+
+ def dfa(self):
+ return self.__dfa
+
+ def minimal_dfa(self):
+ return self.__minimial_dfa
+
def __process_parser_state(self, parser_state):
rule_map = {}
builder = NfaBuilder()
@@ -281,6 +298,4 @@ class RuleProcessor(object):
# build the automata
for rule_name, graph in rule_map.items():
nfa = builder.nfa(graph)
- (start, dfa_nodes) = nfa.compute_dfa()
- dfa = Dfa(start, dfa_nodes)
- self.__automata[rule_name] = (nfa, dfa)
+ self.__automata[rule_name] = RuleProcessor.Automata(nfa)
--
--
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.
