Revision: 19211
Author: [email protected]
Date: Mon Feb 10 07:59:18 2014 UTC
Log: Experimental parser: cleanup dfa.py
[email protected]
BUG=
Review URL: https://codereview.chromium.org/153993014
http://code.google.com/p/v8/source/detail?r=19211
Modified:
/branches/experimental/parser/src/lexer/lexer_py.re
/branches/experimental/parser/tools/lexer_generator/action.py
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
=======================================
--- /branches/experimental/parser/src/lexer/lexer_py.re Tue Feb 4 11:58:53
2014 UTC
+++ /branches/experimental/parser/src/lexer/lexer_py.re Mon Feb 10 07:59:18
2014 UTC
@@ -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];
=======================================
--- /branches/experimental/parser/tools/lexer_generator/action.py Mon Feb
3 21:28:33 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/action.py Mon Feb
10 07:59:18 2014 UTC
@@ -167,7 +167,6 @@
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)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Fri Feb 7
16:06:01 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Mon Feb 10
07:59:18 2014 UTC
@@ -31,10 +31,10 @@
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 @@
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 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 @@
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 @@
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)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Fri Feb 7
16:06:01 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Mon Feb 10
07:59:18 2014 UTC
@@ -130,7 +130,7 @@
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 @@
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 @@
# 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.
