spark.py

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

#  Copyright (c) 1998-2002 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.7 (pre-alpha-5)'

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 c.__dict__.keys():
			if not namedict.has_key(name):
				namelist.append(name)
				namedict[name] = 1
	return namelist

class GenericScanner:
	def __init__(self, flags=0):
		pattern = self.reflect()
		self.re = re.compile(pattern, re.VERBOSE|flags)

		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 )+'
		print "Specification error: unmatched input"
		raise SystemExit

#
#  Extracted from GenericParser and made global so that [un]picking works.
#
class _State:
	def __init__(self, stateno, items):
		self.T, self.complete, self.items = [], [], items
		self.stateno = stateno

class GenericParser:
	#
	#  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.  New formulation of
	#  the parser according to J. Aycock, "Practical Earley Parsing
	#  and the SPARK Toolkit", Ph.D. thesis, University of Victoria,
	#  2001, and J. Aycock and R. N. Horspool, "Practical Earley
	#  Parsing", unpublished paper, 2001.
	#

	def __init__(self, start):
		self.rules = {}
		self.rule2func = {}
		self.rule2name = {}
		self.collectRules()
		self.augment(start)
		self.ruleschanged = 1

	_NULLABLE = '\e_'
	_START = 'START'
	_BOF = '|-'

	#
	#  When pickling, take the time to generate the full state machine;
	#  some information is then extraneous, too.  Unfortunately we
	#  can't save the rule2func map.
	#
	def __getstate__(self):
		if self.ruleschanged:
			#
			#  XXX - duplicated from parse()
			#
			self.computeNull()
			self.newrules = {}
			self.new2old = {}
			self.makeNewRules()
			self.ruleschanged = 0
			self.edges, self.cores = {}, {}
			self.states = { 0: self.makeState0() }
			self.makeState(0, self._BOF)
		#
		#  XXX - should find a better way to do this..
		#
		changes = 1
		while changes:
			changes = 0
			for k, v in self.edges.items():
				if v is None:
					state, sym = k
					if self.states.has_key(state):
						self.goto(state, sym)
						changes = 1
		rv = self.__dict__.copy()
		for s in self.states.values():
			del s.items
		del rv['rule2func']
		del rv['nullable']
		del rv['cores']
		return rv

	def __setstate__(self, D):
		self.rules = {}
		self.rule2func = {}
		self.rule2name = {}
		self.collectRules()
		start = D['rules'][self._START][0][1][1]	# Blech.
		self.augment(start)
		D['rule2func'] = self.rule2func
		D['makeSet'] = self.makeSet_fast
		self.__dict__ = D

	#
	#  A hook for GenericASTBuilder and GenericASTMatcher.  Mess
	#  thee not with this; nor shall thee toucheth the _preprocess
	#  argument to addRule.
	#
	def preprocess(self, rule, func):	return rule, func

	def addRule(self, doc, func, _preprocess=1):
		fn = 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))

			if _preprocess:
				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):
		rule = '%s ::= %s %s' % (self._START, self._BOF, start)
		self.addRule(rule, lambda args: args[1], 0)

	def computeNull(self):
		self.nullable = {}
		tbd = []

		for rulelist in self.rules.values():
			lhs = rulelist[0][0]
			self.nullable[lhs] = 0
			for rule in rulelist:
				rhs = rule[1]
				if len(rhs) == 0:
					self.nullable[lhs] = 1
					continue
				#
				#  We only need to consider rules which
				#  consist entirely of nonterminal symbols.
				#  This should be a savings on typical
				#  grammars.
				#
				for sym in rhs:
					if not self.rules.has_key(sym):
						break
				else:
					tbd.append(rule)
		changes = 1
		while changes:
			changes = 0
			for lhs, rhs in tbd:
				if self.nullable[lhs]:
					continue
				for sym in rhs:
					if not self.nullable[sym]:
						break
				else:
					self.nullable[lhs] = 1
					changes = 1

	def makeState0(self):
		s0 = _State(0, [])
		for rule in self.newrules[self._START]:
			s0.items.append((rule, 0))
		return s0

	def finalState(self, tokens):
		#
		#  Yuck.
		#
		if len(self.newrules[self._START]) == 2 and len(tokens) == 0:
			return 1
		start = self.rules[self._START][0][1][1]
		return self.goto(1, start)

	def makeNewRules(self):
		worklist = []
		for rulelist in self.rules.values():
			for rule in rulelist:
				worklist.append((rule, 0, 1, rule))

		for rule, i, candidate, oldrule in worklist:
			lhs, rhs = rule
			n = len(rhs)
			while i < n:
				sym = rhs[i]
				if not self.rules.has_key(sym) or \
				   not self.nullable[sym]:
					candidate = 0
					i = i + 1
					continue

				newrhs = list(rhs)
				newrhs[i] = self._NULLABLE+sym
				newrule = (lhs, tuple(newrhs))
				worklist.append((newrule, i+1,
						 candidate, oldrule))
				candidate = 0
				i = i + 1
			else:
				if candidate:
					lhs = self._NULLABLE+lhs
					rule = (lhs, rhs)
				if self.newrules.has_key(lhs):
					self.newrules[lhs].append(rule)
				else:
					self.newrules[lhs] = [ rule ]
				self.new2old[rule] = oldrule
	
	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):
		sets = [ [(1,0), (2,0)] ]
		self.links = {}
		
		if self.ruleschanged:
			self.computeNull()
			self.newrules = {}
			self.new2old = {}
			self.makeNewRules()
			self.ruleschanged = 0
			self.edges, self.cores = {}, {}
			self.states = { 0: self.makeState0() }
			self.makeState(0, self._BOF)

		for i in xrange(len(tokens)):
			sets.append([])

			if sets[i] == []:
				break				
			self.makeSet(tokens[i], sets, i)
		else:
			sets.append([])
			self.makeSet(None, sets, len(tokens))

		#_dump(tokens, sets, self.states)

		finalitem = (self.finalState(tokens), 0)
		if finalitem not in sets[-2]:
			if len(tokens) > 0:
				self.error(tokens[i-1])
			else:
				self.error(None)

		return self.buildTree(self._START, finalitem,
				      tokens, len(sets)-2)

	def isnullable(self, sym):
		#
		#  For symbols in G_e only.  If we weren't supporting 1.5,
		#  could just use sym.startswith().
		#
		return self._NULLABLE == sym[0:len(self._NULLABLE)]

	def skip(self, (lhs, rhs), pos=0):
		n = len(rhs)
		while pos < n:
			if not self.isnullable(rhs[pos]):
				break
			pos = pos + 1
		return pos

	def makeState(self, state, sym):
		assert sym is not None
		#
		#  Compute \epsilon-kernel state's core and see if
		#  it exists already.
		#
		kitems = []
		for rule, pos in self.states[state].items:
			lhs, rhs = rule
			if rhs[pos:pos+1] == (sym,):
				kitems.append((rule, self.skip(rule, pos+1)))
		core = kitems

		core.sort()
		tcore = tuple(core)
		if self.cores.has_key(tcore):
			return self.cores[tcore]
		#
		#  Nope, doesn't exist.  Compute it and the associated
		#  \epsilon-nonkernel state together; we'll need it right away.
		#
		k = self.cores[tcore] = len(self.states)
		K, NK = _State(k, kitems), _State(k+1, [])
		self.states[k] = K
		predicted = {}

		edges = self.edges
		rules = self.newrules
		for X in K, NK:
			worklist = X.items
			for item in worklist:
				rule, pos = item
				lhs, rhs = rule
				if pos == len(rhs):
					X.complete.append(rule)
					continue

				nextSym = rhs[pos]
				key = (X.stateno, nextSym)
				if not rules.has_key(nextSym):
					if not edges.has_key(key):
						edges[key] = None
						X.T.append(nextSym)
				else:
					edges[key] = None
					if not predicted.has_key(nextSym):
						predicted[nextSym] = 1
						for prule in rules[nextSym]:
							ppos = self.skip(prule)
							new = (prule, ppos)
							NK.items.append(new)
			#
			#  Problem: we know K needs generating, but we
			#  don't yet know about NK.  Can't commit anything
			#  regarding NK to self.edges until we're sure.  Should
			#  we delay committing on both K and NK to avoid this
			#  hacky code?  This creates other problems..
			#
			if X is K:
				edges = {}

		if NK.items == []:
			return k

		#
		#  Check for \epsilon-nonkernel's core.  Unfortunately we
		#  need to know the entire set of predicted nonterminals
		#  to do this without accidentally duplicating states.
		#