Whitespace normalization.

1 files changed, 760 insertions, 760 deletions

diff --git a/Parser/spark.py b/Parser/spark.py
index 00d9733..2c18623 100644
--- a/Parser/spark.py
+++ b/Parser/spark.py
@@ -1,5 +1,5 @@
 #  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
@@ -7,10 +7,10 @@
 #  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.
@@ -26,651 +26,651 @@ 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
+    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
+    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
+    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.
-		#
-		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]
+    #
+    #  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.
+        #
+        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
@@ -681,32 +681,32 @@ class GenericParser:
 #
 
 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
+    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
@@ -719,57 +719,57 @@ class GenericASTBuilder(GenericParser):
 #
 
 class GenericASTTraversalPruningException:
-	pass
+    pass
 
 class GenericASTTraversal:
-	def __init__(self, ast):
-		self.ast = ast
+    def __init__(self, ast):
+        self.ast = ast
 
-	def typestring(self, node):
-		return node.type
+    def typestring(self, node):
+        return node.type
 
-	def prune(self):
-		raise GenericASTTraversalPruningException
+    def prune(self):
+        raise GenericASTTraversalPruningException
 
-	def preorder(self, node=None):
-		if node is None:
-			node = self.ast
+    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
+        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)
+        for kid in node:
+            self.preorder(kid)
 
-		name = name + '_exit'
-		if hasattr(self, name):
-			func = getattr(self, name)
-			func(node)
+        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
+    def postorder(self, node=None):
+        if node is None:
+            node = self.ast
 
-		for kid in node:
-			self.postorder(kid)
+        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)
+        name = 'n_' + self.typestring(node)
+        if hasattr(self, name):
+            func = getattr(self, name)
+            func(node)
+        else:
+            self.default(node)
 
 
-	def default(self, node):
-		pass
+    def default(self, node):
+        pass
 
 #
 #  GenericASTMatcher.  AST nodes must have "__getitem__" and "__cmp__"
@@ -779,62 +779,62 @@ class GenericASTTraversal:
 #
 
 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 __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
+    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