Reviewers: dcarney,
Message:
Committed patchset #3 manually as r18744 (presubmit successful).
Description:
Experimental parser: remove hacks from replace_tokens_with_gotos.
The hack was for making sure that the state to which we "goto" is connected
to
the state graph: it avoided doing the replacement for states which have an
entry
action, and our grammar happened to have such an action, so it worked.
After this change, we insert a bogus edge to make the "goto" state
connected to
the state graph, and remove the "don't replace states which have an entry
action" condition.
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=18744
Please review this at https://codereview.chromium.org/144943003/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+22, -16 lines):
M tools/lexer_generator/code_generator.py
M tools/lexer_generator/dfa_optimizer.py
Index: tools/lexer_generator/code_generator.py
diff --git a/tools/lexer_generator/code_generator.py
b/tools/lexer_generator/code_generator.py
index
6d07a603233fe8762146ac5af7697d7b446a14d0..0b73881214370e5cfc62f55cc00f47b7933afec4
100644
--- a/tools/lexer_generator/code_generator.py
+++ b/tools/lexer_generator/code_generator.py
@@ -66,31 +66,29 @@ class CodeGenerator:
transitions = sorted(transitions, cmp)
# map transition keys to disjoint ranges and collect stats
disjoint_keys = []
- eos_transition = None
+ unique_transitions = {}
old_transitions = transitions
transitions = []
(class_keys, distinct_keys, ranges) = (0, 0, 0)
for key, transition_id in old_transitions:
- keys = list(key.range_iter(encoding))
- eos_found = False
- for (t, r) in keys:
+ keys = []
+ for (t, r) in key.range_iter(encoding):
if t == 'CLASS':
class_keys += 1
+ keys.append((t, r))
elif t == 'PRIMARY_RANGE':
distinct_keys += r[1] - r[0] + 1
ranges += 1
+ keys.append((t, r))
elif t == 'UNIQUE':
- assert r == 'eos'
- assert len(keys) == 1
- assert eos_transition == None
- eos_transition = transition_id
- eos_found = True
+ assert r == 'no_match' or r == 'eos'
+ assert r not in unique_transitions
+ unique_transitions[r] = transition_id
else:
raise Exception()
- if not eos_found:
+ if keys:
transitions.append((keys, transition_id))
# eos_transitions is for a followup cl
- assert not eos_transition
return {
'node_number' : None,
'original_node_number' : state.node_number(),
@@ -104,7 +102,7 @@ class CodeGenerator:
'switch_transitions' : [],
'deferred_transitions' : [],
'long_char_transitions' : [],
- 'eos_transition' : eos_transition,
+ 'unique_transitions' : unique_transitions,
# state actions
'entry_action' : entry_action,
'match_action' : match_action,
@@ -248,6 +246,8 @@ class CodeGenerator:
dfa_states.append(current_node)
for (key, node_number) in current_node['transitions']:
CodeGenerator.__reorder(node_number, id_map, dfa_states)
+ for node_number in current_node['unique_transitions'].values():
+ CodeGenerator.__reorder(node_number, id_map, dfa_states)
def __build_dfa_states(self):
dfa_states = []
Index: tools/lexer_generator/dfa_optimizer.py
diff --git a/tools/lexer_generator/dfa_optimizer.py
b/tools/lexer_generator/dfa_optimizer.py
index
5622395776a4a9d5175ee7f58b060633fd711b6d..3f8304fcab3a404de353f43c810e7a8e5297bf70
100644
--- a/tools/lexer_generator/dfa_optimizer.py
+++ b/tools/lexer_generator/dfa_optimizer.py
@@ -66,7 +66,7 @@ class DfaOptimizer(object):
def is_replacement_candidate(state):
action = state.action()
- if not action or action.entry_action() or not action.match_action():
+ if not action or not action.match_action():
return False
if (action.match_action()[0] == 'token' or
action.match_action()[0] == 'harmony_token'):
@@ -116,7 +116,6 @@ class DfaOptimizer(object):
store_states = set([])
# generate a store action to replace an existing action
def replacement_action(old_action, transition_state):
- assert not old_action.entry_action()
assert old_action.match_action()
state_id = name(transition_state)
if old_action.match_action()[0] == 'token':
@@ -138,7 +137,8 @@ class DfaOptimizer(object):
counters['store_harmony_token_and_goto'] += 1
else:
raise Exception(old_action.match_action())
- return Action(None, match_action, old_action.precedence())
+ return Action(old_action.entry_action(), match_action,
+ old_action.precedence())
# map the old state to the new state, with fewer transitions and
# goto actions
def replace_state(state, acc):
@@ -167,6 +167,7 @@ class DfaOptimizer(object):
assert not state_replacements
self.__dfa.visit_all_states(replace_state)
# now patch up all states with stores
+ start_name = name(self.__dfa.start_state())
for state_id in store_states:
old_action = states[state_id]['action']
assert not old_action.entry_action()
@@ -176,7 +177,12 @@ class DfaOptimizer(object):
precedence = old_action.precedence()
states[state_id]['action'] = Action(
entry_action, match_action, precedence)
- start_name = name(self.__dfa.start_state())
+ # The state might be only reachable via gotos; make sure it's
connected in
+ # the state graph by adding a bogus transition from the start state.
This
+ # transition doens't match any character.
+ states[start_name]['transitions'][
+ TransitionKey.unique('no_match')] = state_id
+
if self.__log:
print 'goto_start inserted %s' % counters['goto_start']
print 'store_token_and_goto inserted %s' % (
--
--
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.
