Reviewers: marja,
Message:
Committed patchset #1 manually as r19204 (presubmit successful).
Description:
Experimental parser: Abstact state matching
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=19204
Please review this at https://codereview.chromium.org/155573004/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+41, -56 lines):
M tools/lexer_generator/automaton.py
M tools/lexer_generator/code_generator.py
M tools/lexer_generator/dfa.py
M tools/lexer_generator/dfa_optimizer.py
M tools/lexer_generator/nfa.py
Index: tools/lexer_generator/automaton.py
diff --git a/tools/lexer_generator/automaton.py
b/tools/lexer_generator/automaton.py
index
2ed399b3ce8d205b54e157bd50b009c75b0c9f4c..a3082fd313640c36b539bfa7dfc537dff7b4821f
100644
--- a/tools/lexer_generator/automaton.py
+++ b/tools/lexer_generator/automaton.py
@@ -55,26 +55,23 @@ class AutomatonState(object):
__pass = lambda x : True
def key_iter(self, key_filter = __pass):
- for k in self.transitions().keys():
- if key_filter(k): yield k
+ return self.key_state_iter(
+ key_filter = key_filter, yield_func = lambda x, y: x)
def state_iter(self, key_filter = __pass, state_filter = __pass):
- return self.key_state_iter(key_filter, state_filter, lambda x, y: y)
-
- def key_state_iter(
- self,
- key_filter = __pass,
- state_filter = __pass,
- yield_func = lambda x, y : (x, y)):
- for key, states in self.transitions().items():
- if key_filter(key):
- if not self.transitions_to_multiple_states():
- if state_filter(states):
- yield yield_func(key, states)
- else:
- for state in states:
- if state_filter(state):
- yield yield_func(key, state)
+ return self.key_state_iter(
+ key_filter = key_filter, state_filter = state_filter,
+ yield_func = lambda x, y: y)
+
+ def transition_state_iter_for_char(self, value):
+ return self.key_state_iter(
+ match_func = lambda k, v : k.matches_char(value),
+ yield_func = lambda x, y: y)
+
+ def transition_state_iter_for_key(self, value):
+ return self.key_state_iter(
+ match_func = lambda k, v : k.is_superset_of_key(value),
+ yield_func = lambda x, y: y)
class Automaton(object):
Index: tools/lexer_generator/code_generator.py
diff --git a/tools/lexer_generator/code_generator.py
b/tools/lexer_generator/code_generator.py
index
1b149fd9453598ff40436be0717ed37078b72703..c542ec56a08fd33cb838e0ed103bea3776a394a5
100644
--- a/tools/lexer_generator/code_generator.py
+++ b/tools/lexer_generator/code_generator.py
@@ -65,7 +65,7 @@ class CodeGenerator:
match_action = action.match_action()
# generate ordered transitions
transitions = map(lambda (k, v) : (k, v.node_number()),
- state.transitions().items())
+ state.key_state_iter())
def cmp(left, right):
return TransitionKey.canonical_compare(left[0], right[0])
transitions = sorted(transitions, cmp)
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
648529428d1adf7a3dae5ffee2f95836f9a917a1..50054e3c0f9944bd6c21d49baee20313e06f4afb
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -38,9 +38,6 @@ class DfaState(AutomatonState):
self.__action = action
assert isinstance(action, Action)
- def transitions_to_multiple_states(self):
- return False
-
def name(self):
return self.__name
@@ -53,30 +50,24 @@ class DfaState(AutomatonState):
assert not self.__transitions.has_key(key)
self.__transitions[key] = state
- def transitions(self):
- return self.__transitions
def epsilon_closure_iter(self):
return iter([])
- # TODO abstract state matching
- def __matches(self, match_func, value):
- items = self.__transitions.items()
- return [state for (key, state) in items if match_func(key, value)]
-
- def transition_state_iter_for_char(self, value):
- return iter(self.__matches(lambda k, v : k.matches_char(v), value))
-
- def transition_state_iter_for_key(self, value):
- return iter(self.__matches(lambda k, v : k.is_superset_of_key(v),
value))
-
def transition_state_for_key(self, value):
- matches = self.__matches(lambda k, v : k.is_superset_of_key(v), value)
- if not matches:
- return None
- # Since this is a dfa, we should have at most one such state. Return
it.
- assert len(matches) == 1
- return matches[0]
+ matches = list(self.transition_state_iter_for_key(value))
+ assert len(matches) <= 1
+ return matches[0] if matches else None
+
+ def key_state_iter(
+ self,
+ key_filter = lambda x: True,
+ state_filter = lambda x: True,
+ match_func = lambda x, y: True,
+ yield_func = lambda x, y: (x, y)):
+ for key, state in self.__transitions.items():
+ if key_filter(key) and state_filter(state) and match_func(key,
state):
+ yield yield_func(key, state)
class Dfa(Automaton):
Index: tools/lexer_generator/dfa_optimizer.py
diff --git a/tools/lexer_generator/dfa_optimizer.py
b/tools/lexer_generator/dfa_optimizer.py
index
115ed1c56fb772e50dde5a85e7387bb43e2ed8aa..c13f4a9c789092c58b7ca41845d0129f13ec02cf
100644
--- a/tools/lexer_generator/dfa_optimizer.py
+++ b/tools/lexer_generator/dfa_optimizer.py
@@ -249,7 +249,7 @@ class DfaOptimizer(object):
}
states[name(state)] = new_state
state_replacements = replacements[state] if state in replacements
else {}
- for transition_key, transition_state in state.transitions().items():
+ for (transition_key, transition_state) in state.key_state_iter():
if not transition_key in state_replacements:
new_state['transitions'][transition_key] = name(transition_state)
continue
Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index
2367630b76b711cea0725b5df5e1083e276f3ca8..ed0b10dcacfbd44234cb2730791341950c156642
100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -37,9 +37,6 @@ class NfaState(AutomatonState):
self.__epsilon_closure = None
self.__action = Action.empty_action()
- def transitions_to_multiple_states(self):
- return True
-
def epsilon_closure_iter(self):
return iter(self.__epsilon_closure)
@@ -94,17 +91,17 @@ class NfaState(AutomatonState):
if not unclosed:
self.__add_transition(TransitionKey.epsilon(), end)
- def __matches(self, match_func, value):
- # f collects states whose corresponding TransitionKey matches 'value'.
- items = self.__transitions.items()
- iters = [iter(states) for (key, states) in items if match_func(key,
value)]
- return chain(*iters)
-
- def transition_state_iter_for_char(self, value):
- return self.__matches(lambda k, v : k.matches_char(v), value)
-
- def transition_state_iter_for_key(self, value):
- return self.__matches(lambda k, v : k.is_superset_of_key(v), value)
+ def key_state_iter(
+ self,
+ key_filter = lambda x: True,
+ state_filter = lambda x: True,
+ match_func = lambda x, y: True,
+ yield_func = lambda x, y: (x, y)):
+ for key, states in self.__transitions.items():
+ if key_filter(key):
+ for state in states:
+ if state_filter(state) and match_func(key, state):
+ yield yield_func(key, state)
class Nfa(Automaton):
--
--
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.
