Revision: 18755
Author: [email protected]
Date: Wed Jan 22 14:19:09 2014 UTC
Log: Experimental parser: introduce jump abstractions
[email protected]
BUG=
Review URL: https://codereview.chromium.org/134153014
http://code.google.com/p/v8/source/detail?r=18755
Modified:
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
/branches/experimental/parser/tools/lexer_generator/code_generator.py
=======================================
---
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Wed Jan 22 10:38:15 2014 UTC
+++
/branches/experimental/parser/tools/lexer_generator/code_generator.jinja
Wed Jan 22 14:19:09 2014 UTC
@@ -24,6 +24,11 @@
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+{%- macro jump(id) -%}
+ {%- set node = jump_table[id] -%}
+ goto {{ node[1] ~ '_' ~ node[0] }};
+{%- endmacro -%}
{%- macro do_key(key) -%}
{%- for r in key -%}
@@ -124,10 +129,10 @@
DO_TOKEN(Token::{{value}})
return;
{% elif type == 'goto_start' %}
- goto state_entry_{{value[0]}};
+ {{ jump(value[0]) }}
{% elif type == 'store_token_and_goto' %}
stored_token = Token::{{value[0]}};
- goto after_entry_code_{{value[1]}};
+ {{ jump(value[1]) }}
{% elif type == 'do_stored_token' %}
DO_TOKEN(stored_token)
return;
@@ -149,7 +154,7 @@
} else {
stored_token = Token::{{value[2]}};
}
- goto after_entry_code_{{value[3]}};
+ {{ jump(value[3]) }}
{% elif type == 'octal_number' %}
last_octal_end_ = cursor_;
DO_TOKEN(Token::NUMBER);
@@ -233,38 +238,39 @@
fprintf(stderr, "char at hand is %c (%d)\n", primary_char,
primary_char);
{% endif -%}
- {%- macro do_transition(transition_state_id) -%}
+ {%- macro do_transition(jump_id) -%}
+ {%- set transition_state_id = jump_table[jump_id][0] -%}
{%- set inline_transition =
dfa_states[transition_state_id]['inline'] %}
FORWARD();
{%- if inline_transition %}
{{ do_dfa_state([transition_state_id] + node_number_chain) }}
{% else %}
- goto state_entry_{{transition_state_id}};
+ {{ jump(jump_id) }}
{% endif %}
{%- endmacro -%}
{%- if state['switch_transitions'] -%}
switch(primary_char) {
- {%- for ranges, transition_state_id in state['switch_transitions'] %}
+ {%- for ranges, jump_id in state['switch_transitions'] %}
{%- for r in ranges -%}
{%- for key in range(r[0], r[1] + 1) -%}
case {{key}}:
{% endfor %}
{%- endfor -%}
- {{ do_transition(transition_state_id) }}
+ {{ do_transition(jump_id) }}
{% endfor -%}
}
{%- endif -%}
- {%- for key, transition_state_id in state['if_transitions'] %}
+ {%- for key, jump_id in state['if_transitions'] %}
if ({{do_key(key)}}) { // normal if transition
- {{ do_transition(transition_state_id) }}
+ {{ do_transition(jump_id) }}
}
{% endfor -%}
- {%- for key, transition_state_id in state['deferred_transitions'] %}
+ {%- for key, jump_id in state['deferred_transitions'] %}
if ({{do_key(key)}}) { // deferred transition
- {{ do_transition(transition_state_id) }}
+ {{ do_transition(jump_id) }}
}
{% endfor -%}
@@ -272,9 +278,9 @@
if ({{long_char_check()}}) {
next_.is_onebyte = false;
{{long_char_create()}}
- {%- for key, transition_state_id in state['long_char_transitions'] %}
+ {%- for key, jump_id in state['long_char_transitions'] %}
if ({{do_key(key)}}) { // long_char transition
- {{ do_transition(transition_state_id) }}
+ {{ do_transition(jump_id) }}
}
{% endfor -%}
}
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Wed Jan 22 12:32:46 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Wed Jan 22 14:19:09 2014 UTC
@@ -51,6 +51,9 @@
self.__log = log
self.__inline = inline
self.__switching = switching
+ self.__jump_table = []
+
+ __jump_labels = ['state_entry', 'after_entry_code']
@staticmethod
def __transform_state(encoding, state):
@@ -111,13 +114,14 @@
'distinct_keys' : distinct_keys,
'ranges' : ranges,
# record of which entry points will be needed
- 'entry_points' : {
- 'state_entry' : True,
- 'after_entry_code' : False,
- # 'before_match' : False,
- # 'before_deferred' : False,
- }
+ 'entry_points' : {k : False for k in CodeGenerator.__jump_labels}
}
+
+ def __register_jump(self, node_id, label):
+ assert label in CodeGenerator.__jump_labels
+ state = self.__dfa_states[node_id]['entry_points'][label] = True
+ self.__jump_table.append((node_id, label))
+ return len(self.__jump_table) - 1
def __set_inline(self, count, state):
assert state['inline'] == None
@@ -282,20 +286,36 @@
for state in states:
if not state['match_action']:
continue
- if state['match_action'][0] in mapped_actions:
+ action = state['match_action'][0]
+ if action 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)
- if state['match_action'][0] != 'goto_start':
- states[value[-1]]['entry_points']['after_entry_code'] = True
+ target_id = goto_map[value[-1]]
+ if action != 'goto_start':
state['can_elide_read'] = False
+ label = 'after_entry_code'
else:
- states[value[-1]]['can_elide_read'] = False
+ states[target_id]['can_elide_read'] = False
+ label = 'state_entry'
+ jump_label = self.__register_jump(target_id, label)
+ state['match_action'] = (action, tuple(list(value[:-1]) +
[jump_label]))
- @staticmethod
- def __mark_entry_points(dfa_states):
+ def __rewrite_transitions_to_jumps(self):
+ transition_names = [
+ 'if_transitions',
+ 'switch_transitions',
+ 'deferred_transitions',
+ 'long_char_transitions']
+ def f((key, target_id)):
+ return (key, self.__register_jump(target_id, 'state_entry'))
+ for state in self.__dfa_states:
+ for name in transition_names:
+ state[name] = map(f, state[name])
+
+ def __mark_entry_points(self):
+ # mark the entry point in case there are implicit jumps to it
+ self.__dfa_states[0]['entry_points']['state_entry'] = True
# inlined states can write no labels
- for state in dfa_states:
+ for state in self.__dfa_states:
entry_points = state['entry_points']
if state['inline']:
for k in entry_points.keys():
@@ -304,16 +324,7 @@
def process(self):
self.__build_dfa_states()
- self.__rewrite_gotos()
-
dfa_states = self.__dfa_states
- # set nodes to inline
- if self.__inline:
- inlined = reduce(self.__set_inline, dfa_states, 0)
- if self.__log:
- print "%s states inlined" % inlined
- elif self.__log:
- print "no inlining"
# split transitions
switched = reduce(self.__split_transitions, dfa_states, 0)
if self.__log:
@@ -321,8 +332,19 @@
# rewrite deferred transitions
for state in dfa_states:
self.__rewrite_deferred_transitions(state)
+ # rewrite gotos
+ self.__rewrite_gotos()
+ # rewrite transitions to use jumps
+ self.__rewrite_transitions_to_jumps()
+ # set nodes to inline
+ if self.__inline:
+ inlined = reduce(self.__set_inline, dfa_states, 0)
+ if self.__log:
+ print "%s states inlined" % inlined
+ elif self.__log:
+ print "no inlining"
# mark all the entry points that will be used
- self.__mark_entry_points(dfa_states)
+ self.__mark_entry_points()
default_action = self.__default_action
assert(default_action and default_action.match_action())
@@ -343,6 +365,7 @@
debug_print = self.__debug_print,
default_action = default_action,
dfa_states = dfa_states,
+ jump_table = self.__jump_table,
encoding = encoding.name(),
char_type = char_type,
upper_bound = encoding.primary_range()[1])
--
--
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.
