summaryrefslogtreecommitdiff
path: root/support/newcommand/spark.py
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/newcommand/spark.py
Initial commit
Diffstat (limited to 'support/newcommand/spark.py')
-rw-r--r--support/newcommand/spark.py566
1 files changed, 566 insertions, 0 deletions
diff --git a/support/newcommand/spark.py b/support/newcommand/spark.py
new file mode 100644
index 0000000000..ffe9b4bf7c
--- /dev/null
+++ b/support/newcommand/spark.py
@@ -0,0 +1,566 @@
+# Copyright (c) 1998-2000 John Aycock
+#
+# Permission is hereby granted, free of charge, to any person obtaining
+# a copy of this software and associated documentation files (the
+# "Software"), to deal in the Software without restriction, including
+# without limitation the rights to use, copy, modify, merge, publish,
+# distribute, sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so, subject to
+# the following conditions:
+#
+# The above copyright notice and this permission notice shall be
+# included in all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+__version__ = 'SPARK-0.6.1'
+
+import re
+import sys
+import string
+
+def _namelist(instance):
+ namelist, namedict, classlist = [], {}, [instance.__class__]
+ for c in classlist:
+ for b in c.__bases__:
+ classlist.append(b)
+ for name in dir(c):
+ if not namedict.has_key(name):
+ namelist.append(name)
+ namedict[name] = 1
+ return namelist
+
+class GenericScanner:
+ def __init__(self):
+ pattern = self.reflect()
+ self.re = re.compile(pattern, re.VERBOSE)
+
+ self.index2func = {}
+ for name, number in self.re.groupindex.items():
+ self.index2func[number-1] = getattr(self, 't_' + name)
+
+ def makeRE(self, name):
+ doc = getattr(self, name).__doc__
+ rv = '(?P<%s>%s)' % (name[2:], doc)
+ return rv
+
+ def reflect(self):
+ rv = []
+ for name in _namelist(self):
+ if name[:2] == 't_' and name != 't_default':
+ rv.append(self.makeRE(name))
+
+ rv.append(self.makeRE('t_default'))
+ return string.join(rv, '|')
+
+ def error(self, s, pos):
+ print "Lexical error at position %s" % pos
+ raise SystemExit
+
+ def tokenize(self, s):
+ pos = 0
+ n = len(s)
+ while pos < n:
+ m = self.re.match(s, pos)
+ if m is None:
+ self.error(s, pos)
+
+ groups = m.groups()
+ for i in range(len(groups)):
+ if groups[i] and self.index2func.has_key(i):
+ self.index2func[i](groups[i])
+ pos = m.end()
+
+ def t_default(self, s):
+ r'( . | \n )+'
+ pass
+
+class GenericParser:
+ def __init__(self, start):
+ self.rules = {}
+ self.rule2func = {}
+ self.rule2name = {}
+ self.collectRules()
+ self.startRule = self.augment(start)
+ self.ruleschanged = 1
+
+ _START = 'START'
+ _EOF = 'EOF'
+
+ #
+ # A hook for GenericASTBuilder and GenericASTMatcher.
+ #
+ def preprocess(self, rule, func): return rule, func
+
+ def addRule(self, doc, func):
+ rules = string.split(doc)
+
+ index = []
+ for i in range(len(rules)):
+ if rules[i] == '::=':
+ index.append(i-1)
+ index.append(len(rules))
+
+ for i in range(len(index)-1):
+ lhs = rules[index[i]]
+ rhs = rules[index[i]+2:index[i+1]]
+ rule = (lhs, tuple(rhs))
+
+ rule, fn = self.preprocess(rule, func)
+
+ if self.rules.has_key(lhs):
+ self.rules[lhs].append(rule)
+ else:
+ self.rules[lhs] = [ rule ]
+ self.rule2func[rule] = fn
+ self.rule2name[rule] = func.__name__[2:]
+ self.ruleschanged = 1
+
+ def collectRules(self):
+ for name in _namelist(self):
+ if name[:2] == 'p_':
+ func = getattr(self, name)
+ doc = func.__doc__
+ self.addRule(doc, func)
+
+ def augment(self, start):
+ #
+ # Tempting though it is, this isn't made into a call
+ # to self.addRule() because the start rule shouldn't
+ # be subject to preprocessing.
+ #
+ startRule = (self._START, ( start, self._EOF ))
+ self.rule2func[startRule] = lambda args: args[0]
+ self.rules[self._START] = [ startRule ]
+ self.rule2name[startRule] = ''
+ return startRule
+
+ def makeFIRST(self):
+ union = {}
+ self.first = {}
+
+ for rulelist in self.rules.values():
+ for lhs, rhs in rulelist:
+ if not self.first.has_key(lhs):
+ self.first[lhs] = {}
+
+ if len(rhs) == 0:
+ self.first[lhs][None] = 1
+ continue
+
+ sym = rhs[0]
+ if not self.rules.has_key(sym):
+ self.first[lhs][sym] = 1
+ else:
+ union[(sym, lhs)] = 1
+ changes = 1
+ while changes:
+ changes = 0
+ for src, dest in union.keys():
+ destlen = len(self.first[dest])
+ self.first[dest].update(self.first[src])
+ if len(self.first[dest]) != destlen:
+ changes = 1
+
+ #
+ # An Earley parser, as per J. Earley, "An Efficient Context-Free
+ # Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley,
+ # "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis,
+ # Carnegie-Mellon University, August 1968, p. 27.
+ #
+
+ def typestring(self, token):
+ return None
+
+ def error(self, token):
+ print "Syntax error at or near `%s' token" % token
+ raise SystemExit
+
+ def parse(self, tokens):
+ tree = {}
+ tokens.append(self._EOF)
+ states = { 0: [ (self.startRule, 0, 0) ] }
+
+ if self.ruleschanged:
+ self.makeFIRST()
+
+ for i in xrange(len(tokens)):
+ states[i+1] = []
+
+ if states[i] == []:
+ break
+ self.buildState(tokens[i], states, i, tree)
+
+ #_dump(tokens, states)
+
+ if i < len(tokens)-1 or states[i+1] != [(self.startRule, 2, 0)]:
+ del tokens[-1]
+ self.error(tokens[i-1])
+ rv = self.buildTree(tokens, tree, ((self.startRule, 2, 0), i+1))
+ del tokens[-1]
+ return rv
+
+ def buildState(self, token, states, i, tree):
+ needsCompletion = {}
+ state = states[i]
+ predicted = {}
+
+ for item in state:
+ rule, pos, parent = item
+ lhs, rhs = rule
+
+ #
+ # A -> a . (completer)
+ #
+ if pos == len(rhs):
+ if len(rhs) == 0:
+ needsCompletion[lhs] = (item, i)
+
+ for pitem in states[parent]:
+ if pitem is item:
+ break
+
+ prule, ppos, pparent = pitem
+ plhs, prhs = prule
+
+ if prhs[ppos:ppos+1] == (lhs,):
+ new = (prule,
+ ppos+1,
+ pparent)
+ if new not in state:
+ state.append(new)
+ tree[(new, i)] = [(item, i)]
+ else:
+ tree[(new, i)].append((item, i))
+ continue
+
+ nextSym = rhs[pos]
+
+ #
+ # A -> a . B (predictor)
+ #
+ if self.rules.has_key(nextSym):
+ #
+ # Work on completer step some more; for rules
+ # with empty RHS, the "parent state" is the
+ # current state we're adding Earley items to,
+ # so the Earley items the completer step needs
+ # may not all be present when it runs.
+ #
+ if needsCompletion.has_key(nextSym):
+ new = (rule, pos+1, parent)
+ olditem_i = needsCompletion[nextSym]
+ if new not in state:
+ state.append(new)
+ tree[(new, i)] = [olditem_i]
+ else:
+ tree[(new, i)].append(olditem_i)
+
+ #
+ # Has this been predicted already?
+ #
+ if predicted.has_key(nextSym):
+ continue
+ predicted[nextSym] = 1
+
+ ttype = token is not self._EOF and \
+ self.typestring(token) or \
+ None
+ if ttype is not None:
+ #
+ # Even smarter predictor, when the
+ # token's type is known. The code is
+ # grungy, but runs pretty fast. Three
+ # cases are looked for: rules with
+ # empty RHS; first symbol on RHS is a
+ # terminal; first symbol on RHS is a
+ # nonterminal (and isn't nullable).
+ #
+ for prule in self.rules[nextSym]:
+ new = (prule, 0, i)
+ prhs = prule[1]
+ if len(prhs) == 0:
+ state.append(new)
+ continue
+ prhs0 = prhs[0]
+ if not self.rules.has_key(prhs0):
+ if prhs0 != ttype:
+ continue
+ else:
+ state.append(new)
+ continue
+ first = self.first[prhs0]
+ if not first.has_key(None) and \
+ not first.has_key(ttype):
+ continue
+ state.append(new)
+ continue
+
+ for prule in self.rules[nextSym]:
+ #
+ # Smarter predictor, as per Grune &
+ # Jacobs' _Parsing Techniques_. Not
+ # as good as FIRST sets though.
+ #
+ prhs = prule[1]
+ if len(prhs) > 0 and \
+ not self.rules.has_key(prhs[0]) and \
+ token != prhs[0]:
+ continue
+ state.append((prule, 0, i))
+
+ #
+ # A -> a . c (scanner)
+ #
+ elif token == nextSym:
+ #assert new not in states[i+1]
+ states[i+1].append((rule, pos+1, parent))
+
+ def buildTree(self, tokens, tree, root):
+ stack = []
+ self.buildTree_r(stack, tokens, -1, tree, root)
+ return stack[0]
+
+ def buildTree_r(self, stack, tokens, tokpos, tree, root):
+ (rule, pos, parent), state = root
+
+ while pos > 0:
+ want = ((rule, pos, parent), state)
+ if not tree.has_key(want):
+ #
+ # Since pos > 0, it didn't come from closure,
+ # and if it isn't in tree[], then there must
+ # be a terminal symbol to the left of the dot.
+ # (It must be from a "scanner" step.)
+ #
+ pos = pos - 1
+ state = state - 1
+ stack.insert(0, tokens[tokpos])
+ tokpos = tokpos - 1
+ else:
+ #
+ # There's a NT to the left of the dot.
+ # Follow the tree pointer recursively (>1
+ # tree pointers from it indicates ambiguity).
+ # Since the item must have come about from a
+ # "completer" step, the state where the item
+ # came from must be the parent state of the
+ # item the tree pointer points to.
+ #
+ children = tree[want]
+ if len(children) > 1:
+ child = self.ambiguity(children)
+ else:
+ child = children[0]
+
+ tokpos = self.buildTree_r(stack,
+ tokens, tokpos,
+ tree, child)
+ pos = pos - 1
+ (crule, cpos, cparent), cstate = child
+ state = cparent
+
+ lhs, rhs = rule
+ result = self.rule2func[rule](stack[:len(rhs)])
+ stack[:len(rhs)] = [result]
+ return tokpos
+
+ def ambiguity(self, children):
+ #
+ # XXX - problem here and in collectRules() if the same
+ # rule appears in >1 method. But in that case the
+ # user probably gets what they deserve :-) Also
+ # undefined results if rules causing the ambiguity
+ # appear in the same method.
+ #
+ sortlist = []
+ name2index = {}
+ for i in range(len(children)):
+ ((rule, pos, parent), index) = children[i]
+ lhs, rhs = rule
+ name = self.rule2name[rule]
+ sortlist.append((len(rhs), name))
+ name2index[name] = i
+ sortlist.sort()
+ list = map(lambda (a,b): b, sortlist)
+ return children[name2index[self.resolve(list)]]
+
+ def resolve(self, list):
+ #
+ # Resolve ambiguity in favor of the shortest RHS.
+ # Since we walk the tree from the top down, this
+ # should effectively resolve in favor of a "shift".
+ #
+ return list[0]
+
+#
+# GenericASTBuilder automagically constructs a concrete/abstract syntax tree
+# for a given input. The extra argument is a class (not an instance!)
+# which supports the "__setslice__" and "__len__" methods.
+#
+# XXX - silently overrides any user code in methods.
+#
+
+class GenericASTBuilder(GenericParser):
+ def __init__(self, AST, start):
+ GenericParser.__init__(self, start)
+ self.AST = AST
+
+ def preprocess(self, rule, func):
+ rebind = lambda lhs, self=self: \
+ lambda args, lhs=lhs, self=self: \
+ self.buildASTNode(args, lhs)
+ lhs, rhs = rule
+ return rule, rebind(lhs)
+
+ def buildASTNode(self, args, lhs):
+ children = []
+ for arg in args:
+ if isinstance(arg, self.AST):
+ children.append(arg)
+ else:
+ children.append(self.terminal(arg))
+ return self.nonterminal(lhs, children)
+
+ def terminal(self, token): return token
+
+ def nonterminal(self, type, args):
+ rv = self.AST(type)
+ rv[:len(args)] = args
+ return rv
+
+#
+# GenericASTTraversal is a Visitor pattern according to Design Patterns. For
+# each node it attempts to invoke the method n_<node type>, falling
+# back onto the default() method if the n_* can't be found. The preorder
+# traversal also looks for an exit hook named n_<node type>_exit (no default
+# routine is called if it's not found). To prematurely halt traversal
+# of a subtree, call the prune() method -- this only makes sense for a
+# preorder traversal. Node type is determined via the typestring() method.
+#
+
+class GenericASTTraversalPruningException:
+ pass
+
+class GenericASTTraversal:
+ def __init__(self, ast):
+ self.ast = ast
+
+ def typestring(self, node):
+ return node.type
+
+ def prune(self):
+ raise GenericASTTraversalPruningException
+
+ def preorder(self, node=None):
+ if node is None:
+ node = self.ast
+
+ try:
+ name = 'n_' + self.typestring(node)
+ if hasattr(self, name):
+ func = getattr(self, name)
+ func(node)
+ else:
+ self.default(node)
+ except GenericASTTraversalPruningException:
+ return
+
+ for kid in node:
+ self.preorder(kid)
+
+ name = name + '_exit'
+ if hasattr(self, name):
+ func = getattr(self, name)
+ func(node)
+
+ def postorder(self, node=None):
+ if node is None:
+ node = self.ast
+
+ for kid in node:
+ self.postorder(kid)
+
+ name = 'n_' + self.typestring(node)
+ if hasattr(self, name):
+ func = getattr(self, name)
+ func(node)
+ else:
+ self.default(node)
+
+
+ def default(self, node):
+ pass
+
+#
+# GenericASTMatcher. AST nodes must have "__getitem__" and "__cmp__"
+# implemented.
+#
+# XXX - makes assumptions about how GenericParser walks the parse tree.
+#
+
+class GenericASTMatcher(GenericParser):
+ def __init__(self, start, ast):
+ GenericParser.__init__(self, start)
+ self.ast = ast
+
+ def preprocess(self, rule, func):
+ rebind = lambda func, self=self: \
+ lambda args, func=func, self=self: \
+ self.foundMatch(args, func)
+ lhs, rhs = rule
+ rhslist = list(rhs)
+ rhslist.reverse()
+
+ return (lhs, tuple(rhslist)), rebind(func)
+
+ def foundMatch(self, args, func):
+ func(args[-1])
+ return args[-1]
+
+ def match_r(self, node):
+ self.input.insert(0, node)
+ children = 0
+
+ for child in node:
+ if children == 0:
+ self.input.insert(0, '(')
+ children = children + 1
+ self.match_r(child)
+
+ if children > 0:
+ self.input.insert(0, ')')
+
+ def match(self, ast=None):
+ if ast is None:
+ ast = self.ast
+ self.input = []
+
+ self.match_r(ast)
+ self.parse(self.input)
+
+ def resolve(self, list):
+ #
+ # Resolve ambiguity in favor of the longest RHS.
+ #
+ return list[-1]
+
+def _dump(tokens, states):
+ for i in range(len(states)):
+ print 'state', i
+ for (lhs, rhs), pos, parent in states[i]:
+ print '\t', lhs, '::=',
+ print string.join(rhs[:pos]),
+ print '.',
+ print string.join(rhs[pos:]),
+ print ',', parent
+ if i < len(tokens):
+ print
+ print 'token', str(tokens[i])
+ print