spark.py

Python Development Environment (Python IDE plugin for Eclipse). Features editor, code completion, re

		core = predicted.keys()
		core.sort()
		tcore = tuple(core)
		if self.cores.has_key(tcore):
			self.edges[(k, None)] = self.cores[tcore]
			return k

		nk = self.cores[tcore] = self.edges[(k, None)] = NK.stateno
		self.edges.update(edges)
		self.states[nk] = NK
		return k

	def goto(self, state, sym):
		key = (state, sym)
		if not self.edges.has_key(key):
			#
			#  No transitions from state on sym.
			#
			return None

		rv = self.edges[key]
		if rv is None:
			#
			#  Target state isn't generated yet.  Remedy this.
			#
			rv = self.makeState(state, sym)
			self.edges[key] = rv
		return rv

	def gotoT(self, state, t):
		return [self.goto(state, t)]

	def gotoST(self, state, st):
		rv = []
		for t in self.states[state].T:
			if st == t:
				rv.append(self.goto(state, t))
		return rv

	def add(self, set, item, i=None, predecessor=None, causal=None):
		if predecessor is None:
			if item not in set:
				set.append(item)
		else:
			key = (item, i)
			if item not in set:
				self.links[key] = []
				set.append(item)
			self.links[key].append((predecessor, causal))

	def makeSet(self, token, sets, i):
		cur, next = sets[i], sets[i+1]

		ttype = token is not None and self.typestring(token) or None
		if ttype is not None:
			fn, arg = self.gotoT, ttype
		else:
			fn, arg = self.gotoST, token

		for item in cur:
			ptr = (item, i)
			state, parent = item
			add = fn(state, arg)
			for k in add:
				if k is not None:
					self.add(next, (k, parent), i+1, ptr)
					nk = self.goto(k, None)
					if nk is not None:
						self.add(next, (nk, i+1))

			if parent == i:
				continue

			for rule in self.states[state].complete:
				lhs, rhs = rule
				for pitem in sets[parent]:
					pstate, pparent = pitem
					k = self.goto(pstate, lhs)
					if k is not None:
						why = (item, i, rule)
						pptr = (pitem, parent)
						self.add(cur, (k, pparent),
							 i, pptr, why)
						nk = self.goto(k, None)
						if nk is not None:
							self.add(cur, (nk, i))

	def makeSet_fast(self, token, sets, i):
		#
		#  Call *only* when the entire state machine has been built!
		#  It relies on self.edges being filled in completely, and
		#  then duplicates and inlines code to boost speed at the
		#  cost of extreme ugliness.
		#
		cur, next = sets[i], sets[i+1]
		ttype = token is not None and self.typestring(token) or None

		for item in cur:
			ptr = (item, i)
			state, parent = item
			if ttype is not None:
				k = self.edges.get((state, ttype), None)
				if k is not None:
					#self.add(next, (k, parent), i+1, ptr)
					#INLINED --v
					new = (k, parent)
					key = (new, i+1)
					if new not in next:
						self.links[key] = []
						next.append(new)
					self.links[key].append((ptr, None))
					#INLINED --^
					#nk = self.goto(k, None)
					nk = self.edges.get((k, None), None)
					if nk is not None:
						#self.add(next, (nk, i+1))
						#INLINED --v
						new = (nk, i+1)
						if new not in next:
							next.append(new)
						#INLINED --^
			else:
				add = self.gotoST(state, token)
				for k in add:
					if k is not None:
						self.add(next, (k, parent), i+1, ptr)
						#nk = self.goto(k, None)
						nk = self.edges.get((k, None), None)
						if nk is not None:
							self.add(next, (nk, i+1))

			if parent == i:
				continue

			for rule in self.states[state].complete:
				lhs, rhs = rule
				for pitem in sets[parent]:
					pstate, pparent = pitem
					#k = self.goto(pstate, lhs)
					k = self.edges.get((pstate, lhs), None)
					if k is not None:
						why = (item, i, rule)
						pptr = (pitem, parent)
						#self.add(cur, (k, pparent),
						#	 i, pptr, why)
						#INLINED --v
						new = (k, pparent)
						key = (new, i)
						if new not in cur:
							self.links[key] = []
							cur.append(new)
						self.links[key].append((pptr, why))
						#INLINED --^
						#nk = self.goto(k, None)
						nk = self.edges.get((k, None), None)
						if nk is not None:
							#self.add(cur, (nk, i))
							#INLINED --v
							new = (nk, i)
							if new not in cur:
								cur.append(new)
							#INLINED --^

	def predecessor(self, key, causal):
		for p, c in self.links[key]:
			if c == causal:
				return p
		assert 0

	def causal(self, key):
		links = self.links[key]
		if len(links) == 1:
			return links[0][1]
		choices = []
		rule2cause = {}
		for p, c in links:
			rule = c[2]
			choices.append(rule)
			rule2cause[rule] = c
		return rule2cause[self.ambiguity(choices)]

	def deriveEpsilon(self, nt):
		if len(self.newrules[nt]) > 1:
			rule = self.ambiguity(self.newrules[nt])
		else:
			rule = self.newrules[nt][0]
		#print rule

		rhs = rule[1]
		attr = [None] * len(rhs)

		for i in range(len(rhs)-1, -1, -1):
			attr[i] = self.deriveEpsilon(rhs[i])
		return self.rule2func[self.new2old[rule]](attr)

	def buildTree(self, nt, item, tokens, k):
		state, parent = item

		choices = []
		for rule in self.states[state].complete:
			if rule[0] == nt:
				choices.append(rule)
		rule = choices[0]
		if len(choices) > 1:
			rule = self.ambiguity(choices)
		#print rule

		rhs = rule[1]
		attr = [None] * len(rhs)

		for i in range(len(rhs)-1, -1, -1):
			sym = rhs[i]
			if not self.newrules.has_key(sym):
				if sym != self._BOF:
					attr[i] = tokens[k-1]
					key = (item, k)
					item, k = self.predecessor(key, None)
			#elif self.isnullable(sym):
			elif self._NULLABLE == sym[0:len(self._NULLABLE)]:
				attr[i] = self.deriveEpsilon(sym)
			else:
				key = (item, k)
				why = self.causal(key)
				attr[i] = self.buildTree(sym, why[0],
							 tokens, why[1])
				item, k = self.predecessor(key, why)
		return self.rule2func[self.new2old[rule]](attr)

	def ambiguity(self, rules):
		#
		#  XXX - problem here and in collectRules() if the same rule
		#	 appears in >1 method.  Also undefined results if rules
		#	 causing the ambiguity appear in the same method.
		#
		sortlist = []
		name2index = {}
		for i in range(len(rules)):
			lhs, rhs = rule = rules[i]
			name = self.rule2name[self.new2old[rule]]
			sortlist.append((len(rhs), name))
			name2index[name] = i
		sortlist.sort()
		list = map(lambda (a,b): b, sortlist)
		return rules[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, sets, states):
	for i in range(len(sets)):
		print 'set', i
		for item in sets[i]:
			print '\t', item
			for (lhs, rhs), pos in states[item[0]].items:
				print '\t\t', lhs, '::=',
				print string.join(rhs[:pos]),
				print '.',
				print string.join(rhs[pos:])
		if i < len(tokens):
			print
			print 'token', str(tokens[i])
			print