Revision: 19204
Author: [email protected]
Date: Fri Feb 7 16:06:01 2014 UTC
Log: Experimental parser: Abstact state matching
[email protected]
BUG=
Review URL: https://codereview.chromium.org/155573004
http://code.google.com/p/v8/source/detail?r=19204
Modified:
/branches/experimental/parser/tools/lexer_generator/automaton.py
/branches/experimental/parser/tools/lexer_generator/code_generator.py
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/automaton.py Mon
Feb 3 21:28:33 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/automaton.py Fri
Feb 7 16:06:01 2014 UTC
@@ -55,26 +55,23 @@
__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)
+ return self.key_state_iter(
+ key_filter = key_filter, state_filter = state_filter,
+ yield_func = 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)
+ 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):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Mon Feb 3 21:28:33 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Fri Feb 7 16:06:01 2014 UTC
@@ -65,7 +65,7 @@
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)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Mon Feb 3
15:08:36 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Fri Feb 7
16:06:01 2014 UTC
@@ -38,9 +38,6 @@
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 @@
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_for_key(self, value):
+ matches = list(self.transition_state_iter_for_key(value))
+ assert len(matches) <= 1
+ return matches[0] if matches else None
- 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]
+ 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):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Mon Feb 3 15:08:36 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Fri Feb 7 16:06:01 2014 UTC
@@ -249,7 +249,7 @@
}
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
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Mon Feb 3
15:08:36 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Fri Feb 7
16:06:01 2014 UTC
@@ -37,9 +37,6 @@
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 @@
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.
