Revision: 18061
Author: [email protected]
Date: Mon Nov 25 15:42:28 2013 UTC
Log: Experimental parser: simplify goto logic
[email protected]
BUG=
Review URL: https://codereview.chromium.org/85853003
http://code.google.com/p/v8/source/detail?r=18061
Modified:
/branches/experimental/parser/tools/lexer_generator/automaton.py
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
/branches/experimental/parser/tools/lexer_generator/code_generator.py
/branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
/branches/experimental/parser/tools/lexer_generator/rule_parser.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/automaton.py Fri
Nov 22 09:05:23 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/automaton.py Mon
Nov 25 15:42:28 2013 UTC
@@ -80,8 +80,8 @@
part = ""
if action:
part += action[0]
- if action[1] and isinstance(action[1], str):
- part += "(%s)" % action[1]
+ if action[1]:
+ part += "(%s)" % str(action[1])
parts.append(part)
return "action< %s >" % " | ".join(parts)
=======================================
---
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Mon Nov 25 13:39:47 2013 UTC
+++
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Mon Nov 25 15:42:28 2013 UTC
@@ -87,26 +87,30 @@
DO_LINE_TERMINATOR();
{% elif type == 'token' %}
DO_TOKEN(Token::{{value}})
- {% elif type == 'goto' %}
- goto code_after_entry_{{value}};
+ {% elif type == 'goto_start' %}
+ goto code_{{value[0]}};
{% elif type == 'store_token' %}
stored_token = Token::{{value}};
+ {% elif type == 'store_token_and_goto' %}
+ stored_token = Token::{{value[0]}};
+ goto code_after_entry_{{value[1]}};
{% elif type == 'do_stored_token' %}
DO_TOKEN(stored_token)
{% elif type == 'do_token_and_go_forward' %}
DO_TOKEN_AND_GO_FORWARD(Token::{{value}})
{% elif type == 'harmony_token' %}
if (harmony_{{value[0]}}_) {
- DO_TOKEN(Token::{{value[1][0]}});
+ DO_TOKEN(Token::{{value[1]}});
} else {
- DO_TOKEN(Token::{{value[1][1]}});
+ DO_TOKEN(Token::{{value[2]}});
}
- {% elif type == 'store_harmony_token' %}
+ {% elif type == 'store_harmony_token_and_goto' %}
if (harmony_{{value[0]}}_) {
- stored_token = Token::{{value[1][0]}};
+ stored_token = Token::{{value[1]}};
} else {
- stored_token = Token::{{value[1][1]}};
+ stored_token = Token::{{value[2]}};
}
+ goto code_after_entry_{{value[3]}};
{% elif type == 'set_marker' %}
marker_ = cursor_ - {{value}};
{% else %}
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Mon Nov 25 13:28:43 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Mon Nov 25 15:42:28 2013 UTC
@@ -299,9 +299,17 @@
assert not state['match_action'][1] in goto_map
goto_map[state['match_action'][1]] = state['node_number']
state['has_goto_after_entry'] = True
+ mapped_actions = set([
+ 'store_harmony_token_and_goto',
+ 'store_token_and_goto',
+ 'goto_start'])
for state in self.__dfa_states:
- if state['match_action'] and state['match_action'][0] == 'goto':
- state['match_action'] = ('goto',
goto_map[state['match_action'][1]])
+ if not state['match_action']:
+ continue
+ if state['match_action'][0] in mapped_actions:
+ value = state['match_action'][1]
+ value = tuple(list(value[:-1]) + [goto_map[value[-1]]])
+ state['match_action'] = (state['match_action'][0], value)
def process(self):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Mon Nov 25 13:28:43 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Mon Nov 25 15:42:28 2013 UTC
@@ -107,19 +107,38 @@
# perform replacement
states = {}
name = lambda state : str(state.node_number())
- counters = {'removals' : 0, 'gotos' : 0}
+ counters = {
+ 'removals' : 0,
+ 'goto_start' : 0,
+ 'store_token_and_goto' : 0,
+ 'store_harmony_token_and_goto' : 0,
+ }
store_states = set([])
# generate a store action to replace an existing action
- def replacement_action(old_action, match_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':
- entry_action = ('store_token', old_action.match_action()[1])
+ old_token = old_action.match_action()[1]
+ if (transition_state.action().match_action()[0] == 'token' and
+ transition_state.action().match_action()[1] == old_token):
+ # no need to store token
+ match_action = ('goto_start', (state_id,))
+ counters['goto_start'] += 1
+ else:
+ counters['store_token_and_goto'] += 1
+ match_action = ('store_token_and_goto', (old_token, state_id))
elif old_action.match_action()[0] == 'harmony_token':
- entry_action = ('store_harmony_token',
old_action.match_action()[1])
+ match_action = ('store_harmony_token_and_goto',
+ (old_action.match_action()[1][0],
+ old_action.match_action()[1][1],
+ old_action.match_action()[1][2],
+ state_id))
+ counters['store_harmony_token_and_goto'] += 1
else:
raise Exception(old_action.match_action())
- return Action(entry_action, match_action, old_action.precedence())
+ return Action(None, match_action, old_action.precedence())
# map the old state to the new state, with fewer transitions and
# goto actions
def replace_state(state, acc):
@@ -140,10 +159,9 @@
if replacement == None:
counters['removals'] += 1
continue
+ assert replacement == transition_state
# do goto replacement
- counters['gotos'] += 1
- match_action = ('goto', name(transition_state))
- new_state['action'] = replacement_action(state.action(),
match_action)
+ new_state['action'] = replacement_action(state.action(),
replacement)
# will need to patch up transition_state
store_states.add(name(transition_state))
assert not state_replacements
@@ -151,11 +169,20 @@
# now patch up all states with stores
for state_id in store_states:
old_action = states[state_id]['action']
+ assert not old_action.entry_action()
+ assert old_action.match_action()[0] == 'token', 'unimplemented'
+ entry_action = ('store_token', old_action.match_action()[1])
match_action = ('do_stored_token', state_id)
- states[state_id]['action'] = replacement_action(old_action,
match_action)
+ precedence = old_action.precedence()
+ states[state_id]['action'] = Action(
+ entry_action, match_action, precedence)
start_name = name(self.__dfa.start_state())
if self.__log:
- print 'gotos inserted %s' % counters['gotos']
+ print 'goto_start inserted %s' % counters['goto_start']
+ print 'store_token_and_goto inserted %s' % (
+ counters['store_token_and_goto'])
+ print 'store_harmony_token_and_goto %s' % (
+ counters['store_harmony_token_and_goto'])
print 'transitions removed %s' % counters['removals']
print 'do_stored_token actions added %s' % len(store_states)
self.__dfa = Dfa(self.__dfa.encoding(), start_name, states)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/rule_parser.py Mon
Nov 25 12:18:26 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/rule_parser.py Mon
Nov 25 15:42:28 2013 UTC
@@ -134,7 +134,7 @@
def p_action_part(self, p):
'''action_part : code
- | identifier_action'''
+ | identifier_action'''
p[0] = p[1]
def p_maybe_transition(self, p):
@@ -150,7 +150,10 @@
if len(p) == 2 or len(p) == 4:
p[0] = (p[1], None)
elif len(p) == 5:
- p[0] = (p[1], p[3])
+ if len(p[3]) == 1:
+ p[0] = (p[1], p[3][0])
+ else:
+ p[0] = (p[1], p[3])
else:
raise Exception()
@@ -158,9 +161,9 @@
'''action_params : IDENTIFIER
| IDENTIFIER COMMA action_params'''
if len(p) == 2:
- p[0] = p[1]
+ p[0] = (p[1],)
elif len(p) == 4:
- p[0] = (p[1], p[3])
+ p[0] = tuple(([p[1]] + list(p[3])))
else:
raise Exception()
--
--
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.
