Reviewers: marja,
Message:
Committed patchset #1 manually as r19032 (presubmit successful).
Description:
Experimental parser: use sentinal values for actions
[email protected]
BUG=
Committed: https://code.google.com/p/v8/source/detail?r=19032
Please review this at https://codereview.chromium.org/152823002/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+50, -33 lines):
M tools/lexer_generator/automaton.py
M tools/lexer_generator/code_generator.py
M tools/lexer_generator/dfa.py
M tools/lexer_generator/dfa_optimizer.py
M tools/lexer_generator/lexer_test.py
M tools/lexer_generator/nfa.py
M tools/lexer_generator/rule_parser.py
Index: tools/lexer_generator/automaton.py
diff --git a/tools/lexer_generator/automaton.py
b/tools/lexer_generator/automaton.py
index
90213cbb3f88138643adb762f4aec8256fb863bd..ff355d1102b5a45102d2810d334ef0f40c50b542
100644
--- a/tools/lexer_generator/automaton.py
+++ b/tools/lexer_generator/automaton.py
@@ -34,6 +34,14 @@ class Term(object):
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 @@ class Term(object):
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 @@ class Term(object):
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 Term(object):
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 @@ class Action(object):
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 @@ class Action(object):
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 @@ class Action(object):
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):
Index: tools/lexer_generator/code_generator.py
diff --git a/tools/lexer_generator/code_generator.py
b/tools/lexer_generator/code_generator.py
index
6bc44eb8da20905171050a6d350727dd3ed122da..96a26f473d52c1024265af92d0bbafc934f49d18
100644
--- a/tools/lexer_generator/code_generator.py
+++ b/tools/lexer_generator/code_generator.py
@@ -61,8 +61,8 @@ class CodeGenerator:
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 @@ class CodeGenerator:
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([
Index: tools/lexer_generator/dfa.py
diff --git a/tools/lexer_generator/dfa.py b/tools/lexer_generator/dfa.py
index
a8f29cdbd6a2389fe79e49e68dadd8330beae9b0..648529428d1adf7a3dae5ffee2f95836f9a917a1
100644
--- a/tools/lexer_generator/dfa.py
+++ b/tools/lexer_generator/dfa.py
@@ -36,6 +36,7 @@ class DfaState(AutomatonState):
self.__name = name
self.__transitions = {}
self.__action = action
+ assert isinstance(action, Action)
def transitions_to_multiple_states(self):
return False
Index: tools/lexer_generator/dfa_optimizer.py
diff --git a/tools/lexer_generator/dfa_optimizer.py
b/tools/lexer_generator/dfa_optimizer.py
index
99922120d5d56e80347276a41aeda853f79d6189..115ed1c56fb772e50dde5a85e7387bb43e2ed8aa
100644
--- a/tools/lexer_generator/dfa_optimizer.py
+++ b/tools/lexer_generator/dfa_optimizer.py
@@ -172,13 +172,8 @@ class DfaOptimizer(object):
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 @@ class DfaOptimizer(object):
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
Index: tools/lexer_generator/lexer_test.py
diff --git a/tools/lexer_generator/lexer_test.py
b/tools/lexer_generator/lexer_test.py
index
386de463205cfda8815ed33e91d3e23fead5c843..38af54258c4b199b64665dbde3d068bacec60829
100644
--- a/tools/lexer_generator/lexer_test.py
+++ b/tools/lexer_generator/lexer_test.py
@@ -32,8 +32,9 @@ from rule_parser import RuleProcessor
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()]:
Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index
fd791864b8a379d6074a70b8663d65343fce550b..2367630b76b711cea0725b5df5e1083e276f3ca8
100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -35,7 +35,7 @@ class NfaState(AutomatonState):
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 @@ class NfaState(AutomatonState):
def set_action(self, action):
assert not self.is_closed()
assert not self.__action
+ assert isinstance(action, Action)
self.__action = action
def transitions(self):
Index: tools/lexer_generator/rule_parser.py
diff --git a/tools/lexer_generator/rule_parser.py
b/tools/lexer_generator/rule_parser.py
index
1884df567cb49461d13415c2ab322c9df7a40e68..dc47f0e25ac4cf668a1727c55b237ae327139dd4
100644
--- a/tools/lexer_generator/rule_parser.py
+++ b/tools/lexer_generator/rule_parser.py
@@ -86,7 +86,7 @@ class RuleParser:
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 @@ class RuleParser:
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 @@ class RuleParser:
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 @@ class RuleProcessor(object):
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 @@ class RuleProcessor(object):
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.
