Revision: 17549
Author: [email protected]
Date: Thu Nov 7 09:58:01 2013 UTC
Log: Experimental parser: subclass for common code
[email protected]
BUG=
Review URL: https://codereview.chromium.org/63863004
http://code.google.com/p/v8/source/detail?r=17549
Added:
/branches/experimental/parser/tools/lexer_generator/automaton.py
Modified:
/branches/experimental/parser/tools/lexer_generator/dfa.py
/branches/experimental/parser/tools/lexer_generator/nfa.py
=======================================
--- /dev/null
+++ /branches/experimental/parser/tools/lexer_generator/automaton.py Thu
Nov 7 09:58:01 2013 UTC
@@ -0,0 +1,97 @@
+# Copyright 2013 the V8 project authors. All rights reserved.
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+# * Redistributions in binary form must reproduce the above
+# copyright notice, this list of conditions and the following
+# disclaimer in the documentation and/or other materials provided
+# with the distribution.
+# * Neither the name of Google Inc. nor the names of its
+# contributors may be used to endorse or promote products derived
+# from this software without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+# 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.
+
+from types import TupleType
+from transition_keys import TransitionKey
+
+class Action(object):
+ pass
+
+class AutomatonState(object):
+
+ def __init__(self, node_number):
+ self.__node_number = node_number
+
+ def node_number(self):
+ return self.__node_number
+
+class Automaton(object):
+
+ @staticmethod
+ def visit_edges(edge, compute_next_edge, visitor, state):
+ visited = set()
+ while edge:
+ f = lambda (next_edge, state), node: (
+ next_edge | compute_next_edge(node),
+ visitor(node, state))
+ (next_edge, state) = reduce(f, edge, (set(), state))
+ visited |= edge
+ edge = next_edge - visited
+ return state
+
+ @staticmethod
+ def generate_dot(start_node, terminal_set, edge_iterator):
+
+ def f(node, node_content):
+ for key, values in node.transitions().items():
+ if key == TransitionKey.epsilon():
+ key = "ε"
+ key = str(key).replace('\\', '\\\\')
+ # TODO pass this action as parameter
+ if type(values) == TupleType:
+ values = [values]
+ for (state, action) in values:
+ if action:
+ node_content.append(
+ " S_%s -> S_%s [ label = \"%s {%s} -> %s\" ];" %
+ (node.node_number(), state.node_number(), key, action[1],
+ action[2]))
+ else:
+ node_content.append(
+ " S_%s -> S_%s [ label = \"%s\" ];" %
+ (node.node_number(), state.node_number(), key))
+ return node_content
+
+ node_content = edge_iterator(f, [])
+ terminals = ["S_%d;" % x.node_number() for x in terminal_set]
+ start_number = start_node.node_number()
+ start_shape = "circle"
+ if start_node in terminal_set:
+ start_shape = "doublecircle"
+
+ return '''
+digraph finite_state_machine {
+ rankdir=LR;
+ node [shape = %s, style=filled, bgcolor=lightgrey]; S_%s
+ node [shape = doublecircle, style=unfilled]; %s
+ node [shape = circle];
+%s
+}
+ ''' % (start_shape,
+ start_number,
+ " ".join(terminals),
+ "\n".join(node_content))
=======================================
--- /branches/experimental/parser/tools/lexer_generator/dfa.py Thu Nov 7
09:48:54 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/dfa.py Thu Nov 7
09:58:01 2013 UTC
@@ -25,22 +25,20 @@
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+from automaton import *
from nfa import Nfa
from transition_keys import TransitionKey
-class DfaState:
+class DfaState(AutomatonState):
def __init__(self, name, node_number):
+ super(DfaState, self).__init__(node_number)
self.__name = name
- self.__node_number = node_number
self.__transitions = {}
def name(self):
return self.__name
- def node_number(self):
- return self.__node_number
-
def add_transition(self, key, action, state):
assert not self.__transitions.has_key(key)
self.__transitions[key] = (state, action)
@@ -48,9 +46,10 @@
def transitions(self):
return self.__transitions
-class Dfa:
+class Dfa(Automaton):
def __init__(self, start_name, mapping):
+ super(Dfa, self).__init__()
self.__terminal_set = set()
name_map = {}
action_map = {}
@@ -79,20 +78,6 @@
self.__start = name_map[start_name]
assert self.__terminal_set
- @staticmethod
- def __visit_edges(start, visitor, state):
- edge = set([start])
- visited = set()
- first = lambda v: [x[0] for x in v]
- while edge:
- f = lambda (next_edge, state), node: (
- next_edge | set(first(node.transitions().values())),
- visitor(node, state))
- (next_edge, state) = reduce(f, edge, (set(), state))
- visited |= edge
- edge = next_edge - visited
- return state
-
def collect_actions(self, string):
state = self.__start
for c in string:
@@ -113,38 +98,12 @@
actions = list(self.collect_actions(string))
return actions and actions[-1][0] == 'TERMINATE'
- def to_dot(self):
+ def __visit_all_edges(self, visitor, state):
+ edge = set([self.__start])
+ first = lambda v: set([x[0] for x in v])
+ next_edge = lambda node: first(node.transitions().values())
+ return self.visit_edges(edge, next_edge, visitor, state)
- def f(node, node_content):
- for key, (state, action) in node.transitions().items():
- key = str(key).replace('\\', '\\\\')
- if action:
- node_content.append(
- " S_%s -> S_%s [ label = \"%s {%s} -> %s\" ];" %
- (node.node_number(), state.node_number(), key, action[1],
- action[2]))
- else:
- node_content.append(
- " S_%s -> S_%s [ label = \"%s\" ];" %
- (node.node_number(), state.node_number(), key))
- return node_content
-
- node_content = self.__visit_edges(self.__start, f, [])
- terminals = ["S_%d;" % x.node_number() for x in self.__terminal_set]
- start_number = self.__start.node_number()
- start_shape = "circle"
- if self.__start in self.__terminal_set:
- start_shape = "doublecircle"
-
- return '''
-digraph finite_state_machine {
- rankdir=LR;
- node [shape = %s, style=filled, bgcolor=lightgrey]; S_%s
- node [shape = doublecircle, style=unfilled]; %s
- node [shape = circle];
-%s
-}
- ''' % (start_shape,
- start_number,
- " ".join(terminals),
- "\n".join(node_content))
+ def to_dot(self):
+ iterator = lambda visitor, state: self.__visit_all_edges(visitor,
state)
+ return self.generate_dot(self.__start, self.__terminal_set, iterator)
=======================================
--- /branches/experimental/parser/tools/lexer_generator/nfa.py Thu Nov 7
09:48:54 2013 UTC
+++ /branches/experimental/parser/tools/lexer_generator/nfa.py Thu Nov 7
09:58:01 2013 UTC
@@ -27,20 +27,18 @@
from types import TupleType
from transition_keys import TransitionKey
+from automaton import *
from inspect import getmembers
-class NfaState:
+class NfaState(AutomatonState):
def __init__(self, node_number):
+ super(NfaState, self).__init__(node_number)
self.__transitions = {}
self.__unclosed = set()
- self.__node_number = node_number
self.__epsilon_closure = None
self.__transition_action = None
- def node_number(self):
- return self.__node_number
-
def epsilon_closure(self):
return self.__epsilon_closure
@@ -109,7 +107,7 @@
return self.__matches(lambda k, v : k.matches_key(v), value)
def __str__(self):
- return "NfaState(" + str(self.__node_number) + ")"
+ return "NfaState(" + str(self.node_number()) + ")"
@staticmethod
def gather_transition_keys(state_set):
@@ -255,30 +253,19 @@
def apply_modifier(modifier, graph):
return (NfaBuilder.__modifer_map[modifier], graph)
-class Nfa:
+class Nfa(Automaton):
def __init__(self, start, end, nodes_created):
+ super(Nfa, self).__init__()
self.__start = start
self.__end = end
self.__epsilon_closure_computed = False
self.__verify(nodes_created)
- @staticmethod
- def __visit_edges(edge, compute_next_edge, visitor, state):
- visited = set()
- while edge:
- f = lambda (next_edge, state), node: (
- next_edge | compute_next_edge(node),
- visitor(node, state))
- (next_edge, state) = reduce(f, edge, (set(), state))
- visited |= edge
- edge = next_edge - visited
- return state
-
def __visit_all_edges(self, visitor, state):
edge = set([self.__start])
next_edge = lambda node: node.next_states(lambda x : True)
- return Nfa.__visit_edges(edge, next_edge, visitor, state)
+ return self.visit_edges(edge, next_edge, visitor, state)
def __verify(self, nodes_created):
def f(node, node_list):
@@ -299,7 +286,7 @@
is_epsilon = lambda k: k == TransitionKey.epsilon()
next_edge = lambda node : node.next_states(is_epsilon)
edge = next_edge(node)
- closure = Nfa.__visit_edges(edge, next_edge, inner, set())
+ closure = self.visit_edges(edge, next_edge, inner, set())
node.set_epsilon_closure(closure)
self.__visit_all_edges(outer, None)
@@ -362,34 +349,5 @@
return (start_name, dfa_nodes)
def to_dot(self):
-
- def f(node, node_content):
- for key, values in node.transitions().items():
- if key == TransitionKey.epsilon():
- key = "ε"
- key = str(key).replace('\\', '\\\\')
- for value in values:
- if value[1]:
- node_content.append(
- " S_%d -> S_%d [ label = \"%s {%s} -> %s\" ];" %
- (node.node_number(), value[0].node_number(), key,
value[1][1],
- value[1][2]))
- else:
- node_content.append(
- " S_%d -> S_%d [ label = \"%s\" ];" %
- (node.node_number(), value[0].node_number(), key))
- return node_content
-
- node_content = self.__visit_all_edges(f, [])
-
- return '''
-digraph finite_state_machine {
- rankdir=LR;
- node [shape = circle, style=filled, bgcolor=lightgrey]; S_%s
- node [shape = doublecircle, style=unfilled]; S_%s
- node [shape = circle];
-%s
-}
- ''' % (self.__start.node_number(),
- self.__end.node_number(),
- "\n".join(node_content))
+ iterator = lambda visitor, state: self.__visit_all_edges(visitor,
state)
+ return self.generate_dot(self.__start, set([self.__end]), iterator)
--
--
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.
