Revision: 17576
Author: [email protected]
Date: Fri Nov 8 07:29:01 2013 UTC
Log: Experimental parser: some support for adding subraphs
[email protected]
BUG=
Review URL: https://codereview.chromium.org/66293002
http://code.google.com/p/v8/source/detail?r=17576
Modified:
/branches/experimental/parser/tools/lexer_generator/generator.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
=======================================
--- /branches/experimental/parser/tools/lexer_generator/generator.py Thu
Nov 7 12:03:35 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/generator.py Fri
Nov 8 07:29:01 2013 UTC
@@ -80,12 +80,34 @@
builder = NfaBuilder()
builder.set_character_classes(parser_state.character_classes)
assert 'default' in parser_state.rules
- for k, v in parser_state.rules.items():
+ def process(k, v):
assert 'default' in v
graphs = []
for (graph, action) in v['regex']:
- graphs.append(NfaBuilder.add_action(graph, action))
- rule_map[k] = NfaBuilder.or_graphs(graphs)
+ (precedence, code, transition) = action
+ if code:
+ graph = NfaBuilder.add_action(graph, (precedence, code, None))
+ if transition == 'continue':
+ graph = NfaBuilder.add_continue(graph)
+ elif (transition == 'break' or
+ transition == 'terminate' or
+ transition == 'terminate_illegal'):
+ pass
+ else:
+ assert k == 'default'
+ graph = NfaBuilder.join_subgraph(graph, transition,
rule_map[transition])
+ graphs.append(graph)
+ graph = NfaBuilder.or_graphs(graphs)
+ # merge default action
+ (precedence, code, transition) = v['default'][1]
+ assert transition == 'continue' or transition == 'break'
+ if code:
+ graph = NfaBuilder.add_incoming_action(graph, (precedence, code,
None))
+ rule_map[k] = graph
+ for k, v in parser_state.rules.items():
+ if k == 'default': continue
+ process(k, v)
+ process('default', parser_state.rules['default'])
html_data = []
for rule_name, graph in rule_map.items():
nfa = builder.nfa(graph)
@@ -98,11 +120,12 @@
parser = argparse.ArgumentParser()
parser.add_argument('--html')
+ parser.add_argument('--re', default='src/lexer/lexer_py.re')
args = parser.parse_args()
- re_file = 'src/lexer/lexer_py.re'
-
+ re_file = args.re
parser_state = RuleParserState()
+ print "parsing %s" % re_file
with open(re_file, 'r') as f:
RuleParser.parse(f.read(), parser_state)
html_data = process_rules(parser_state)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Thu Nov 7
12:55:33 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Fri Nov 8
07:29:01 2013 UTC
@@ -88,8 +88,7 @@
unclosed, self.__unclosed = self.__unclosed, None
action, self.__transition_action = self.__transition_action, None
if end == None:
- assert not unclosed
- assert not action
+ assert not unclosed and not action
return
for key in unclosed:
self.__add_transition(key, action, end)
@@ -121,6 +120,7 @@
self.__operation_map = {}
self.__members = getmembers(self)
self.__character_classes = {}
+ self.__states = []
def set_character_classes(self, classes):
self.__character_classes = classes
@@ -205,21 +205,42 @@
return self.__key_state(TransitionKey.any())
def __action(self, graph):
- result = self.__process(graph[1])
- for end in result[1]:
- end.set_transition_action(graph[2])
- return result
+ incoming = graph[3]
+ (start, ends) = self.__process(graph[1])
+ action = graph[2]
+ if incoming:
+ new_start = self.__new_state()
+ new_start.set_transition_action(action)
+ new_start.close(start)
+ start = new_start
+ else:
+ for end in ends:
+ end.set_transition_action(action)
+ return (start, ends)
def __continue(self, graph):
(start, ends) = self.__process(graph[1])
- if not self.__start_node:
- self.__start_node = self.__new_state()
+ state = self.__peek_state()
+ if not state['start_node']:
+ state['start_node'] = self.__new_state()
end = self.__new_state()
self.__patch_ends(ends, end)
ends = [end]
- end.add_epsilon_transition(self.__start_node)
+ end.add_epsilon_transition(state['start_node'])
return (start, ends)
+ def __join(self, graph):
+ (graph, name, subgraph) = graph[1:]
+ subgraphs = self.__peek_state()['subgraphs']
+ if not name in subgraphs:
+ subgraphs[name] = self.__nfa(subgraph)
+ (subgraph_start, subgraph_end, nodes_in_subgraph) = subgraphs[name]
+ (start, ends) = self.__process(graph)
+ self.__patch_ends(ends, subgraph_start)
+ end = self.__new_state()
+ subgraph_end.add_epsilon_transition(end)
+ return (start, [end])
+
def __process(self, graph):
assert type(graph) == TupleType
method = "_NfaBuilder__" + graph[0].lower()
@@ -233,26 +254,53 @@
for end in ends:
end.close(new_end)
- def nfa(self, graph):
- self.__start_node = None
+ def __push_state(self):
+ self.__states.append({
+ 'start_node' : None,
+ 'subgraphs' : {},
+ })
+
+ def __pop_state(self):
+ return self.__states.pop()
+
+ def __peek_state(self):
+ return self.__states[len(self.__states) - 1]
+
+ def __nfa(self, graph):
start_node_number = self.__node_number
+ self.__push_state()
(start, ends) = self.__process(graph)
- if self.__start_node:
- self.__start_node.close(start)
- start = self.__start_node
+ state = self.__pop_state()
+ if state['start_node']:
+ state['start_node'].close(start)
+ start = state['start_node']
+ for k, subgraph in state['subgraphs'].items():
+ subgraph[1].close(None)
end = self.__new_state()
self.__patch_ends(ends, end)
+ return (start, end, self.__node_number - start_node_number)
+
+ def nfa(self, graph):
+ (start, end, nodes_created) = self.__nfa(graph)
end.close(None)
- return Nfa(start, end, self.__node_number - start_node_number)
+ return Nfa(start, end, nodes_created)
@staticmethod
def add_action(graph, action):
- return ('ACTION', graph, action)
+ return ('ACTION', graph, action, False)
+
+ @staticmethod
+ def add_incoming_action(graph, action):
+ return ('ACTION', graph, action, True)
@staticmethod
def add_continue(graph):
return ('CONTINUE', graph)
+ @staticmethod
+ def join_subgraph(graph, name, subgraph):
+ return ('JOIN', graph, name, subgraph)
+
@staticmethod
def or_graphs(graphs):
return reduce(lambda acc, g: ('OR', acc, g), graphs)
--
--
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.
