Revision: 19032
Author: [email protected]
Date: Mon Feb 3 15:08:36 2014 UTC
Log: Experimental parser: use sentinal values for actions
[email protected]
BUG=
Review URL: https://codereview.chromium.org/152823002
http://code.google.com/p/v8/source/detail?r=19032
Modified:
/branches/experimental/parser/tools/lexer_generator/automaton.py
/branches/experimental/parser/tools/lexer_generator/code_generator.py
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
/branches/experimental/parser/tools/lexer_generator/lexer_test.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
/branches/experimental/parser/tools/lexer_generator/rule_parser.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/automaton.py Mon
Feb 3 14:12:24 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/automaton.py Mon
Feb 3 15:08:36 2014 UTC
@@ -34,6 +34,14 @@
f(a,b,c) would be represented as ('f', a, b, c) where
a, b, and c are strings or Terms.'''
+ __empty_term = None
+
+ @staticmethod
+ def empty_term():
+ if Term.__empty_term == None:
+ Term.__empty_term = Term('')
+ return Term.__empty_term
+
@staticmethod
def __verify_string(v):
assert (not ',' in v) and (not '(' in v)
@@ -41,7 +49,10 @@
def __init__(self, name, *args):
assert type(name) == StringType
self.__verify_string(name)
+ if not name:
+ assert not args, 'empty term must not have args'
for v in args:
+ assert v, 'args must be non empty'
if type(v) == StringType:
self.__verify_string(v)
else:
@@ -58,9 +69,11 @@
def __hash__(self):
return hash(self.__tuple)
+ def __nonzero__(self):
+ return bool(self.__tuple[0])
+
def __eq__(self, other):
- return (isinstance(other, self.__class__) and
- self.__tuple == other.__tuple)
+ return (isinstance(other, self.__class__) and self.__tuple ==
other.__tuple)
def __str__(self):
if self.__str == None:
@@ -69,9 +82,17 @@
class Action(object):
+ __empty_action = None
+
+ @staticmethod
+ def empty_action():
+ if Action.__empty_action == None:
+ Action.__empty_action = Action(Term.empty_term(), Term.empty_term())
+ return Action.__empty_action
+
@staticmethod
def dominant_action(state_set):
- action = None
+ action = Action.empty_action()
for state in state_set:
if not state.action():
continue
@@ -86,10 +107,7 @@
def __init__(self, entry_action, match_action, precedence = -1):
for action in [entry_action, match_action]:
- if action == None:
- continue
assert isinstance(action, Term)
- assert entry_action or match_action
self.__entry_action = entry_action
self.__match_action = match_action
self.__precedence = precedence
@@ -103,6 +121,9 @@
def precedence(self):
return self.__precedence
+ def __nonzero__(self):
+ return bool(self.__entry_action) or bool(self.__match_action)
+
def __hash__(self):
return hash((self.__entry_action, self.__match_action))
@@ -114,10 +135,7 @@
def __str__(self):
parts = []
for action in [self.__entry_action, self.__match_action]:
- part = ""
- if action:
- part += str(action)
- parts.append(part)
+ parts.append('' if not action else str(action))
return "action< %s >" % " | ".join(parts)
class AutomatonState(object):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/code_generator.py
Mon Feb 3 14:12:24 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/code_generator.py
Mon Feb 3 15:08:36 2014 UTC
@@ -61,8 +61,8 @@
def __transform_state(encoding, state):
# action data
action = state.action()
- entry_action = None if not action else action.entry_action()
- match_action = None if not action else action.match_action()
+ entry_action = action.entry_action()
+ match_action = action.match_action()
# generate ordered transitions
transitions = map(lambda (k, v) : (k, v.node_number()),
state.transitions().items())
@@ -297,8 +297,7 @@
goto_map = {}
states = self.__dfa_states
for state in states:
- if (state['match_action'] and
- state['match_action'].name() == 'do_stored_token'):
+ if (state['match_action'].name() == 'do_stored_token'):
assert not state['match_action'].args()[0] in goto_map
goto_map[state['match_action'].args()[0]] = state['node_number']
mapped_actions = set([
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Thu Jan 16
12:05:01 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Mon Feb 3
15:08:36 2014 UTC
@@ -36,6 +36,7 @@
self.__name = name
self.__transitions = {}
self.__action = action
+ assert isinstance(action, Action)
def transitions_to_multiple_states(self):
return False
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Mon Feb 3 14:12:24 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa_optimizer.py
Mon Feb 3 15:08:36 2014 UTC
@@ -172,13 +172,8 @@
dfa.visit_all_states(build_incoming_transitions)
def is_replacement_candidate(state):
- action = state.action()
- if not action or not action.match_action():
- return False
- if (action.match_action().name() == 'token' or
- action.match_action().name() == 'harmony_token'):
- return True
- return False
+ return (state.action().match_action().name() == 'token' or
+ state.action().match_action().name() == 'harmony_token')
replacements = {}
for state, incoming in incoming_transitions.items():
@@ -241,7 +236,8 @@
counters['store_harmony_token_and_goto'] += 1
else:
raise Exception(old_action.match_action())
- return Action(old_action.entry_action(), match_action,
+ 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
=======================================
--- /branches/experimental/parser/tools/lexer_generator/lexer_test.py Mon
Feb 3 14:12:24 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/lexer_test.py Mon
Feb 3 15:08:36 2014 UTC
@@ -32,8 +32,9 @@
class LexerTestCase(unittest.TestCase):
def __verify_action_stream(self, rules, string, expected):
- expected = map(lambda (action, s) : (Action(None, Term(action)), s),
- expected)
+ expected = map(lambda (action, s) : (
+ Action(Term.empty_term(), Term(action)), s),
+ expected)
rule_processor = RuleProcessor.parse(rules, 'latin1')
automata = rule_processor.default_automata()
for automaton in [automata.nfa(), automata.dfa(),
automata.minimal_dfa()]:
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Mon Jan 13
13:22:39 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Mon Feb 3
15:08:36 2014 UTC
@@ -35,7 +35,7 @@
self.__transitions = {}
self.__unclosed = set()
self.__epsilon_closure = None
- self.__action = None
+ self.__action = Action.empty_action()
def transitions_to_multiple_states(self):
return True
@@ -55,6 +55,7 @@
def set_action(self, action):
assert not self.is_closed()
assert not self.__action
+ assert isinstance(action, Action)
self.__action = action
def transitions(self):
=======================================
--- /branches/experimental/parser/tools/lexer_generator/rule_parser.py Mon
Feb 3 14:12:24 2014 UTC
+++ /branches/experimental/parser/tools/lexer_generator/rule_parser.py Mon
Feb 3 15:08:36 2014 UTC
@@ -86,7 +86,7 @@
assert state.current_state
if not state.current_state in state.rules:
state.rules[state.current_state] = {
- 'default_action': None,
+ 'default_action': Term.empty_term(),
'uniques' : {},
'regex' : []
}
@@ -112,7 +112,8 @@
if p[1] == 'default_action':
assert self.__state.current_state == 'default'
assert not rules['default_action']
- rules['default_action'] = action
+ assert not entry_action
+ rules['default_action'] = match_action
elif p[1] == 'eos' or p[1] == 'catch_all':
assert p[1] not in rules['uniques']
rules['uniques'][p[1]] = True
@@ -127,16 +128,16 @@
def p_default_action(self, p):
'default_action : ACTION_OPEN identifier_action ACTION_CLOSE'
- p[0] = (None, p[2], None)
+ p[0] = (Term.empty_term(), p[2], None)
def p_eos(self, p):
'eos : ACTION_OPEN identifier_action ACTION_CLOSE'
- p[0] = (None, p[2], None)
+ p[0] = (Term.empty_term(), p[2], None)
def p_maybe_identifier_action(self, p):
'''maybe_identifier_action : identifier_action
| empty'''
- p[0] = p[1]
+ p[0] = p[1] if p[1] else Term.empty_term()
def p_maybe_transition(self, p):
'''maybe_transition : IDENTIFIER
@@ -313,10 +314,10 @@
if not transition:
pass
elif transition == 'continue':
- assert not subgraph == 'default'
+ assert not subgraph == 'default', 'unimplemented'
graph = NfaBuilder.add_continue(graph)
else:
- assert subgraph == 'default'
+ assert subgraph == 'default', 'unimplemented'
graph = NfaBuilder.join_subgraph(
graph, transition, rule_map[transition])
graphs.append(graph)
@@ -333,4 +334,4 @@
self.__rule_trees[rule_name] = graph
# process default_action
default_action = parser_state.rules['default']['default_action']
- self.default_action = Action(None, default_action[1]) if
default_action else None
+ self.default_action = Action(Term.empty_term(), default_action)
--
--
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.
