Reviewers: marja,
Message:
Committed patchset #3 manually as r19211 (presubmit successful).
Description:
Experimental parser: cleanup dfa.py
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=19211
Please review this at https://codereview.chromium.org/153993014/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+28, -33 lines):
M src/lexer/lexer_py.re
M tools/lexer_generator/action.py
M tools/lexer_generator/dfa.py
M tools/lexer_generator/nfa.py
Index: src/lexer/lexer_py.re
diff --git a/src/lexer/lexer_py.re b/src/lexer/lexer_py.re
index
5709c20de49dec37cb9bf7b0fc753a763be749dc..9ecc269f9d597421259409f76132a67b6d1848d7
100644
--- a/src/lexer/lexer_py.re
+++ b/src/lexer/lexer_py.re
@@ -27,7 +27,7 @@
# Character classes and auxiliary regexps.
-line_terminator = [:line_terminator:];
+line_terminator = [:line_terminator:]; # TODO(dcarney): just include these
identifier_start = [$_:letter:];
identifier_char = [:identifier_start::identifier_part_not_letter:];
digit = [0-9];
Index: tools/lexer_generator/action.py
diff --git a/tools/lexer_generator/action.py
b/tools/lexer_generator/action.py
index
fdcde20cd1d8cc0ad893a4161896ea087186c8eb..8a854640bfbf7c5481a1d83e10e1494b7b2ae8f9
100644
--- a/tools/lexer_generator/action.py
+++ b/tools/lexer_generator/action.py
@@ -167,7 +167,6 @@ class Action(object):
self.__match_action == other.__match_action)
def __str__(self):
- parts = []
- for action in [self.__entry_action, self.__match_action]:
- parts.append('' if not action else str(action))
+ parts = map(lambda action : '' if not action else str(action),
+ [self.__entry_action, self.__match_action])
return "action< %s >" % " | ".join(parts)
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
50054e3c0f9944bd6c21d49baee20313e06f4afb..32ac769fafbb037fea4a215d42e8e1049486c86c
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -31,10 +31,10 @@ from transition_keys import TransitionKey
class DfaState(AutomatonState):
- def __init__(self, name, action):
+ def __init__(self, name, action, transitions):
super(DfaState, self).__init__()
self.__name = name
- self.__transitions = {}
+ self.__transitions = transitions
self.__action = action
assert isinstance(action, Action)
@@ -44,13 +44,6 @@ class DfaState(AutomatonState):
def action(self):
return self.__action
- def add_transition(self, key, state):
- assert key != None
- assert not key == TransitionKey.epsilon()
- assert not self.__transitions.has_key(key)
- self.__transitions[key] = state
-
-
def epsilon_closure_iter(self):
return iter([])
@@ -71,17 +64,25 @@ class DfaState(AutomatonState):
class Dfa(Automaton):
+ @staticmethod
+ def __add_transition(transitions, key, state):
+ assert key != None
+ assert not key == TransitionKey.epsilon()
+ assert not transitions.has_key(key)
+ transitions[key] = state
+
def __init__(self, encoding, start_name, mapping):
super(Dfa, self).__init__(encoding)
self.__terminal_set = set()
name_map = {}
for name, node_data in mapping.items():
- node = DfaState(name, node_data['action'])
- name_map[name] = node
+ transitions = {}
+ node = DfaState(name, node_data['action'], transitions)
+ name_map[name] = (node, transitions)
if node_data['terminal']:
self.__terminal_set.add(node)
for name, node_data in mapping.items():
- node = name_map[name]
+ (node, transitions) = name_map[name]
inversion = {}
for key, state in node_data['transitions'].items():
if not state in inversion:
@@ -89,8 +90,8 @@ class Dfa(Automaton):
inversion[state].append(key)
for state, keys in inversion.items():
merged_key = TransitionKey.merged_key(encoding, keys)
- node.add_transition(merged_key, name_map[state])
- self.__start = name_map[start_name]
+ self.__add_transition(transitions, merged_key, name_map[state][0])
+ self.__start = name_map[start_name][0]
self.__node_count = len(mapping)
self.__verify()
@@ -179,18 +180,13 @@ class DfaMinimizer:
id_to_state[state_id] = state
action = state.action()
all_keys.append(state.key_iter())
- if action:
- if state not in terminal_set:
- # Match actions are valid only if we have matched the whole
token, not
- # just some sub-part of it.
- assert not action.match_action()
- key = ("nonterminal action", action)
- else:
- key = ("terminal action", action)
- elif state in terminal_set:
- key = ("terminal set",)
+ if state in terminal_set:
+ key = ("terminal set", action)
else:
- key = ("nonterminal set",)
+ # Match actions are valid only if we have matched the whole token,
not
+ # just some sub-part of it.
+ assert not action.match_action()
+ key = ("nonterminal set", action)
if not key in initial_partitions:
initial_partitions[key] = set()
initial_partitions[key].add(state_id)
Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index
ed0b10dcacfbd44234cb2730791341950c156642..cf887304a7fdc6cbe12872c5b5444787c606706d
100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -130,7 +130,7 @@ class Nfa(Automaton):
keys.discard(TransitionKey.epsilon())
return TransitionKey.disjoint_keys(encoding, keys)
- def __to_dfa(self, nfa_state_set, dfa_nodes, end_node):
+ def __to_dfa(self, nfa_state_set, dfa_nodes):
nfa_state_set = Automaton.epsilon_closure(nfa_state_set)
# nfa_state_set will be a state in the dfa.
assert nfa_state_set
@@ -139,7 +139,7 @@ class Nfa(Automaton):
return name
dfa_nodes[name] = {
'transitions': {},
- 'terminal': end_node in nfa_state_set,
+ 'terminal': self.__end in nfa_state_set,
'action' : Action.dominant_action(nfa_state_set)}
# Gather the set of transition keys for which the dfa state will have
# transitions (the disjoint set of all the transition keys from all the
@@ -153,11 +153,11 @@ class Nfa(Automaton):
# states ("match_states") (more accurately, its epsilon closure).
f = lambda state: state.transition_state_iter_for_key(key)
match_states = set(chain(*map(f, nfa_state_set)))
- transition_state = self.__to_dfa(match_states, dfa_nodes, end_node)
+ transition_state = self.__to_dfa(match_states, dfa_nodes)
dfa_nodes[name]['transitions'][key] = transition_state
return name
def compute_dfa(self):
dfa_nodes = {}
- start_name = self.__to_dfa(set([self.__start]), dfa_nodes, self.__end)
+ start_name = self.__to_dfa(set([self.__start]), dfa_nodes)
return (start_name, dfa_nodes)
--
--
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.
