Reviewers: dcarney,
Message:
ptal
Description:
Experimental lexer generator: transfer actions across epsilon transitions
correctly when constructing the dfa.
This produces a reasonable nfa (with actions) with the following grammar:
<default>
/[a-z]+/ { ID } <<break>>
"break" { PUSH_TOKEN(BREAK); } <<break>>
BUG=
Please review this at https://codereview.chromium.org/62223002/
SVN Base: https://v8.googlecode.com/svn/branches/experimental/parser
Affected files (+19, -8 lines):
M tools/lexer_generator/generator.py
M tools/lexer_generator/nfa.py
M tools/lexer_generator/rule_parser.py
Index: tools/lexer_generator/generator.py
diff --git a/tools/lexer_generator/generator.py
b/tools/lexer_generator/generator.py
index
9b1de46b418ae7b71f00e8a4f49c9e19ed0e93ef..3615d2852e9c686e7fd668fef32e84ff54277275
100644
--- a/tools/lexer_generator/generator.py
+++ b/tools/lexer_generator/generator.py
@@ -80,9 +80,8 @@ def process_rules(parser_state):
builder.set_character_classes(parser_state.character_classes)
for k, v in parser_state.rules.items():
graphs = []
- for (graph, code, action) in v['regex']:
- # graphs.append(NfaBuilder.add_action(graph, (action, identifier)))
- graphs.append(graph)
+ for (graph, code, action, precedence) in v['regex']:
+ graphs.append(NfaBuilder.add_action(graph, (code, action,
precedence)))
rule_map[k] = builder.nfa(NfaBuilder.or_graphs(graphs))
html_data = []
for rule_name, nfa in rule_map.items():
Index: tools/lexer_generator/nfa.py
diff --git a/tools/lexer_generator/nfa.py b/tools/lexer_generator/nfa.py
index
b3f013d983924f8a6ed948cb0a96ee42ebafe073..a1447343671aa06e80a7a9a204b8e56fb917f1fa
100644
--- a/tools/lexer_generator/nfa.py
+++ b/tools/lexer_generator/nfa.py
@@ -333,14 +333,24 @@ class Nfa:
f = lambda acc, state: acc | state.key_matches(key)
transitions = reduce(f, nfa_state_set, set())
match_states = set()
- actions = set()
+ actions = []
for (state, action) in transitions:
match_states.add(state)
if action:
- actions.add(action)
+ actions.append((action[2], action[0], action[1]))
+
+ # Pull in actions which can be taken with an epsilon transition
from the
+ # match state.
+ e = TransitionKey.epsilon()
+ if e in state.transitions():
+ for e_trans in state.transitions()[e]:
+ if e_trans[1]:
+ actions.append((e_trans[1][2], e_trans[1][0], e_trans[1][1]))
+
assert len(match_states) == len(transitions)
- assert not actions or len(actions) == 1
- action = iter(actions).next() if actions else None
+
+ actions.sort()
+ action = (actions[0][1], actions[0][2]) if actions else None
transition_state = Nfa.__to_dfa(match_states, dfa_nodes, end_node)
dfa_nodes[name]['transitions'][key] = (transition_state, action)
return name
Index: tools/lexer_generator/rule_parser.py
diff --git a/tools/lexer_generator/rule_parser.py
b/tools/lexer_generator/rule_parser.py
index
215e06df62cb84179ecf807d4990ca804db6e46d..a773d63665ae78a464b768b29348e094c2e71691
100644
--- a/tools/lexer_generator/rule_parser.py
+++ b/tools/lexer_generator/rule_parser.py
@@ -50,6 +50,7 @@ class RuleParser:
def __init__(self):
self.__state = None
+ self.__rule_precedence_counter = 0
def p_statements(self, p):
'statements : aliases rules'
@@ -95,7 +96,8 @@ class RuleParser:
| composite_regex_or_default empty action
| composite_regex_or_default code empty'''
rules = self.__state.rules[self.__state.current_state]
- rule = (p[1], p[2], p[3])
+ rule = (p[1], p[2], p[3], self.__rule_precedence_counter)
+ self.__rule_precedence_counter+=1
if p[1] == 'default':
assert not rules['default']
rules['default'] = rule
--
--
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.
