<gh_stars>10-100
#===============================================================================
# Copyright (c) 2007 <NAME> <<EMAIL>>
#
# 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.
#===============================================================================
#
# Release history:
#
# 1.3 (8 August 2007): Retroactively number public releases.
#
#                      Back-port to Python 2.4.
#
#                      Remove some magic surrounding epsilon, in order to
#                      generalize/simplify.
#
# 1.2 (6 May 2007): Fix some off-by-one errors in production count reporting.
#
#                   Add some missing code that helps detect which definitions
#                   are used/unused when building the parser.
#
# 1.1 (22 March 2007): Optimize/generalize Lr._production() by using argument
#                      list expansion.
#
# 1.0 (19 March 2007): Initial public release.
#
#===============================================================================
"""
The Parsing module implements an LR(1) parser generator, as well as the
runtime support for using a generated parser, via the Lr and Glr parser
drivers.  There is no special parser generator input file format, but the
parser generator still needs to know what classes/methods correspond to
various aspects of the parser.  This information is specified via
docstrings, which the parser generator introspects in order to generate a
parser.  Only one parser specification can be embedded in each module, but
it is possible to share modules between parser specifications so that, for
example, the same token definitions can be used by multiple parser
specifications.

The parsing tables are LR(1), but they are generated using a fast algorithm
that avoids creating duplicate states that result when using the generic
LR(1) algorithm.  Creation time and table size are on par with the LALR(1)
algorithm.  However, LALR(1) can create reduce/reduce conflicts that don't
exist in a true LR(1) parser.  For more information on the algorithm, see:

    A Practical General Method for Constructing LR(k) Parsers
    <NAME>
    Acta Informatica 7, 249-268 (1977)

Parsing table generation requires non-trivial amounts of time for large
grammars.  Internal pickling support makes it possible to cache the most
recent version of the parsing table on disk, and use the table if the
current parser specification is still compatible with the one that was used
to generate the pickled parsing table.  Since the compatibility checking is
quite fast, even for large grammars, this removes the need to use the
standard code generation method that is used by most parser generators.

Parser specifications are encapsulated by the Spec class.  Parser instances
use Spec instances, but are themselves based on separate classes.  This
allows multiple parser instances to exist simultaneously, without requiring
multiple copies of the parsing tables.  There are two separate parser driver
classes:

  Lr : Standard Characteristic Finite State Machine (CFSM) driver, based on
       unambiguous LR(1) parsing tables.  This driver is faster than the Glr
       driver, but it cannot deal with all parsing tables that the Glr
       driver can.

  Glr : Generalized LR driver, capable of tracking multiple parse trees
        simultaneously, if the %split precedence is used to mark ambiguous
        actions.  This driver is closely based on Elkhound's design, which
        is described in a technical report:

            Elkhound: A Fast, Practical GLR Parser Generator
            <NAME>
            Report No. UCB/CSD-2-1214 (December 2002)
            http://www.cs.berkeley.edu/~smcpeak/elkhound/

Parser generator directives are embedded in docstrings, and must begin with
a '%' character, followed immediately by one of several keywords:

    Precedence : %fail %nonassoc %left %right %split
         Token : %token
  Non-terminal : %start %nonterm
    Production : %reduce

All of these directives are associated with classes except for %reduce.
%reduce is associated with methods within non-terminal classes.  The Parsing
module provides base classes from which precedences, tokens, and
non-terminals must be derived.  This is not as restrictive as it sounds,
since there is nothing preventing, for example, a master Token class that
subclasses Parsing.Token, which all of the actual token types then subclass.
Also, nothing prevents using multiple inheritance.

Folowing are the base classes to be subclassed by parser specifications:

  * Precedence
  * Token
  * Nonterm

The Parsing module implements the following exception classes:

  * Exception
  * SpecError
  * SyntaxError
  * AttributeError
"""
__all__ = ["Exception", "SpecError", "SyntaxError", "AttributeError",
	   "Nonterm", "Parser", "Precedence", "Spec", "Token", "Lr", "Glr"]

import cPickle
import exceptions
import re
import sys
import types

#===============================================================================
# Begin exceptions.
#

class Exception(exceptions.Exception):
    """
Top level Parsing exception class, from which all other Parsing
exception classes inherit.
"""

class AttributeError(Exception, exceptions.AttributeError):
    """
Attribute error, no different from the builtin exception, except that it
also derives from Parsing.Exception.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

class SpecError(Exception):
    """
Specification error exception.  SpecError arises when the Spec
introspection machinery detects an error either during docstring parsing
or parser specification generation.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

class SyntaxError(Exception, exceptions.SyntaxError):
    """
Parser syntax error.  SyntaxError arises when a Parser instance detects
a syntax error according to the Spec it is using, for the input being
fed to it.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

#
# End exceptions.
#===============================================================================

class Precedence(object):
    """
Precedences can be associated with tokens, non-terminals, and
productions.  Precedence isn't as important for GLR parsers as for LR
parsers, since GLR parsing allows for parse-time resolution of
ambiguity.  Still, precedence can be useful for reducing the volume of
ambiguities that must be dealt with at run-time.

There are five precedence types: %fail, %nonassoc, %left, %right, and
%split.  Each precedence can have relationships with other precedences:
<, >, or =.  These relationships specify a directed acyclic graph (DAG),
which is used to compute the transitive closures of relationships among
precedences.  If no path exists between two precedences that are
compared during conflict resolution, parser generation fails.  < and >
are reflexive; it does not matter which is used.  Conceptually, the =
relationship causes precedences to share a node in the DAG.

During conflict resolution, an error results if no path exists in the
DAG between the precedences under consideration.  When such a path
exists, the highest precedence non-terminal or production takes
precedence.  Associativity only comes into play for shift/reduce
conflicts, where the terminal and the production have equivalent
precedences (= relationship).  In this case, the non-terminal's
associativity determines how the conflict is resolved.

The %fail and %split associativities are special because they can be
mixed with other associativities.  During conflict resolution, if
another action has non-%fail associativity, then the %fail (lack of)
associativity is overridden.  Similarly, %split associativity overrides
any other associativity.  In contrast, any mixture of associativity
between %nonassoc/%left/%right causes an unresolvable conflict.

       %fail : Any conflict is a parser-generation-time error.

               A pre-defined precedence, [none], is provided.  It has
               %fail associativity, and has no pre-defined precedence
               relationships.

   %nonassoc : Resolve shift/reduce conflicts by removing both
               possibilities, thus making conflicts a parse-time error.

       %left : Resolve shift/reduce conflicts by reducing.

      %right : Resolve shift/reduce conflicts by shifting.

      %split : Do not resolve conflicts; the GLR algorithm will split
               the parse stack when necessary.

               A pre-defined precedence, [split], is provided.  It has
               %split associativity, and has no pre-defined precedence
               relationships.

By default, all symbols have [none] precedence.  Each production
inherits the precedence of its left-hand-side nonterminal's precedence
unless a precedence is manually specified for the production.

Following are some examples of how to specify precedence classes:

  class P1(Parsing.Precedence):
      "%split p1"

  class p2(Parsing.Precedence):
      "%left" # Name implicitly same as class name.

  class P3(Parsing.Precedence):
      "%left p3 >p2" # No whitespace is allowed between > and p2.

  class P4(Parsing.Precedence):
      "%left p4 =p3" # No whitespace is allowed between = and p3.
"""
    def __init__(self, name, assoc, relationships):
	assert assoc in ["fail", "nonassoc", "left", "right", "split"]
	assert type(relationships) == dict

	self.name = name
	self.assoc = assoc
	self.relationships = relationships # Raw relationships specification.

	self.equiv = [self] # Set.  Precedences that have equivalent precedence.
	self.dominators = [] # Set.  Precedences that have higher precedence.

    def __repr__(self):
	equiv = [prec.name for prec in self.equiv]
	equiv.sort()
	domin = [prec.name for prec in self.dominators]
	domin.sort()
	return "[%%%s %s ={%s} <{%s}]" % (self.assoc, self.name, \
	  ",".join(equiv), ",".join(domin))

    # Important for pickling/unpickling.
    def __eq__(self, other):
	return self is other

class SymbolSpec(object):
    seq = 0

    def __init__(self, name, prec):
	assert type(name) == str

	self.name = name
	self.prec = prec
	self.firstSet = [] # Set.
	self.followSet = [] # Set.

	# Used for ordering symbols and hashing.
	self.seq = SymbolSpec.seq
	SymbolSpec.seq += 1

    def __repr__(self):
	return "%s" % self.name

    def __cmp__(self, other):
	return cmp(self.seq, other.seq)

    def __eq__(self, other):
	assert isinstance(other, SymbolSpec)
	return self.seq == other.seq

    def firstSetMerge(self, sym):
	if sym not in self.firstSet:
	    self.firstSet.append(sym)
	    return False
	else:
	    return True

    def followSetMerge(self, set):
	ret = True
	for sym in set:
	    if sym != epsilon and sym not in self.followSet:
		self.followSet.append(sym)
		ret = False
	return ret

class String(list):
    def __init__(self, args=[]):
	list.__init__(self, args)

	self.hash = self._hash()

    def __cmp__(self, other):
	assert isinstance(other, String)
	minLen = min(len(self), len(other))
	for i in xrange(minLen):
	    if self[i] < other[i]:
		return -1
	    elif self[i] > other[i]:
		return 1

	# Prefixes are identical.  Handle trailing characters, if any.
	if len(self) < len(other):
	    return -1
	elif len(self) == len(other):
	    return 0
	else:
	    assert len(self) > len(other)
	    return 1

    def __eq__(self, other):
	if len(self) == len(other):
	    for i in xrange(len(self)):
		if self[i] != other[i]:
		    return False
	    return True
	else:
	    return False

    def _hash(self):
	ret = 5381
	for sym in self:
	    ret = ((ret << 5) + ret) + sym.seq
	    ret &= 0xffffffffffffffff
	return ret

    def __hash__(self):
	return self.hash

class StringSpec(object):
    cache = {}

    def __init__(self, s):
	assert isinstance(s, String)
	for sym in s:
	    assert isinstance(sym, SymbolSpec)

	self.s = s
	if s in StringSpec.cache:
	    self.firstSet = StringSpec.cache[s]
	else:
	    # Calculate the first set for the string encoded by the s vector.
	    self.firstSet = [] # Set.
	    mergeEpsilon = True
	    for sym in self.s:
		hasEpsilon = False
		for elm in sym.firstSet:
		    if elm == epsilon:
			hasEpsilon = True
		    elif sym not in self.firstSet:
			self.firstSet.append(elm)
		if not hasEpsilon:
		    mergeEpsilon = False
		    break
	    # Merge epsilon if it was in the first set of every symbol.
	    if mergeEpsilon:
		self.firstSet.append(epsilon)

	    # Cache the result.
	    StringSpec.cache[s] = self.firstSet

class Symbol(object):
    def __init__(self, symSpec, parser):
	assert isinstance(symSpec, SymbolSpec)
	assert isinstance(parser, Lr)
	self.__symSpec = symSpec
	self.__parser = parser

    def __repr__(self):
	return "%r" % self.symSpec

    def __getSymSpec(self): return self.__symSpec
    def __setSymSpec(self): raise AttributeError
    symSpec = property(__getSymSpec, __setSymSpec)

    def __getParser(self): return self.__parser
    def __setParser(self): raise AttributeError
    parser = property(__getParser, __setParser)

class NontermSpec(SymbolSpec):
    def __init__(self, nontermType, name, qualified, prec):
	assert issubclass(nontermType, Nonterm) # Add forward decl for Lyken.

	SymbolSpec.__init__(self, name, prec)

	self.qualified = qualified
	self.nontermType = nontermType
	self.productions = [] # Set.

class Nonterm(Symbol):
    """
Non-terminal symbols have sets of productions associated with them.  The
productions induce a parse forest on an input token stream.  There is
one special non-terminal, which is denoted via the %start directive,
whereas all other non-terminals are denoted via the %nonterm directive.
In addition to productions (%reduce directives associated with class
methods), the merge() method may be called during resolution of
ambiguous parses.  See the merge() documentation for further details.

Following are examples of how to specify non-terminal classes and their
associated productions:

  class E(Parsing.Nonterm):
      "%start E"
      def __init__(self):
          Parsing.Nonterm.__init__(self)
          # ...

      # Productions.
      def reduceA(self, E, plus, T):
          "%reduce E plus T [split]"
          print "%r ::= %r %r %r." % (self, E, plus, T)

      def reduceB(self, T):
          "%reduce T"

  class T(Parsing.Nonterm):
        "%nonterm" # Name implicitly same as class name.
      def reduceA(self, T, star, F):
          "%reduce T star F"

      def reduceB(self, F):
          "%reduce F [p1]"

  class F(Parsing.Nonterm):
      "%nonterm F [p2]"
      def reduceA(self, lparen, E, rparen):
          "%reduce lparen E rparen"

      def reduceB(self, id):
          "%reduce id"
"""
    def __init__(self, parser):
	assert isinstance(parser, Lr)
	Symbol.__init__(self, parser._spec._sym2spec[type(self)], parser)

    def merge(self, other):
	"""
Merging happens when there is an ambiguity in the input that allows
non-terminals to be part of multiple overlapping series of
reductions.  If no merge() method is specified, the parser will
throw a syntax error upon encountering an ambiguity that confounds
reduction processing.  However, it may be useful to either discard
one of the possible parses, or to explicitly record the ambiguity in
the data structures being created during parsing.  In both of these
cases, the non-terminal-specific merge() is the place to do the
work; merge() returns an object that is stored by the parser onto
the parse stack.  In the case where merge() discards one of the
possible parses, it need only return the parse that is to be
preserved (self or other).

If multiple merges are necessary, they cause a series of merge()
calls.  The first alternative (self) may be the result of a previous
merge() call, whereas other will not have not been merged yet
(unless as the result of merging further down in the parse forest).

The alternative that is discarded is never touched by the parser
again, so if any immediate cleanup is necessary, it should be done
in merge().
"""
	raise SyntaxError, "No merge() for %r; merging %r <--> %r" % \
	  (type(self), self, other)

class Token(Symbol):
    """
Tokens are terminal symbols.  The parser is fed Token instances, which
is what drives parsing.  Typically, the user will define a class that
subclasses Parsing.Token and implement parser-specific machinery there,
then derive all actual token types from that class.

  class Token(Parsing.Token):
      def __init__(self, parser):
	  Parsing.Token.__init__(self, parser)
	  # ...

  class Plus(Token):
      "%token plus [p1]"

  class star(Token):
      "%token star [p2]" # Name implicitly same as class name.

  class lparen(Token):
      "%token [split]"

  class rparen(Token):
      "%token [none]" # [none] not necessary, since it's the default.

  class id(Token):
      "%token"
"""
    def __init__(self, parser):
	assert isinstance(parser, Lr)
	Symbol.__init__(self, parser._spec._sym2spec[type(self)], parser)
	self.__parser = parser

# AKA terminal symbol.
class TokenSpec(SymbolSpec):
    def __init__(self, tokenType, name, prec):
	assert issubclass(tokenType, Token)
	assert type(name) == str
	assert isinstance(prec, Precedence) or type(prec) == str

	SymbolSpec.__init__(self, name, prec)
	self.tokenType = tokenType

# <$>.
class EndOfInput(Token): pass
class EndOfInputSpec(TokenSpec):
    def __init__(self):
	TokenSpec.__init__(self, EndOfInput, "<$>", "none")
eoi = EndOfInputSpec()

# <e>.
class Epsilon(Token): pass
class EpsilonSpec(TokenSpec):
    def __init__(self):
	TokenSpec.__init__(self, Epsilon, "<e>", "none")
epsilon = EpsilonSpec()

class Production(object):
    seq = 0

    def __init__(self, method, qualified, prec, lhs, rhs):
	assert isinstance(prec, Precedence)
	assert isinstance(lhs, NontermSpec)
	if __debug__:
	    for elm in rhs:
		assert isinstance(elm, SymbolSpec)

	self.method = method
	self.qualified = qualified
	self.prec = prec
	self.lhs = lhs
	self.rhs = rhs

	# Used for hashing.
	self.seq = Production.seq
	Production.seq += 1

    def __getstate__(self):
	return (self.qualified, self.prec, self.lhs, self.rhs, self.seq)

    def __setstate__(self, data):
	# Convert qualified name to a function reference.
	(qualified, prec, lhs, rhs, seq) = data
	elms = qualified.split(".")
	method = sys.modules[elms[0]]
	for elm in elms[1:]:
	    method = method.__dict__[elm]

	# Set state.
	self.method = method
	self.qualified = qualified
	self.prec = prec
	self.lhs = lhs
	self.rhs = rhs
	self.seq = seq

    def __repr__(self):
	return "%r ::= %s. [%s]" % \
	  (self.lhs, " ".join(["%r" % elm for elm in self.rhs]), self.prec.name)

    # Optional callback method.
    #
    # Called when a production is reduced.
    def reduce(self, lhs, *rhs): pass

class NontermStart(Nonterm):
    def reduce(self, userStartSym, eoi):
	pass

class Start(Production):
    def __init__(self, startSym, userStartSym):
	Production.__init__(self, none, startSym, userStartSym)

class Item(object):
    def __init__(self, production, dotPos, lookahead):
	assert isinstance(production, Production)
	assert type(dotPos) == int
	assert dotPos >= 0
	assert dotPos <= len(production.rhs)
	assert type(lookahead) == list
	if __debug__:
	    for elm in lookahead:
		assert isinstance(elm, SymbolSpec)

	self.production = production
	self.dotPos = dotPos
	self.lookahead = {}
	for sym in lookahead:
	    self.lookahead[sym] = sym

	self.hash = (dotPos * Production.seq) + production.seq

    def __hash__(self):
	return self.hash

    def __eq__(self, other):
	assert isinstance(other, Item)

	return self.hash == other.hash

    def __cmp__(self, other):
	assert isinstance(other, Item)
	return self.hash.__cmp__(other.hash)

    def __repr__(self):
	strs = []
	strs.append("[%r ::=" % self.production.lhs)
	assert self.dotPos <= len(self.production.rhs)
	i = 0
	while i < self.dotPos:
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(" *")
	while i < len(self.production.rhs):
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	syms = [sym for sym in self.lookahead.iterkeys()]
	syms.sort()
	strs.append("., %s] [%s]" % \
	  ("/".join(["%r" % sym for sym in syms]), \
	  self.production.prec.name))
	
	return "".join(strs)

    def lr0__repr__(self):
	strs = []
	strs.append("%r ::=" % self.production.lhs)
	assert self.dotPos <= len(self.production.rhs)
	i = 0
	while i < self.dotPos:
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(" *")
	while i < len(self.production.rhs):
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(". [%s]" % self.production.prec.name)

	return "".join(strs)

    def lookaheadInsert(self, sym):
	assert isinstance(sym, SymbolSpec)
	self.lookahead[sym] = sym

    def lookaheadDisjoint(self, other):
	sLookahead = self.lookahead
	oLookahead = other.lookahead

	for sSym in sLookahead.iterkeys():
	    if sSym in oLookahead:
		return False

	for oSym in oLookahead.iterkeys():
	    if oSym in sLookahead:
		return False

	return True

class ItemSet(dict):
    def __init__(self, args=[]):
	dict.__init__(self, args)
	self._added = {}

    def __repr__(self):
	kernel = [item for item in self.iterkeys()]
	kernel.sort()
	added = [item for item in self._added.iterkeys()]
	added.sort()
	return "ItemSet(kernel: %s, added: %r)" % \
	  (", ".join(["%r" % item for item in kernel]), \
	  ", ".join(["%r" % item for item in added]))

    def __hash__(self):
	# This works because integers never overflow, and addition is
	# transitive.
	ret = 0
	for item in self.iterkeys():
	    ret += item.hash
	return ret

    def __eq__(self, other):
	if len(self) != len(other):
	    return False
	for sItem in self.iterkeys():
	    if sItem not in other:
		return False
	return True

    def __iter__(self):
	for item in self.iterkeys():
	    assert item.production.lhs.name == "<S>" or item.dotPos != 0
	    yield item
	for item in self._added.iterkeys():
	    assert item.dotPos == 0
	    assert item.production.lhs.name != "<S>"
	    yield item

    # Merge a kernel item.
    def append(self, item):
	assert item.production.lhs.name == "<S>" or item.dotPos != 0

	if item in self:
	    self[item].lookahead.update(item.lookahead)
	else:
	    tItem = Item(item.production, item.dotPos, item.lookahead.keys())
	    self[tItem] = tItem

    # Merge an added item.
    def addedAppend(self, item):
	assert item.dotPos == 0
	assert item.production.lhs.name != "<S>"

	if item in self._added:
	    lookahead = self._added[item].lookahead
	    oldLen = len(lookahead)
	    lookahead.update(item.lookahead)
	    return (oldLen != len(lookahead))
	else:
	    self._added[item] = item
	    return True

    # Given a list of items, compute their closure and merge the results into
    # the set of added items.
    def _closeItems(self, items):
	# Iterate over the items until no more can be added to the closure.
	i = 0
	while i < len(items):
	    item = items[i]
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) \
	      and isinstance(rhs[dotPos], NontermSpec):
		for lookahead in item.lookahead.keys():
		    string = StringSpec( \
		      String(rhs[dotPos+1:] + [lookahead]))
		    lhs = rhs[dotPos]
		    for prod in lhs.productions:
			tItem = Item(prod, 0, string.firstSet)
			if self.addedAppend(tItem):
			    items.append(tItem)
	    i += 1

    # Calculate and merge the kernel's transitive closure.
    def closure(self):
	items = []
	for item in self.iterkeys():
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) and isinstance(rhs[dotPos], \
	      NontermSpec):
		for lookahead in item.lookahead.iterkeys():
		    string = StringSpec(String(rhs[dotPos+1:] + \
		      [lookahead]))
		    lhs = rhs[dotPos]
		    for prod in lhs.productions:
			tItem = Item(prod, 0, string.firstSet)
			if self.addedAppend(tItem):
			    items.append(tItem)
	self._closeItems(items)

    # Calculate the kernel of the goto set, given a particular symbol.
    def goto(self, sym):
	ret = ItemSet()
	for item in self:
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) and rhs[dotPos] == sym:
		tItem = Item(item.production, dotPos + 1, item.lookahead.keys())
		ret.append(tItem)
	return ret

    # Merge the kernel of other into this ItemSet, then update the closure.
    # It is not sufficient to copy other's added items, since other has not
    # computed its closure.
    def merge(self, other):
	items = []
	for item in other.iterkeys():
	    if item in self:
		lookahead = self[item].lookahead
		tLookahead = []
		for sym in item.lookahead.iterkeys():
		    if sym not in lookahead:
			lookahead[sym] = sym
			tLookahead.append(sym)
		if len(tLookahead) > 0:
		    tItem = Item(item.production, item.dotPos, tLookahead)
		    items.append(tItem)
	    else:
		tItem = Item(item.production, item.dotPos, \
		  item.lookahead.keys())
		self[tItem] = tItem
		items.append(tItem)

	if len(items) > 0:
	    self._closeItems(items)
	    return True
	else:
	    return False

    # Determine if self and other are weakly compatible, as defined by the
    # Pager(1977) algorithm.
    def weakCompat(self, other):
	# Check for identical kernel LR(0) items, and pair items, for later use.
	if len(self) != len(other):
	    return False
	pairs = []
	for sItem in self.iterkeys():
	    if sItem not in other:
		return False
	    oItem = other[sItem]
	    pairs.append((sItem, oItem))

	# Check for lookahead compatibility.
	for i in xrange(len(pairs)-1):
	    iPair = pairs[i]
	    isItem = iPair[0]
	    ioItem = iPair[1]
	    for j in xrange(i+1, len(pairs)):
		jPair = pairs[j]
		jsItem = jPair[0]
		joItem = jPair[1]

		if isItem.lookaheadDisjoint(joItem) \
		  and ioItem.lookaheadDisjoint(jsItem):
		    pass
		elif not isItem.lookaheadDisjoint(jsItem):
		    pass
		elif not ioItem.lookaheadDisjoint(joItem):
		    pass
		else:
		    return False
	return True

class Action(object):
    """
Abstract base class, subclassed by {Shift,Reduce}Action.
"""
    def __init__(self): pass

class ShiftAction(Action):
    """
Shift action, with assocated nextState.
"""
    def __init__(self, nextState):
	Action.__init__(self)
	self.nextState = nextState

    def __repr__(self):
	return "[shift %r]" % self.nextState

    def __eq__(self, other):
	if not isinstance(other, ShiftAction):
	    return False
	if self.nextState != other.nextState:
	    return False
	return True

class ReduceAction(Action):
    """
Reduce action, with associated production.
"""
    def __init__(self, production):
	Action.__init__(self)
	self.production = production

    def __repr__(self):
	return "[reduce %r]" % self.production

    def __eq__(self, other):
	if not isinstance(other, ReduceAction):
	    return False
	if self.production != other.production:
	    return False
	return True

class Spec(object):
    """
The Spec class contains the read-only data structures that the Parser
class needs in order to parse input.  Parser generation results in a
Spec instance, which can then be shared by multiple Parser instances.
"""
    def __init__(self, modules, pickleFile=None, pickleMode="rw",
		 skinny=True, logFile=None, graphFile=None, verbose=False):
	"""
modules : Either a single module, or a list of modules, wherein to
          look for parser generator directives in docstrings.

pickleFile : The path of a file to use for Spec pickling/unpickling.

pickleMode :  "r" : Unpickle from pickleFile.
              "w" : Pickle to pickleFile.
              "rw" : Unpickle/pickle from/to pickleFile.

skinny : If true, discard all data that are only strictly necessary
         while constructing the parsing tables.  This reduces
         available debugging context, but substantially reduces
         pickle size.

logFile : The path of a file to store a human-readable copy of the
          parsing tables in.

graphFile : The path of a file to store a graphviz representation
            (dot format) of the precedence relationship graph.

verbose : If true, print progress information while generating the
          parsing tables.
"""
	assert pickleFile == None or type(pickleFile) == str
	assert pickleMode in ["rw", "r", "w"]
	assert type(skinny) == bool
	assert logFile == None or type(logFile) == str
	assert graphFile == None or type(graphFile) == str
	assert type(verbose) == bool

	self._skinny = skinny
	self._verbose = verbose

	# Default (no) precedence.
	self._none = Precedence("none", "fail", {})
	self._split = Precedence("split", "split", {})

	# Symbols are maintained as two separate sets so that non-terminals and
	# terminals (tokens) can be operated on separately where needed.
	self._precedences = {self._none.name: self._none,
			     self._split.name: self._split}
	self._nonterms = {}
	self._tokens = {eoi.name: eoi, epsilon.name: epsilon}
	self._sym2spec = {EndOfInput: eoi, Epsilon: epsilon}
	self._productions = []

	self._userStartSym = None
	self._startSym = None
	self._startProd = None

	# Everything below this point is computed from the above (once
	# introspection is complete).

	self._itemSets = [] # Each element corresponds to an element in _action.
	self._itemSetsHash = None
	# LR parsing tables.  The tables conceptually contain one state per row,
	# where each row contains one element per symbol.  The table is
	# conceptually in row-major form, but each row is actually a dictionary.
	# If no entry for a symbol exists for a particular state, then input of
	# that symbol is an error for that state.
	self._action = []
	self._goto = []
	self._startState = None
	self._nActions = 0
	self._nConflicts = 0
	self._nImpure = 0 # Number of LR impurities (does not affect GLR).

	# Introspect modules and generate parse tables.
	if type(modules) == types.ModuleType:
	    # Wrap single module in a list.
	    modules = [modules]
	self._prepare(modules, pickleFile, pickleMode, logFile, graphFile)

    def __getPureLR(self):
	return (self._nConflicts + self._nImpure == 0)
    def __setPureLR(self): raise AttributeError
    pureLR = property(__getPureLR, __setPureLR)

    def __getConflicts(self): return self._nConflicts
    def __setConflicts(self): raise AttributeError
    conflicts = property(__getConflicts, __setConflicts)

    def __repr__(self):
	if self._skinny:
	    # Print a very reduced summary, since most info has been discarded.
	    return "Parsing.Spec: %d states, %d actions (%d split)" % \
	      (len(self._action), self._nActions, self._nImpure)

	lines = []

	#=======================================================================
	lines.append("Precedences:")
	deco = [(prec.name, prec) for prec in self._precedences.itervalues()]
	deco.sort()
	for elm in deco:
	    prec = elm[1]
	    lines.append("  %r" % prec)

	lines.append("Tokens:")
	syms = [sym for sym in self._tokens.itervalues()]
	syms.sort()
	for token in syms:
	    lines.append("  %r %r" % (token, token.prec))
	    lines.append("    First set: %r" % token.firstSet)
	    lines.append("    Follow set: %r" % token.followSet)

	lines.append("Non-terminals:")
	syms = [sym for sym in self._nonterms.itervalues()]
	syms.sort()
	for sym in syms:
	    lines.append("  %r %r" % (sym, sym.prec))
	    lines.append("    First set: %r" % sym.firstSet)
	    lines.append("    Follow set: %r" % sym.followSet)
	    lines.append("    Productions:")
	    prods = sym.productions[:]
	    prods.sort()
	    for prod in prods:
		lines.append("      %r" % prod)

	lines.append("Item sets:")
	for i in xrange(len(self._itemSets)):
	    lines.append("  %d: %r" % (i, self._itemSets[i]))
	#=======================================================================

	ntokens = len(self._tokens) - 1
	nnonterms = len(self._nonterms) - 1
	nproductions = len(self._productions) - 1
	nstates = len(self._action)
	lines.append(("Parsing.Spec: %d token%s, %d non-terminal%s, " + \
	  "%d production%s, %d state%s, %d action%s (%d split):") % \
	  (ntokens, ("s", "")[ntokens == 1], \
	  nnonterms, ("s", "")[nnonterms == 1], \
	  nproductions, ("s", "")[nproductions == 1], \
	  nstates, ("s", "")[nstates == 1], \
	  self._nActions, ("s", "")[self._nActions == 1], \
	  self._nImpure))
	if self.pureLR:
	    lines.append("Algorithm compatibility: GLR, LR")
	elif self._nConflicts == 0:
	    lines.append("Algorithm compatibility: GLR")
	else:
	    lines.append("Algorithm compatibility: None, due to ambiguity")
	lines.append("Parsing tables:")
	for i in xrange(len(self._action)):
	    lines.append("  %s" % ("=" * 78))
	    lines.append("  State %d:%s" % \
	      (i, ("", " (start state)")[self._startState == i]))
	    items = [item for item in self._itemSets[i]]
	    items.sort()
	    for item in items:
		lines.append(" %s%s" % (" " * (len("%d" % i) + 9),
		  item.lr0__repr__()))
	    lines.append("    Goto:")
	    syms = [sym for sym in self._goto[i]]
	    syms.sort()
	    for sym in syms:
		lines.append("    %15r : %r" % (sym, self._goto[i][sym]))
	    lines.append("    Action:")
	    syms = [sym for sym in self._action[i]]
	    syms.sort()
	    for sym in syms:
		for action in self._action[i][sym]:
		    conflict = "   "
		    for other in self._action[i][sym]:
			if action != other:
			    resolution = self._resolve(sym, other, action)
			    if resolution == "err":
				conflict = "XXX"
				break

		    if type(action) == ShiftAction:
			lines.append("%s %15r : %-6s %d [%s]" % \
			  (conflict, sym, "shift", action.nextState, \
			  sym.prec.name))
		    else:
			assert type(action) == ReduceAction
			lines.append("%s %15r : %-6s %r" % \
			  (conflict, sym, "reduce", action.production))

	ret = "\n".join(lines)
	return ret

    def _prepare(self, modules, pickleFile, pickleMode, logFile, graphFile):
	"""
Compile the specification into data structures that can be used by
the Parser class for parsing.
"""
	# Get the grammar specification.
	self._introspect(modules)

	# Augment grammar with a special start symbol and production:
	#
	#   <S> ::= S <$>.
	assert self._startSym == None
	assert isinstance(self._userStartSym, NontermSpec)
	self._startSym = NontermSpec(NontermStart, "<S>",
	  "%s.NontermStart" % __name__, self._none)
	self._startProd = Production(NontermStart.reduce.im_func,
				     "%s.NontermStart.reduce" % __name__,
				     self._none, self._startSym, \
				     [self._userStartSym, eoi])
	self._startSym.productions.append(self._startProd)
	self._nonterms["<S>"] = self._startSym
	self._productions.append(self._startProd)

	# Resolve references in the grammar specification.
	self._references(logFile, graphFile)

	# Check for a compatible pickle.
	compat = self._unpickle(pickleFile, pickleMode)

	if compat == "incompatible":
	    # Create the collection of sets of LR(1) items.
	    self._firstSets()
	    self._followSets()
	    self._items()

	if compat == "compatible":
	    # Just because the pickle was compatible does not mean that it is
	    # valid for parsing.
	    if self._nConflicts != 0:
		raise SpecError, \
		  "Compatible pickle is invalid due to conflicts (%d)" % \
		  self._nConflicts
	if compat in ["itemsets", "incompatible"]:
	    # Generate LR(1) parsing tables.
	    self._lr()

	    # Disambiguate actions.
	    self._disambiguate()

	    # Check for unused or ambiguous definitions, as well as reporting
	    # ambiguities.
	    try:
		self._validate(logFile)
	    finally:
		# Pickle the spec, if method parameters so dictate, even if
		# there were validation errors, so that the pickle might be
		# used in part during later runs.
		self._pickle(pickleFile, pickleMode)
	elif compat == "repickle":
	    # Pickle the spec, if method parameters so dictate.
	    self._pickle(pickleFile, pickleMode)

	if self._skinny:
	    # Discard data that are not needed during parsing.  Note that
	    # _pickle() also discarded data that don't even need to be pickled.
	    del self._precedences
	    del self._nonterms
	    del self._tokens
	    del self._productions

    # Introspect modules and find special parser declarations.  In order to be
    # a special class, the class must both 1) be subclassed from Token or
    # Nonterm, and 2) contain the appropriate %foo docstring.
    def _introspect(self, modules):
	if self._verbose:
	    print ("Parsing.Spec: Introspecting module%s to acquire formal" + \
	    " grammar specification...") % ("s", "")[len(modules) == 1]

	self._precedences["none"] = self._none
	self._precedences["split"] = self._split

	for module in modules:
	    d = module.__dict__
	    for k in d:
		v = d[k]
		if type(v) is types.TypeType and type(v.__doc__) == str:
		    dirtoks = v.__doc__.split(" ")

		    #===========================================================
		    # Precedence.
		    #
		    if issubclass(v, Precedence) and dirtoks[0] in \
		      ["%fail", "%nonassoc", "%left", "%right", "%split"]:
			name = k
			relationships = {}
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'([<>=])([A-Za-z]\w*)').match(tok)
			    if m:
				# Precedence relationship.
				if m.group(2) in relationships:
				    raise SpecError, \
				      ("Duplicate precedence " \
				      + "relationship: %s") \
				      % v.__doc__
				relationships[m.group(2)] = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    if i != 1:
					raise SpecError, \
					  ("Precedence name must come before " \
					  + "relationships: %s") \
					  % v.__doc__
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid precedence specification: %s" % \
				      v.__doc__
			    i += 1

			if name in self._precedences:
			    raise SpecError, \
			      "Duplicate precedence name: %s" % v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Identical token/precedence names: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Identical nonterm/precedence names: %s" % \
			      v.__doc__
			prec = Precedence(name, dirtoks[0][1:], relationships)
			self._precedences[name] = prec
		    #===========================================================
		    # Token.
		    #
		    elif issubclass(v, Token) and dirtoks[0] in ["%token"]:
			name = k
			prec = None
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
			    if m:
				if i < len(dirtoks) - 1:
				    raise SpecError, \
				      ("Precedence must come last in token " \
				      + "specification: %s") % v.__doc__
				prec = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid token specification: %s" % \
				      v.__doc__
			    i += 1
			if name in self._precedences:
			    raise SpecError, \
			      "Identical precedence/token names: %s" % v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Duplicate token name: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Identical nonterm/token names: %s" % v.__doc__
			if prec == None:
			    prec = "none"
			token = TokenSpec(v, name, prec)
			self._tokens[name] = token
			self._sym2spec[v] = token
		    #===========================================================
		    # Nonterm.
		    #
		    elif issubclass(v, Nonterm) and \
		      dirtoks[0] in ["%start", "%nonterm"]:
			name = None
			prec = None
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
			    if m:
				if i < len(dirtoks) - 1:
				    raise SpecError, \
				      ("Precedence must come last in " \
				      + "non-terminal specification: %s") % \
				      v.__doc__
				prec = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid non-terminal specification: %s" \
				      % v.__doc__
			    i += 1
			if name == None:
			    name = k
			if prec == None:
			    prec = "none"
			if name in self._precedences:
			    raise SpecError, \
			      "Identical precedence/nonterm names: %s" % \
			      v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Identical token/nonterm names: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Duplicate nonterm name: %s" % v.__doc__
			nonterm = NontermSpec(v, name,
			  "%s.%s" % (module.__name__, name), prec)
			self._nonterms[name] = nonterm
			self._sym2spec[v] = nonterm

			if dirtoks[0] == "%start":
			    # Start symbol.
			    if self._userStartSym != None:
				raise SpecError, \
				  "Only one start non-terminal allowed: %s" \
				  % v.__doc__
			    self._userStartSym = nonterm
		    #===========================================================
	if not isinstance(self._userStartSym, NontermSpec):
	    raise SpecError, "No start symbol specified"

    # Resolve all symbolic (named) references.
    def _references(self, logFile, graphFile):
	# Build the graph of Precedence relationships.
	self._resolvePrec(graphFile)

	# Resolve Token-->Precedence references.
	for token in self._tokens.itervalues():
	    if type(token.prec) == str:
		token.prec = self._precedences[token.prec]

	# Resolve Nonterm-->Precedence references.
	for nonterm in self._nonterms.itervalues():
	    if type(nonterm.prec) == str:
		nonterm.prec = self._precedences[nonterm.prec]

	# Resolve Nonterm-->{Nonterm,Token,Precedence} references.
	for nonterm in self._nonterms.itervalues():
	    d = nonterm.nontermType.__dict__
	    for k in d:
		v = d[k]
		if type(v) is types.FunctionType and type(v.__doc__) == str:
		    dirtoks = v.__doc__.split(" ")
		    if dirtoks[0] == "%reduce":
			rhs = []
			prec = None
			for i in xrange(1, len(dirtoks)):
			    tok = dirtoks[i]
			    m = re.compile(r'([A-Za-z]\w*)').match(tok)
			    if m:
				# Symbolic reference.
				if tok in self._tokens:
				    rhs.append(self._tokens[tok])
				elif tok in self._nonterms:
				    rhs.append(self._nonterms[tok])
				else:
				    raise SpecError, \
				      ("Unknown symbol '%s' in reduction " \
				      + "specification: %s") % (tok, v.__doc__)
			    else:
				m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
				if m:
				    # Precedence.
				    if i < len(dirtoks) - 1:
					raise SpecError, \
					  ("Precedence must come last in " \
					  + "reduction specification: %s") % \
					  v.__doc__
				    if m.group(1) not in self._precedences:
					raise SpecError, \
					  ("Unknown precedence in reduction " \
					  + "specification: %s") % v.__doc__
				    prec = self._precedences[m.group(1)]

			if prec == None:
			    # Inherit the non-terminal's precedence.
			    prec = nonterm.prec

			prod = Production(v, "%s.%s" % (nonterm.qualified, k), \
			  prec, nonterm, rhs)
			assert prod not in nonterm.productions
			nonterm.productions.append(prod)
			self._productions.append(prod)
	if self._verbose:
	    ntokens = len(self._tokens) - 1
	    nnonterms = len(self._nonterms) - 1
	    nproductions = len(self._productions) - 1
	    print \
	      "Parsing.Spec: %d token%s, %d non-terminal%s, %d production%s" % \
	      (ntokens, ("s", "")[ntokens == 1], \
	      nnonterms, ("s", "")[nnonterms == 1], \
	      nproductions, ("s", "")[nproductions == 1])

    # Build the graph of Precedence relationships.
    def _resolvePrec(self, graphFile):
	# Resolve symbolic references and populate equiv/dominators.
	for precA in self._precedences.itervalues():
	    for precBName in precA.relationships:
		if precBName not in self._precedences:
		    raise SpecError, \
		      ("Precedence '%s' specifies a relationship with " + \
		      "unknown Precedence '%s'") % (precA, precBName)
		precB = self._precedences[precBName]
		rel = precA.relationships[precBName]
		if rel == "=":
		    precA.equiv.append(precB)
		elif rel == "<":
		    if precB not in precA.dominators:
			precA.dominators.append(precB)
		elif rel == ">":
		    if precA not in precB.dominators:
			precB.dominators.append(precA)
		else:
		    assert False

	# Create equivalence classes for all Precedence classes.  Since the
	# Precedence classes are equivalent, they also share dominator sets.
	for precA in self._precedences.itervalues():
	    for precB in precA.equiv[:]:
		if not precB.equiv is precA.equiv:
		    # Merge the sets of equivalent Precedence classes.
		    for prec in precB.equiv:
			if prec not in precA.equiv:
			    precA.equiv.append(prec)
		    # Share the equiv set.
		    for prec in precA.equiv:
			prec.equiv = precA.equiv

	# Use the equivalence classes to merge dominator sets and share them.
	for precA in self._precedences.itervalues():
	    for precB in precA.equiv[1:]:
		# Merge the sets of dominator Precedence classes.
		for prec in precB.dominators:
		    if prec not in precA.dominators:
			precA.dominators.append(prec)
		# Share the dominator set.
		precB.dominators = precA.dominators

	# Write graphviz precedence graph to graphFile, if graphFile was
	# specified.
	if graphFile != None:
	    f = open(graphFile, "w+")
	    if self._verbose:
		print \
		  "Parsing.Spec: Writing graphviz precedence graph to '%s'..." \
		  % graphFile
	    print >> f, 'digraph Precedence {'
	    print >> f, '    graph [bgcolor=black, labeljust="l"]'
	    print >> f, \
	      ('    node [shape=record, style=filled, color=black, ' + \
	      'fillcolor=gray, fontname=Helvetica, fontsize=10.0]')
	    print >> f, '    edge [color=gray]'
	    for precA in self._precedences.itervalues():
		if precA == precA.equiv[0]:
		    print >> f, \
		      ('    Precedence_%s [label="{%s}"]') % (precA.name, \
		      "\\n".join(["%s (%s)" % (p.name, p.assoc) \
		      for p in precA.equiv]))
		    for precB in precA.dominators:
			print >> f, '    Precedence_%s -> Precedence_%s' % \
			  (precB.equiv[0].name, precA.equiv[0].name)
	    print >> f, '}'
	    f.close()

	# Iteratively build dominator sets until no more work can be done.
	done = False
	while not done:
	    done = True
	    for precA in self._precedences.itervalues():
		if precA == precA.equiv[0]: # No need to do more than this.
		    for precB in precA.dominators[:]:
			for precC in precB.equiv:
			    if precC not in precA.dominators:
				precA.dominators.append(precC)
				done = False
			for precC in precB.dominators:
			    for precD in precC.equiv:
				if precD not in precA.dominators:
				    precA.dominators.append(precD)
				    done = False

	# Check for cycles in the graph.
	cycles = []
	for precA in self._precedences.itervalues():
	    for precB in [precA] + precA.equiv:
		if precB in precA.dominators:
		    cycles.append( \
		      "Precedence relationship cycle involving '%s'" % \
		      precA.name)
	if len(cycles) > 0:
	    raise SpecError, "\n".join(cycles)

    # Store state to a pickle file, if requested.
    def _pickle(self, file, mode):
	if self._skinny:
	    # Discard data that don't need to be pickled.
	    del self._startSym
	    del self._startProd
	    del self._itemSets
	    del self._itemSetsHash
	    del self._startState

	if file != None and "w" in mode:
	    if self._verbose:
		print "Parsing.Spec: Creating %s Spec pickle in %s..." % \
		  (("fat", "skinny")[self._skinny], file)
	    f = open(file, "w")
	    cPickle.dump(self, f, protocol=cPickle.HIGHEST_PROTOCOL)
	    f.close()

    # Restore state from a pickle file, if a compatible one is provided.  This
    # method uses the same set of return values as does _compatible().
    def _unpickle(self, file, mode):
	if file != None and "r" in mode:
	    if self._verbose:
		print \
		  "Parsing.Spec: Attempting to use pickle from file \"%s\"..." \
		  % file
	    try:
		f = open(file, "r")
	    except IOError:
		if self._verbose:
		    error = sys.exc_info()
		    print "Parsing.Spec: Pickle open failed: Exception %s: %s" \
		      % (error[0], error[1])
		return "incompatible"

	    # Any exception at all in unpickling can be assumed to be due to
	    # an incompatible pickle.
	    try:
		spec = cPickle.load(f)
	    except:
		if self._verbose:
		    error = sys.exc_info()
		    print "Parsing.Spec: Pickle load failed: Exception %s: %s" \
		      % (error[0], error[1])
		return "incompatible"

	    compat = self._compatible(spec)
	    if compat == "incompatible":
		if self._verbose:
		    print "Parsing.Spec: Pickle in \"%s\" is incompatible." % \
		      file
		return compat

	    if self._verbose:
		print \
		  "Parsing.Spec: Using %s pickle in \"%s\" (%s)..." \
		  % (("fat", "skinny")[spec._skinny], file, compat)

	    if compat in ["compatible", "repickle"]:
		# Copy spec's data structures.
		self._precedences = spec._precedences
		self._action = spec._action
		self._goto = spec._goto
		if not self._skinny:
		    self._startState = spec._startState
		self._nActions = spec._nActions
		self._nConflicts = spec._nConflicts
		self._nImpure = spec._nImpure
	    elif compat == "itemsets":
		# Precedences are incompatible, so great care has to be taken
		# when copying from the pickle.  Overwrite all precedence
		# specifications in spec with the new ones, then copy over all
		# of the new symbols/productions (but not the new precedences,
		# of course).  This still leaves table generation, which is
		# done by the _prepare() method later.

		# Nonterminals.
		for key in self._nonterms:
		    nontermSelf = self._nonterms[key]
		    nontermSpec = spec._nonterms[key]
		    nontermSpec.prec = nontermSelf.prec
		    # Productions.
		    for prodSelf in nontermSelf.productions:
			for prodSpec in nontermSpec.productions:
			    if prodSelf.qualified == prodSpec.qualified:
				prodSpec.prec = prodSelf.prec
				break
			assert prodSelf.qualified == prodSpec.qualified
		# Tokens.
		for key in self._tokens:
		    tokenSelf = self._tokens[key]
		    tokenSpec = spec._tokens[key]
		    tokenSpec.prec = tokenSelf.prec
	    else:
		assert False

	    # Copy spec data structures that are usable regardless of whether
	    # the parsing tables need to be rebuilt.
	    self._nonterms = spec._nonterms
	    self._tokens = spec._tokens
	    self._sym2spec = spec._sym2spec
	    self._productions = spec._productions
	    self._userStartSym = spec._userStartSym
	    if not self._skinny:
		self._startSym = spec._startSym
		self._startProd = spec._startProd
		self._itemSets = spec._itemSets
		self._itemSetsHash = spec._itemSetsHash

	    return compat
	else:
	    return "incompatible"

    # Determine whether other is compatible with self.  Note that self is not
    # completely initialized; the idea here is to determine whether other's
    # data structures can be copied *before* doing the work of building parsing
    # tables.
    #
    # Itemsets and precedences are not directly related, other than that
    # symbols have precedences associated with them.  Therefore, we check for
    # the following cases:
    #
    #   "compatible" : Completely compatible.
    #
    #   "repickle" : Compatible, but pickle needs to be regenerated.
    #
    #   "itemsets" : Itemsets are compatible, but precedence specifications are
    #                not.
    #
    #   "incompatible" : No useful compatibility.
    def _compatible(self, other):
	ret = "compatible"

	if (not self._skinny) and other._skinny:
	    return "incompatible"
	elif self._skinny != other._skinny:
	    ret = "repickle"

	# Precedences.
	if len(self._precedences) != len(other._precedences):
	    if self._verbose:
		print "Parsing.Spec: Unequal number of precedences (%d vs %d)" \
		  % (len(self._precedences), len(other._precedences))
	    ret = "itemsets"
	for key in self._precedences:
	    if key not in other._precedences:
		if self._verbose:
		    print "Parsing.Spec: Missing precedence: %s" % key
		ret = "itemsets"
		continue
	    precA = self._precedences[key]
	    precB = other._precedences[key]
	    if precA.name != precB.name \
	      or precA.assoc != precB.assoc \
	      or len(precA.relationships) != len(precB.relationships):
		if self._verbose:
		    print "Parsing.Spec: Incompatible precedences: %r vs. %r" \
		      % (precA, precB)
		ret = "itemsets"
		continue
	    for prec in precA.relationships:
		rel = precA.relationships[prec]
		if prec not in precB.relationships \
		  or precB.relationships[prec] != rel:
		    if self._verbose:
			print \
			  "Parsing.Spec: Incompatible precedences: %r vs. %r" \
			  % (precA, precB)
		    ret = "itemsets"
		    break

	# Nonterminals.
	if len(self._nonterms) != len(other._nonterms):
	    if self._verbose:
		print \
		  "Parsing.Spec: Unequal number of non-terminals (%d vs %d)" \
		  % (len(self._nonterms), len(other._nonterms))
	    return "incompatible"
	for key in self._nonterms:
	    if key not in other._nonterms:
		if self._verbose:
		    print "Parsing.Spec: Missing non-terminal: %s" % key
		return "incompatible"
	    nontermA = self._nonterms[key]
	    nontermB = other._nonterms[key]
	    if nontermA.name != nontermB.name \
	      or nontermA.qualified != nontermB.qualified \
	      or nontermA.nontermType != nontermB.nontermType:
		if self._verbose:
		    print \
		      "Parsing.Spec: Incompatible non-terminals: %r vs. %r" \
		      % (nontermA, nontermB)
		return "incompatible"
	    if nontermA.prec.name != nontermB.prec.name:
		if self._verbose:
		    print \
		      ("Parsing.Spec: Differing precedences for " + \
		      "non-terminal: %r") % nontermA
		ret = "itemsets"

	    # Productions.
	    if len(nontermA.productions) != len(nontermB.productions):
		if self._verbose:
		    print \
		      "Parsing.Spec: Unequal number of productions (%d vs %d)" \
		      % (len(self._productions) - 1, \
		      len(other._productions) - 1)
		return "incompatible"
	    for prodA in nontermA.productions:
		match = False
		for prodB in nontermB.productions:
		    if prodA.qualified == prodB.qualified \
		      and prodA.lhs.name == prodB.lhs.name \
		      and len(prodA.rhs) == len(prodB.rhs):
			match = True
			for i in xrange(len(prodA.rhs)):
			    if prodA.rhs[i].name != prodB.rhs[i].name:
				match = False
				if self._verbose:
				    print \
				      ("Parsing.Spec: Incompatible" + \
				      " productions: %r vs. %r") \
				      % (prodA, prodB)
				break
			if prodA.prec.name != prodB.prec.name:
			    if self._verbose:
				print \
				  ("Parsing.Spec: Differing precedences " + \
				  "for production: %r") % prodA
			    ret = "itemsets"
		if not match:
		    return "incompatible"

	# Tokens.
	if len(self._tokens) != len(other._tokens):
	    if self._verbose:
		print "Parsing.Spec: Unequal number of tokens (%d vs %d)" \
		  % (len(self._tokens), len(other._tokens))
	    return "incompatible"
	for key in self._tokens:
	    if key not in other._tokens:
		if self._verbose:
		    print "Parsing.Spec: Missing token: %s" % key
		return "incompatible"
	    tokenA = self._tokens[key]
	    tokenB = other._tokens[key]
	    if tokenA.name != tokenB.name \
	      or tokenA.tokenType != tokenB.tokenType:
		if self._verbose:
		    print \
		      "Parsing.Spec: Incompatible tokens: %r vs. %r" \
		      % (tokenA, tokenB)
		return "incompatible"
	    if tokenA.prec.name != tokenB.prec.name:
		if self._verbose:
		    print \
		      "Parsing.Spec: Differing precedences for token: %r" \
		      % tokenA
		ret = "itemsets"

	# User start symbol.
	if self._userStartSym.name != other._userStartSym.name:
	    if self._verbose:
		print "Parsing.Spec: Differing start symbols: %s vs. %s" \
		  % (self._userStartSym.name, other._userStartSym.name)
	    return "incompatible"

	if other._skinny and ret == "itemsets":
	    # The itemsets have to be regenerated, since they weren't pickled.
	    ret = "incompatible"
	return ret

    # Check for unused prececence/token/nonterm/reduce specifications, then
    # throw a SpecError if any ambiguities exist in the grammar.
    def _validate(self, logFile):
	if self._verbose:
	    print "Parsing.Spec: Validating grammar..."

	lines = []
	if self._nConflicts > 0:
	    lines.append("Parsing.Spec: %d unresolvable conflict%s" % \
	      (self._nConflicts, ("s", "")[self._nConflicts == 1]))

	# Previous code guarantees that all precedence/token/nonterm names are
	# unique.  Therefore, we can build a single dictionary here that keys on
	# names.
	used = {}
	productions = []
	for itemSet in self._itemSets:
	    for item in itemSet:
		productions.append(item.production)
		used[item.production.prec.name] = item.production.prec
		for sym in [item.production.lhs] + item.production.rhs:
		    used[sym.name] = sym
		    used[sym.prec.name] = sym.prec

		for token in item.lookahead.iterkeys():
		    used[token.prec.name] = token.prec

	nUnused = 0

	# Precedences.
	for prec in self._precedences:
	    if prec not in [self._none.name, self._split.name]:
		if prec not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused precedence: %r" % \
		      self._precedences[prec])

	# Tokens.
	for token in self._tokens:
	    if token not in [eoi.name, epsilon.name]:
		if token not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused token: %s" % \
		      self._tokens[token])

	# Nonterms.
	for nonterm in self._nonterms:
	    if nonterm not in [self._startSym.name]:
		if nonterm not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused nonterm: %s" % \
		      self._nonterms[nonterm])

	# Productions.
	for production in self._productions:
	    if production not in productions:
		nUnused += 1
		lines.append("Parsing.Spec: Unused production: %r" % production)

	if nUnused > 0:
	    lines.insert((1, 0)[self._nConflicts == 0], \
	      "Parsing.Spec: %d unused definition%s" % \
	      (nUnused, ("s", "")[nUnused == 1]))

	# Write to logFile, if one was specified.
	if logFile != None:
	    f = open(logFile, "w+")
	    if self._verbose:
		print "Parsing.Spec: Writing log to '%s'..." % logFile
	    f.write("%s" % "\n".join(lines + ["%r" % self]))
	    f.close()

	# Conflicts are fatal.
	if self._nConflicts > 0:
	    raise SpecError, ("%s" % ("\n".join(lines)))

	# Make sure to let the user know about unused symbols if verbosity is
	# enabled, and there weren't any conflicts to cause notification via an
	# exception.
	if self._verbose:
	    ntokens = len(self._tokens) - 1
	    nnonterms = len(self._nonterms) - 1
	    nproductions = len(self._productions) - 1
	    lines.append(
	      "Parsing.Spec: %d token%s, %d non-terminal%s, %d production%s" \
	      % (ntokens, ("s", "")[ntokens == 1], \
	      nnonterms, ("s", "")[nnonterms == 1], \
	      nproductions, ("s", "")[nproductions == 1]))
	    sys.stdout.write("%s\n" % "\n".join(lines))

    # Compute the first sets for all symbols.
    def _firstSets(self):
	# Terminals.
	# first(X) is X for terminals.
	for sym in self._tokens.itervalues():
	    sym.firstSetMerge(sym)

	# Non-terminals.
	#
	# Repeat the following loop until no more symbols can be added to any
	# first set.
	done = False
	while not done:
	    done = True
	    for name in self._nonterms:
		sym = self._nonterms[name]
		for prod in sym.productions:
		    # Merge epsilon if there is an empty production.
		    if len(prod.rhs) == 0:
			if not sym.firstSetMerge(epsilon):
			    done = False

		    # Iterate through the RHS and merge the first sets into
		    # this symbol's, until a preceding symbol's first set does
		    # not contain epsilon.
		    for elm in prod.rhs:
			containsEpsilon = False
			for elmSym in elm.firstSet:
			    if not sym.firstSetMerge(elmSym):
				done = False
			    if elmSym == epsilon:
				containsEpsilon = True
			if not containsEpsilon:
			    break

    # Compute the follow sets for all symbols.
    def _followSets(self):
	self._startSym.followSet = [epsilon]

	# Repeat the following loop until no more symbols can be added to any
	# follow set.
	done = False
	while not done:
	    done = True
	    for name in self._nonterms:
		sym = self._nonterms[name]
		for prod in sym.productions:
		    # For all A ::= aBb, merge first(b) into follow(B).
		    for i in xrange(len(prod.rhs) - 1):
			for j in xrange(i+1, len(prod.rhs)):
			    if not prod.rhs[i].followSetMerge( \
			      prod.rhs[j].firstSet):
				done = False
			    if epsilon not in prod.rhs[j].firstSet:
				break

		    # For A ::= ab, or A ::= aBb where first(b) contains <e>,
		    # merge follow(A) into follow(B).
		    for i in xrange(len(prod.rhs)-1, -1, -1):
			if not prod.rhs[i].followSetMerge(prod.lhs.followSet):
			    done = False
			if epsilon not in prod.rhs[i].firstSet:
			    break

    # Compute the collection of sets of LR(1) items.
    def _items(self):
	# Add {[S' ::= * S $., <e>]} to _itemSets.
	tItemSet = ItemSet()
	tItem = Item(self._startProd, 0, [epsilon])
	tItemSet.append(tItem)
	tItemSet.closure()
	self._itemSets.append(tItemSet)

	# List of state numbers that need to be processed.
	worklist = [0]
	if self._verbose:
	    nwork = len(worklist)
	    print "Parsing.Spec: Generating LR(1) itemset collection... ",
	    sys.stdout.write("+")
	    sys.stdout.flush()

	# itemSetsHash uses itemsets as keys.  A value is a list of _itemSets
	# indices; these itemsets are the ones referred to the key itemset.
	itemSetsHash = {tItemSet: [0]}

	syms = self._tokens.values() + self._nonterms.values()
	while len(worklist) > 0:
	    if self._verbose:
		if abs(len(worklist) - nwork) >= 10:
		    nwork = len(worklist)
		    sys.stdout.write("[%d/%d]" % \
		      (len(worklist), len(self._itemSets)))
		    sys.stdout.flush()

	    i = worklist.pop(0)
	    itemSet = self._itemSets[i]
	    for sym in syms:
		gotoSet = itemSet.goto(sym)
		if len(gotoSet) > 0:
		    merged = False
		    if gotoSet in itemSetsHash:
			for j in itemSetsHash[gotoSet]:
			    mergeSet = self._itemSets[j]
			    if mergeSet.weakCompat(gotoSet):
				merged = True
				if mergeSet.merge(gotoSet):
				    # Process worklist in MRU order.  This
				    # causes a depth-first traversal.
				    if j in worklist:
					worklist.remove(j)
				    else:
					if self._verbose:
					    sys.stdout.write(".")
					    sys.stdout.flush()
				    worklist.insert(0, j)
				break
		    if not merged:
			gotoSet.closure()
			worklist.append(len(self._itemSets))
			if gotoSet not in itemSetsHash:
			    itemSetsHash[gotoSet] = [len(self._itemSets)]
			else:
			    itemSetsHash[gotoSet].append(len(self._itemSets))
			self._itemSets.append(gotoSet)
			if self._verbose:
			    sys.stdout.write("+")
			    sys.stdout.flush()

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()
	self._itemSetsHash = itemSetsHash

    # Compute LR parsing tables.
    def _lr(self):
	# The collection of sets of LR(1) items already exists.
	assert len(self._itemSets) > 0
	assert len(self._action) == 0
	assert len(self._goto) == 0
	assert self._startState == None
	assert self._nConflicts == 0

	if self._verbose:
	    print \
	      "Parsing.Spec: Generating LR(1) parsing tables (%d state%s)... " \
	      % (len(self._itemSets), \
	      ("s", "")[len(self._itemSets) == 1]),
	    sys.stdout.flush()

	itemSetsHash = self._itemSetsHash

	for itemSet in self._itemSets:
	    if self._verbose:
		sys.stdout.write(".")
		sys.stdout.flush()
	    #===================================================================
	    # _action.
	    state = {}
	    self._action.append(state)
	    for item in itemSet:
		# X ::= a*Ab
		if item.dotPos < len(item.production.rhs):
		    sym = item.production.rhs[item.dotPos]
		    if isinstance(sym, TokenSpec):
			itemSetB = itemSet.goto(sym)
			for i in itemSetsHash[itemSetB]:
			    itemSetC = self._itemSets[i]
			    if itemSetC.weakCompat(itemSetB):
				self._actionAppend(state, sym, ShiftAction(i))

		    # Check if this is the start state.
		    if self._startState == None \
		      and item.production.lhs == self._startSym \
		      and item.dotPos == 0:
			assert len(item.production.rhs) == 2
			self._startState = len(self._action) - 1
		# X ::= a*
		elif item.dotPos == len(item.production.rhs):
		    for lookahead in item.lookahead.iterkeys():
			self._actionAppend(state, lookahead, \
			  ReduceAction(item.production))
		else:
		    assert False
	    #===================================================================
	    # _goto.
	    state = {}
	    self._goto.append(state)
	    for nonterm in self._nonterms.itervalues():
		itemSetB = itemSet.goto(nonterm)
		if itemSetB in itemSetsHash:
		    for i in itemSetsHash[itemSetB]:
			itemSetC = self._itemSets[i]
			if itemSetC.weakCompat(itemSetB):
			    assert nonterm not in state
			    state[nonterm] = i

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()

    # Add a symbol action to state, if the action doesn't already exist.
    def _actionAppend(self, state, sym, action):
	assert type(state) == dict
	assert isinstance(sym, SymbolSpec)
	assert isinstance(action, Action)

	if sym not in state:
	    state[sym] = [action]
	else:
	    actions = state[sym]
	    if action not in actions:
		state[sym].append(action)

    # Look for action ambiguities and resolve them if possible.
    def _disambiguate(self):
	assert self._nActions == 0
	assert self._nConflicts == 0
	assert self._nImpure == 0

	if self._verbose:
	    print "Parsing.Spec: Disambiguating LR(1) parsing tables... ",
	    sys.stdout.flush()

	for stateInd in xrange(len(self._action)):
	    state = self._action[stateInd]
	    if self._verbose:
		vRes = "."
		vNConflicts = 0
	    for sym in state:
		nConflicts = 0
		acts = [act for act in state[sym]]
		# Construct a list that corresponds to acts; each element
		# indicates whether to preserve the action.
		actStats = [True] * len(acts)

		# Fill in the cells of actStats.
		for i in xrange(len(acts)):
		    actI = acts[i]
		    for j in xrange(i+1, len(acts)):
			actJ = acts[j]
			res = self._resolve(sym, actI, actJ)
			if res == "neither":
			    actStats[i] = False
			    actStats[j] = False
			elif res == "old":
			    actStats[j] = False
			elif res == "both":
			    pass
			elif res == "new":
			    actStats[i] = False
			elif res == "err":
			    actStats[i] = False
			    actStats[j] = False
			    nConflicts += 1
			else:
			    assert False

		# Look for actions that can coexist or dominate all other
		# actions.
		newActs = []
		for j in xrange(len(acts)):
		    if actStats[j]:
			newActs.append(acts[j])
		# Replace the action set if there exists a valid resolution
		# among the actions.
		if len(newActs) > 0 or nConflicts == 0:
		    if self._verbose:
			if len(newActs) != len(acts):
			    vRes = "_"
		    state[sym] = newActs
		    nConflicts = 0
		elif self._verbose:
		    vNConflicts += nConflicts

		nActions = len(state[sym])
		if nActions > 1:
		    nImpure = nActions
		else:
		    nImpure = 0

		# Update summary stats.
		self._nActions += nActions
		self._nConflicts += nConflicts
		self._nImpure += nImpure

	    if self._verbose:
		if vNConflicts == 0:
		    sys.stdout.write("%s" % vRes)
		else:
		    sys.stdout.write("[%d:%d]" % (stateInd, vNConflicts))
		sys.stdout.flush()

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()

    # Compute how to resolve an action conflict.
    #
    # ret: "neither" : Discard both.
    #      "old"     : Keep old.
    #      "both"    : Keep both.
    #      "new"     : Keep new.
    #      "err"     : Unresolvable conflict.
    def _resolve(self, sym, oldAct, newAct):
	if type(oldAct) == ShiftAction:
	    oldPrec = sym.prec
	elif type(oldAct) == ReduceAction:
	    oldPrec = oldAct.production.prec
	else:
	    assert False

	if type(newAct) == ShiftAction:
	    newPrec = sym.prec
	elif type(newAct) == ReduceAction:
	    newPrec = newAct.production.prec
	else:
	    assert False

	if oldPrec in newPrec.dominators:
	    # Discard new action.
	    ret = "old"
	elif newPrec in oldPrec.dominators:
	    # Discard old action.
	    ret = "new"
	elif oldPrec in newPrec.equiv:
	    assert newPrec in oldPrec.equiv

	    if oldPrec.assoc == "split" or newPrec.assoc == "split":
		ret = "both"
	    elif type(newAct) == type(oldAct):
		assert type(newAct) == ReduceAction
		assert type(oldAct) == ReduceAction
		# Fatal reduce/reduce conflict.
		ret = "err"
	    else:
		if oldPrec.assoc != "fail" and newPrec.assoc != "fail" \
		  and oldPrec.assoc != newPrec.assoc:
		    # Conflicting associativity.
		    ret = "err"
		else:
		    # Determine associativity.  If only one of the actions has
		    # %fail associativity, it is overridden by the other.
		    if oldPrec.assoc == "fail":
			assoc = newPrec.assoc
		    else:
			assoc = oldPrec.assoc
		    assert assoc in ["fail", "nonassoc", "left", "right"]

		    if assoc == "fail":
			ret = "err"
		    elif assoc == "left":
			if type(oldAct) == ShiftAction:
			    ret = "new"
			else:
			    assert type(newAct) == ShiftAction
			    ret = "old"
		    elif assoc == "right":
			if type(oldAct) == ShiftAction:
			    ret = "old"
			else:
			    assert type(newAct) == ShiftAction
			    ret = "new"
		    elif assoc == "nonassoc":
			ret = "neither"
		    else:
			assert False
	else:
	    if newPrec in oldPrec.equiv:
		print "%r <--> %r" % (oldPrec, newPrec)
	    assert newPrec not in oldPrec.equiv
	    # No specified relationship between precedences.
	    ret = "err"

	return ret

class Lr(object):
    """
LR(1) parser.  The Lr class uses a Spec instance in order to parse
input that is fed to it via the token() method, and terminated via the
eoi() method.
"""
    def __init__(self, spec):
	if __debug__:
	    if type(self) == Lr:
		assert spec.pureLR
	assert spec._nConflicts == 0
	self._spec = spec
	self.reset()
	self._verbose = False

    def __getSpec(self): return self._spec
    def __setSpec(self, spec): return AttributeError
    spec = property(__getSpec, __setSpec)

    def __getStart(self): return self._start
    def __setStart(self, start): raise AttributeError
    start = property(__getStart, __setStart, """
A list of parsing results.  For LR parsing, there is only ever one
result, but for compatibility with the Glr interface, start is a
list.
""")

    def __getVerbose(self): return self._verbose
    def __setVerbose(self, verbose):
	assert type(verbose) == bool
	self._verbose = verbose
    verbose = property(__getVerbose, __setVerbose)

    def reset(self):
	self._start = None
	self._stack = [(Epsilon(self), 0)]

    def token(self, token):
	"""
Feed a token to the parser.
"""
	tokenSpec = self._spec._sym2spec[type(token)]
	self._act(token, tokenSpec)

    def eoi(self):
	"""
Signal end-of-input to the parser.
"""
	token = EndOfInput(self)
	self.token(token)

	assert self._stack[-1][0] == token # <$>.
	if self._verbose:
	    self._printStack()
	    print "   --> accept"
	self._stack.pop()

	top = self._stack[-1]
	self._start = [self._stack[1][0]]
	assert self._start[0].symSpec == self._spec._userStartSym

    def _act(self, sym, symSpec):
	if self._verbose:
	    self._printStack()
	    print "INPUT: %r" % sym

	while True:
	    top = self._stack[-1]
	    if symSpec not in self._spec._action[top[1]]:
		raise SyntaxError, ("Unexpected token: %r" % sym)

	    actions = self._spec._action[top[1]][symSpec]
	    assert len(actions) == 1
	    action = actions[0]

	    if self._verbose:
		print "   --> %r" % action
	    if type(action) == ShiftAction:
		self._stack.append((sym, action.nextState))
		break
	    else:
		assert type(action) == ReduceAction
		self._reduce(action.production)

	    if self._verbose:
		self._printStack()

    def _printStack(self):
	    print "STACK:",
	    for node in self._stack:
		print "%r" % node[0],
	    print
	    print "      ",
	    for node in self._stack:
		print "%r%s" % (node[1], \
		  (" " * (len("%r" % node[0]) - len("%r" % node[1])))),
	    print

    def _reduce(self, production):
	nRhs = len(production.rhs)
	rhs = []
	for i in xrange(len(self._stack) - nRhs, len(self._stack)):
	    rhs.append(self._stack[i][0])

	r = self._production(production, rhs)

	for i in xrange(nRhs):
	    self._stack.pop()

	top = self._stack[-1]
	self._stack.append((r, self._spec._goto[top[1]][production.lhs]))

    def _production(self, production, rhs):
	sym = production.lhs.nontermType(self)
	nRhs = len(rhs)
	assert nRhs == len(production.rhs)
	r = production.method(sym, *rhs)

	# Python's method definition syntax makes returning self from %reduce
	# methods cumbersome, so translate None here.
	if r == None:
	    r = sym

	return r

#===============================================================================
# Begin graph-structured stack (GSS) classes.
#

class Gss(list):
    """Graph-structured stack."""
    def __init__(self, glr):
	list.__init__(self)

	self._glr = glr

class Gsse(object):
    """Graph-structured stack edge."""
    def __init__(self, below, above, value):
	self.node = below
	above._edges.append(self)
	self.value = value

    def __repr__(self):
	return "{%r}" % self.value

    def __eq__(self, other):
	if self.node != other.node \
	  or self.value != other.value:
	    return False
	return True

class Gssn(object):
    """Graph-structured stack node."""
    def __init__(self, below, value, nextState):
	assert isinstance(below, Gssn) or below == None

	self._edges = []
	if below != None:
	    Gsse(below, self, value)
	self.nextState = nextState

    def __repr__(self):
	return "[%d]" % self.nextState

    def __getEdge(self):
	assert len(self._edges) == 1
	return self._edges[0]
    def __setEdge(self): raise AttributeError
    edge = property(__getEdge, __setEdge)

    def edges(self):
	for edge in self._edges:
	    yield edge

    def nodes(self):
	for edge in self._edges:
	    yield edge.node

    # Iterate over all paths of length pathLen.  Path length is measured as the
    # number of edges in the path, so a path of length 0 still consists of a
    # single node.
    #
    # Each path is encoded as a list that alternates between nodes and edges,
    # where the first and last elements are always nodes.
    #
    # <e>-grammars can cause cycles, which requires that we avoid infinite
    # recursion.
    def paths(self, pathLen=None):
	assert ((type(pathLen) == int and pathLen >= 0) or pathLen == None)

	for path in self._pathsRecurse(pathLen, []):
	    yield path

    def _pathsRecurse(self, pathLen, path):
	path.insert(0, self)
	if pathLen == None and len(self._edges) == 0:
	    yield path[:]
	elif pathLen != None and len(path) - 1 == pathLen * 2:
	    yield path[:]
	else:
	    for edge in self.edges():
		# Avoid infinite recursion due to <e>-production cycles.
		if len(path) < 3 or edge != path[1]:
		    path.insert(0, edge)
		    for x in edge.node._pathsRecurse(pathLen, path):
			yield x
		    path.pop(0)
	path.pop(0)

#
# End graph-structured stack (GSS) classes.
#===============================================================================

class Glr(Lr):
    """
GLR parser.  The Glr class uses a Spec instance in order to parse input
that is fed to it via the token() method, and terminated via the eoi()
method.
"""
    def __init__(self, spec):
	Lr.__init__(self, spec)

    def reset(self):
	self._start = None

	# Initialize with a stack that is in the start state.
	self._gss = Gss(self)
	top = Gssn(None, None, 0)
	self._gss.append(top)

	self._paths = []

    def token(self, token):
	"""
Feed a token to the parser.
"""
	if self._verbose:
	    print "%s" % ("-" * 80)
	    print "INPUT: %r" % token
	tokenSpec = self._spec._sym2spec[type(token)]
	self._act(token, tokenSpec)
	if len(self._gss) == 0:
	    raise SyntaxError, ("Unexpected token: %r" % token)

    def eoi(self):
	"""
Signal end-of-input to the parser.
"""
	token = EndOfInput(self)
	self.token(token)

	# Gather the start symbols from the stacks.
	self._start = []
	for top in self._gss:
	    for path in top.paths():
		assert len(path) == 5
		if self._verbose:
		    print "   --> accept %r" % path
		edge = path[1]
		assert isinstance(edge.value, Nonterm)
		assert edge.value.symSpec == self._spec._userStartSym
		self._start.append(edge.value)

	if len(self._start) == 0:
	    raise SyntaxError, "Unexpected end of input"

	if self._verbose:
	    print "Start: %r" % self._start
	    print "%s" % ("-" * 80)

    def _act(self, sym, symSpec):
	self._reductions(sym, symSpec)
	self._shifts(sym, symSpec)

    def _reductions(self, sym, symSpec):
	# epsilons is a dictionary that maps production-->[tops].  The purpose
	# is to avoid repeating the same epsilon production on a particular
	# stack top.  Ordinary productions do not require this care because we
	# can notice when a path has already been used for a production.
	epsilons = {}

	if self._verbose:
	    nReduces = 0

	# Enqueue work.
	workQ = []
	i = 0
	while i < len(self._gss):
	    top = self._gss[i]
	    if symSpec not in self._spec._action[top.nextState]:
		# Unexpected token for this stack.
		self._gss.pop(i)
	    else:
		for action in self._spec._action[top.nextState][symSpec]:
		    if type(action) == ReduceAction:
			if len(action.production.rhs) == 0:
			    if action.production not in epsilons:
				assert len([path for path in top.paths(0)]) == 1
				path = [p for p in top.paths(0)][0]
				epsilons[action.production] = [top]
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(a) %r" % \
				      action.production
				    print "                  %r" % path
			    elif top not in epsilons[action.production]:
				assert len([path for path in top.paths(0)]) == 1
				path = [p for p in top.paths(0)][0]
				epsilons[action.production].append(top)
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(b) %r" % \
				      action.production
				    print "                  %r" % path
			else:
			    # Iterate over all reduction paths through stack and
			    # enqueue them.
			    for path in top.paths(len(action.production.rhs)):
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(c) %r" % \
				      action.production
				    print "                  %r" % path
		i += 1

	# Process the work queue.
	while len(workQ) > 0:
	    (path, production) = workQ.pop(0)

	    if self._verbose:
		print "   --> reduce %r" % production
		print "              %r" % path
		nReduces += 1

	    self._reduce(workQ, epsilons, path, production, symSpec)

	if self._verbose:
	    if nReduces > 0:
		self._printStack()

    def _reduce(self, workQ, epsilons, path, production, symSpec):
	assert len(path[1::2]) == len(production.rhs)

	# Build the list of RHS semantic values to pass to the reduction action.
	rhs = [edge.value for edge in path[1::2]]

	# Call the user reduction method.
	r = self._production(production, rhs)

	below = path[0]
	done = False
	for top in self._gss:
	    if top.nextState == \
	      self._spec._goto[below.nextState][production.lhs]:
		# top is compatible with the reduction result we want to add to
		# the set of stack tops.
		for edge in top.edges():
		    if edge.node == below:
			# There is already a below<--top link, so merge
			# competing interpretations.
			if self._verbose:
			    print "   --> merge %r <--> %r" % (edge.value, r)
			value = production.lhs.nontermType.merge(edge.value, r)
			if self._verbose:
			    if value == edge.value:
				print "             %s" % \
				  ("-" * len("%r" % edge.value))
			    else:
				print "             %s      %s" % \
				  ((" " * len("%r" % edge.value)), \
				  "-" * len("%r" % r))
			edge.value = value
			done = True
			break
		if not done:
		    # Create a new below<--top link.
		    edge = Gsse(below, top, r)
		    if self._verbose:
			print "   --> shift(b) %r" % top

		    # Enqueue reduction paths that were created as a result of
		    # the new link.
		    self._enqueueLimitedReductions(workQ, epsilons, edge, \
		      symSpec)
		    done = True
		break
	if not done:
	    # There is no compatible stack top, so create a new one.
	    top = Gssn(below, r, \
	      self._spec._goto[below.nextState][production.lhs])
	    self._gss.append(top)
	    if self._verbose:
		print "   --> shift(c) %r" % \
		  self._spec._goto[below.nextState][production.lhs]
	    self._enqueueLimitedReductions(workQ, epsilons, top.edge, symSpec)

    # Enqueue paths that incorporate edge.
    def _enqueueLimitedReductions(self, workQ, epsilons, edge, symSpec):
	for top in self._gss:
	    if symSpec in self._spec._action[top.nextState]:
		for action in self._spec._action[top.nextState][symSpec]:
		    if type(action) == ReduceAction:
			if len(action.production.rhs) == 0:
			    if self._spec._goto[top.nextState] \
			      [action.production.lhs] == top.nextState:
				# Do nothing, since enqueueing a reduction
				# would result in performing the same reduction
				# twice.
				pass
			    elif action.production not in epsilons:
				path = [top]
				epsilons[action.production] = [top]
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(d) %r" % \
				      action.production
				    print "                  %r" % path
			    elif top not in epsilons[action.production]:
				path = [top]
				epsilons[action.production].append(top)
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(e) %r" % \
				      action.production
				    print "                  %r" % path
			else:
			    # Iterate over all reduction paths through stack and
			    # enqueue them if they incorporate edge.
			    for path in top.paths(len(action.production.rhs)):
				if edge in path[1::2]:
				    workQ.append((path, action.production))
				    if self._verbose:
					print "   --> enqueue(f) %r" % \
					  action.production
					print "                  %r" % path

    def _shifts(self, sym, symSpec):
	prevGss = self._gss
	self._gss = Gss(self)

	if self._verbose:
	    nShifts = 0

	for topA in prevGss:
	    if symSpec in self._spec._action[topA.nextState]:
		for action in self._spec._action[topA.nextState][symSpec]:
		    if type(action) == ShiftAction:
			merged = False
			for topB in self._gss:
			    if topB.nextState == topA.nextState:
				Gsse(topA, topB, sym)
				merged = True
				break
			if not merged:
			    top = Gssn(topA, sym, action.nextState)
			    self._gss.append(top)
			    if self._verbose:
				print "   --> shift(a) %d" % action.nextState
				nShifts += 1
	if self._verbose:
	    if nShifts > 0:
		self._printStack()

    def _printStack(self):
	i = 0
	for top in self._gss:
	    for path in top.paths():
		if i == 0:
		    print "STK 0:",
		else:
		    print "    %d:" % i,
		for elm in path:
		    print "%r" % elm,
		print
		i += 1

#===============================================================================
# Copyright (c) 2007 <NAME> <<EMAIL>>
#
# 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.
#===============================================================================
#
# Release history:
#
# 1.3 (8 August 2007): Retroactively number public releases.
#
#                      Back-port to Python 2.4.
#
#                      Remove some magic surrounding epsilon, in order to
#                      generalize/simplify.
#
# 1.2 (6 May 2007): Fix some off-by-one errors in production count reporting.
#
#                   Add some missing code that helps detect which definitions
#                   are used/unused when building the parser.
#
# 1.1 (22 March 2007): Optimize/generalize Lr._production() by using argument
#                      list expansion.
#
# 1.0 (19 March 2007): Initial public release.
#
#===============================================================================
"""
The Parsing module implements an LR(1) parser generator, as well as the
runtime support for using a generated parser, via the Lr and Glr parser
drivers.  There is no special parser generator input file format, but the
parser generator still needs to know what classes/methods correspond to
various aspects of the parser.  This information is specified via
docstrings, which the parser generator introspects in order to generate a
parser.  Only one parser specification can be embedded in each module, but
it is possible to share modules between parser specifications so that, for
example, the same token definitions can be used by multiple parser
specifications.

The parsing tables are LR(1), but they are generated using a fast algorithm
that avoids creating duplicate states that result when using the generic
LR(1) algorithm.  Creation time and table size are on par with the LALR(1)
algorithm.  However, LALR(1) can create reduce/reduce conflicts that don't
exist in a true LR(1) parser.  For more information on the algorithm, see:

    A Practical General Method for Constructing LR(k) Parsers
    <NAME>
    Acta Informatica 7, 249-268 (1977)

Parsing table generation requires non-trivial amounts of time for large
grammars.  Internal pickling support makes it possible to cache the most
recent version of the parsing table on disk, and use the table if the
current parser specification is still compatible with the one that was used
to generate the pickled parsing table.  Since the compatibility checking is
quite fast, even for large grammars, this removes the need to use the
standard code generation method that is used by most parser generators.

Parser specifications are encapsulated by the Spec class.  Parser instances
use Spec instances, but are themselves based on separate classes.  This
allows multiple parser instances to exist simultaneously, without requiring
multiple copies of the parsing tables.  There are two separate parser driver
classes:

  Lr : Standard Characteristic Finite State Machine (CFSM) driver, based on
       unambiguous LR(1) parsing tables.  This driver is faster than the Glr
       driver, but it cannot deal with all parsing tables that the Glr
       driver can.

  Glr : Generalized LR driver, capable of tracking multiple parse trees
        simultaneously, if the %split precedence is used to mark ambiguous
        actions.  This driver is closely based on Elkhound's design, which
        is described in a technical report:

            Elkhound: A Fast, Practical GLR Parser Generator
            <NAME>
            Report No. UCB/CSD-2-1214 (December 2002)
            http://www.cs.berkeley.edu/~smcpeak/elkhound/

Parser generator directives are embedded in docstrings, and must begin with
a '%' character, followed immediately by one of several keywords:

    Precedence : %fail %nonassoc %left %right %split
         Token : %token
  Non-terminal : %start %nonterm
    Production : %reduce

All of these directives are associated with classes except for %reduce.
%reduce is associated with methods within non-terminal classes.  The Parsing
module provides base classes from which precedences, tokens, and
non-terminals must be derived.  This is not as restrictive as it sounds,
since there is nothing preventing, for example, a master Token class that
subclasses Parsing.Token, which all of the actual token types then subclass.
Also, nothing prevents using multiple inheritance.

Folowing are the base classes to be subclassed by parser specifications:

  * Precedence
  * Token
  * Nonterm

The Parsing module implements the following exception classes:

  * Exception
  * SpecError
  * SyntaxError
  * AttributeError
"""
__all__ = ["Exception", "SpecError", "SyntaxError", "AttributeError",
	   "Nonterm", "Parser", "Precedence", "Spec", "Token", "Lr", "Glr"]

import cPickle
import exceptions
import re
import sys
import types

#===============================================================================
# Begin exceptions.
#

class Exception(exceptions.Exception):
    """
Top level Parsing exception class, from which all other Parsing
exception classes inherit.
"""

class AttributeError(Exception, exceptions.AttributeError):
    """
Attribute error, no different from the builtin exception, except that it
also derives from Parsing.Exception.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

class SpecError(Exception):
    """
Specification error exception.  SpecError arises when the Spec
introspection machinery detects an error either during docstring parsing
or parser specification generation.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

class SyntaxError(Exception, exceptions.SyntaxError):
    """
Parser syntax error.  SyntaxError arises when a Parser instance detects
a syntax error according to the Spec it is using, for the input being
fed to it.
"""
    def __init__(self, str):
	self._str = str

    def __str__(self):
	return self._str

#
# End exceptions.
#===============================================================================

class Precedence(object):
    """
Precedences can be associated with tokens, non-terminals, and
productions.  Precedence isn't as important for GLR parsers as for LR
parsers, since GLR parsing allows for parse-time resolution of
ambiguity.  Still, precedence can be useful for reducing the volume of
ambiguities that must be dealt with at run-time.

There are five precedence types: %fail, %nonassoc, %left, %right, and
%split.  Each precedence can have relationships with other precedences:
<, >, or =.  These relationships specify a directed acyclic graph (DAG),
which is used to compute the transitive closures of relationships among
precedences.  If no path exists between two precedences that are
compared during conflict resolution, parser generation fails.  < and >
are reflexive; it does not matter which is used.  Conceptually, the =
relationship causes precedences to share a node in the DAG.

During conflict resolution, an error results if no path exists in the
DAG between the precedences under consideration.  When such a path
exists, the highest precedence non-terminal or production takes
precedence.  Associativity only comes into play for shift/reduce
conflicts, where the terminal and the production have equivalent
precedences (= relationship).  In this case, the non-terminal's
associativity determines how the conflict is resolved.

The %fail and %split associativities are special because they can be
mixed with other associativities.  During conflict resolution, if
another action has non-%fail associativity, then the %fail (lack of)
associativity is overridden.  Similarly, %split associativity overrides
any other associativity.  In contrast, any mixture of associativity
between %nonassoc/%left/%right causes an unresolvable conflict.

       %fail : Any conflict is a parser-generation-time error.

               A pre-defined precedence, [none], is provided.  It has
               %fail associativity, and has no pre-defined precedence
               relationships.

   %nonassoc : Resolve shift/reduce conflicts by removing both
               possibilities, thus making conflicts a parse-time error.

       %left : Resolve shift/reduce conflicts by reducing.

      %right : Resolve shift/reduce conflicts by shifting.

      %split : Do not resolve conflicts; the GLR algorithm will split
               the parse stack when necessary.

               A pre-defined precedence, [split], is provided.  It has
               %split associativity, and has no pre-defined precedence
               relationships.

By default, all symbols have [none] precedence.  Each production
inherits the precedence of its left-hand-side nonterminal's precedence
unless a precedence is manually specified for the production.

Following are some examples of how to specify precedence classes:

  class P1(Parsing.Precedence):
      "%split p1"

  class p2(Parsing.Precedence):
      "%left" # Name implicitly same as class name.

  class P3(Parsing.Precedence):
      "%left p3 >p2" # No whitespace is allowed between > and p2.

  class P4(Parsing.Precedence):
      "%left p4 =p3" # No whitespace is allowed between = and p3.
"""
    def __init__(self, name, assoc, relationships):
	assert assoc in ["fail", "nonassoc", "left", "right", "split"]
	assert type(relationships) == dict

	self.name = name
	self.assoc = assoc
	self.relationships = relationships # Raw relationships specification.

	self.equiv = [self] # Set.  Precedences that have equivalent precedence.
	self.dominators = [] # Set.  Precedences that have higher precedence.

    def __repr__(self):
	equiv = [prec.name for prec in self.equiv]
	equiv.sort()
	domin = [prec.name for prec in self.dominators]
	domin.sort()
	return "[%%%s %s ={%s} <{%s}]" % (self.assoc, self.name, \
	  ",".join(equiv), ",".join(domin))

    # Important for pickling/unpickling.
    def __eq__(self, other):
	return self is other

class SymbolSpec(object):
    seq = 0

    def __init__(self, name, prec):
	assert type(name) == str

	self.name = name
	self.prec = prec
	self.firstSet = [] # Set.
	self.followSet = [] # Set.

	# Used for ordering symbols and hashing.
	self.seq = SymbolSpec.seq
	SymbolSpec.seq += 1

    def __repr__(self):
	return "%s" % self.name

    def __cmp__(self, other):
	return cmp(self.seq, other.seq)

    def __eq__(self, other):
	assert isinstance(other, SymbolSpec)
	return self.seq == other.seq

    def firstSetMerge(self, sym):
	if sym not in self.firstSet:
	    self.firstSet.append(sym)
	    return False
	else:
	    return True

    def followSetMerge(self, set):
	ret = True
	for sym in set:
	    if sym != epsilon and sym not in self.followSet:
		self.followSet.append(sym)
		ret = False
	return ret

class String(list):
    def __init__(self, args=[]):
	list.__init__(self, args)

	self.hash = self._hash()

    def __cmp__(self, other):
	assert isinstance(other, String)
	minLen = min(len(self), len(other))
	for i in xrange(minLen):
	    if self[i] < other[i]:
		return -1
	    elif self[i] > other[i]:
		return 1

	# Prefixes are identical.  Handle trailing characters, if any.
	if len(self) < len(other):
	    return -1
	elif len(self) == len(other):
	    return 0
	else:
	    assert len(self) > len(other)
	    return 1

    def __eq__(self, other):
	if len(self) == len(other):
	    for i in xrange(len(self)):
		if self[i] != other[i]:
		    return False
	    return True
	else:
	    return False

    def _hash(self):
	ret = 5381
	for sym in self:
	    ret = ((ret << 5) + ret) + sym.seq
	    ret &= 0xffffffffffffffff
	return ret

    def __hash__(self):
	return self.hash

class StringSpec(object):
    cache = {}

    def __init__(self, s):
	assert isinstance(s, String)
	for sym in s:
	    assert isinstance(sym, SymbolSpec)

	self.s = s
	if s in StringSpec.cache:
	    self.firstSet = StringSpec.cache[s]
	else:
	    # Calculate the first set for the string encoded by the s vector.
	    self.firstSet = [] # Set.
	    mergeEpsilon = True
	    for sym in self.s:
		hasEpsilon = False
		for elm in sym.firstSet:
		    if elm == epsilon:
			hasEpsilon = True
		    elif sym not in self.firstSet:
			self.firstSet.append(elm)
		if not hasEpsilon:
		    mergeEpsilon = False
		    break
	    # Merge epsilon if it was in the first set of every symbol.
	    if mergeEpsilon:
		self.firstSet.append(epsilon)

	    # Cache the result.
	    StringSpec.cache[s] = self.firstSet

class Symbol(object):
    def __init__(self, symSpec, parser):
	assert isinstance(symSpec, SymbolSpec)
	assert isinstance(parser, Lr)
	self.__symSpec = symSpec
	self.__parser = parser

    def __repr__(self):
	return "%r" % self.symSpec

    def __getSymSpec(self): return self.__symSpec
    def __setSymSpec(self): raise AttributeError
    symSpec = property(__getSymSpec, __setSymSpec)

    def __getParser(self): return self.__parser
    def __setParser(self): raise AttributeError
    parser = property(__getParser, __setParser)

class NontermSpec(SymbolSpec):
    def __init__(self, nontermType, name, qualified, prec):
	assert issubclass(nontermType, Nonterm) # Add forward decl for Lyken.

	SymbolSpec.__init__(self, name, prec)

	self.qualified = qualified
	self.nontermType = nontermType
	self.productions = [] # Set.

class Nonterm(Symbol):
    """
Non-terminal symbols have sets of productions associated with them.  The
productions induce a parse forest on an input token stream.  There is
one special non-terminal, which is denoted via the %start directive,
whereas all other non-terminals are denoted via the %nonterm directive.
In addition to productions (%reduce directives associated with class
methods), the merge() method may be called during resolution of
ambiguous parses.  See the merge() documentation for further details.

Following are examples of how to specify non-terminal classes and their
associated productions:

  class E(Parsing.Nonterm):
      "%start E"
      def __init__(self):
          Parsing.Nonterm.__init__(self)
          # ...

      # Productions.
      def reduceA(self, E, plus, T):
          "%reduce E plus T [split]"
          print "%r ::= %r %r %r." % (self, E, plus, T)

      def reduceB(self, T):
          "%reduce T"

  class T(Parsing.Nonterm):
        "%nonterm" # Name implicitly same as class name.
      def reduceA(self, T, star, F):
          "%reduce T star F"

      def reduceB(self, F):
          "%reduce F [p1]"

  class F(Parsing.Nonterm):
      "%nonterm F [p2]"
      def reduceA(self, lparen, E, rparen):
          "%reduce lparen E rparen"

      def reduceB(self, id):
          "%reduce id"
"""
    def __init__(self, parser):
	assert isinstance(parser, Lr)
	Symbol.__init__(self, parser._spec._sym2spec[type(self)], parser)

    def merge(self, other):
	"""
Merging happens when there is an ambiguity in the input that allows
non-terminals to be part of multiple overlapping series of
reductions.  If no merge() method is specified, the parser will
throw a syntax error upon encountering an ambiguity that confounds
reduction processing.  However, it may be useful to either discard
one of the possible parses, or to explicitly record the ambiguity in
the data structures being created during parsing.  In both of these
cases, the non-terminal-specific merge() is the place to do the
work; merge() returns an object that is stored by the parser onto
the parse stack.  In the case where merge() discards one of the
possible parses, it need only return the parse that is to be
preserved (self or other).

If multiple merges are necessary, they cause a series of merge()
calls.  The first alternative (self) may be the result of a previous
merge() call, whereas other will not have not been merged yet
(unless as the result of merging further down in the parse forest).

The alternative that is discarded is never touched by the parser
again, so if any immediate cleanup is necessary, it should be done
in merge().
"""
	raise SyntaxError, "No merge() for %r; merging %r <--> %r" % \
	  (type(self), self, other)

class Token(Symbol):
    """
Tokens are terminal symbols.  The parser is fed Token instances, which
is what drives parsing.  Typically, the user will define a class that
subclasses Parsing.Token and implement parser-specific machinery there,
then derive all actual token types from that class.

  class Token(Parsing.Token):
      def __init__(self, parser):
	  Parsing.Token.__init__(self, parser)
	  # ...

  class Plus(Token):
      "%token plus [p1]"

  class star(Token):
      "%token star [p2]" # Name implicitly same as class name.

  class lparen(Token):
      "%token [split]"

  class rparen(Token):
      "%token [none]" # [none] not necessary, since it's the default.

  class id(Token):
      "%token"
"""
    def __init__(self, parser):
	assert isinstance(parser, Lr)
	Symbol.__init__(self, parser._spec._sym2spec[type(self)], parser)
	self.__parser = parser

# AKA terminal symbol.
class TokenSpec(SymbolSpec):
    def __init__(self, tokenType, name, prec):
	assert issubclass(tokenType, Token)
	assert type(name) == str
	assert isinstance(prec, Precedence) or type(prec) == str

	SymbolSpec.__init__(self, name, prec)
	self.tokenType = tokenType

# <$>.
class EndOfInput(Token): pass
class EndOfInputSpec(TokenSpec):
    def __init__(self):
	TokenSpec.__init__(self, EndOfInput, "<$>", "none")
eoi = EndOfInputSpec()

# <e>.
class Epsilon(Token): pass
class EpsilonSpec(TokenSpec):
    def __init__(self):
	TokenSpec.__init__(self, Epsilon, "<e>", "none")
epsilon = EpsilonSpec()

class Production(object):
    seq = 0

    def __init__(self, method, qualified, prec, lhs, rhs):
	assert isinstance(prec, Precedence)
	assert isinstance(lhs, NontermSpec)
	if __debug__:
	    for elm in rhs:
		assert isinstance(elm, SymbolSpec)

	self.method = method
	self.qualified = qualified
	self.prec = prec
	self.lhs = lhs
	self.rhs = rhs

	# Used for hashing.
	self.seq = Production.seq
	Production.seq += 1

    def __getstate__(self):
	return (self.qualified, self.prec, self.lhs, self.rhs, self.seq)

    def __setstate__(self, data):
	# Convert qualified name to a function reference.
	(qualified, prec, lhs, rhs, seq) = data
	elms = qualified.split(".")
	method = sys.modules[elms[0]]
	for elm in elms[1:]:
	    method = method.__dict__[elm]

	# Set state.
	self.method = method
	self.qualified = qualified
	self.prec = prec
	self.lhs = lhs
	self.rhs = rhs
	self.seq = seq

    def __repr__(self):
	return "%r ::= %s. [%s]" % \
	  (self.lhs, " ".join(["%r" % elm for elm in self.rhs]), self.prec.name)

    # Optional callback method.
    #
    # Called when a production is reduced.
    def reduce(self, lhs, *rhs): pass

class NontermStart(Nonterm):
    def reduce(self, userStartSym, eoi):
	pass

class Start(Production):
    def __init__(self, startSym, userStartSym):
	Production.__init__(self, none, startSym, userStartSym)

class Item(object):
    def __init__(self, production, dotPos, lookahead):
	assert isinstance(production, Production)
	assert type(dotPos) == int
	assert dotPos >= 0
	assert dotPos <= len(production.rhs)
	assert type(lookahead) == list
	if __debug__:
	    for elm in lookahead:
		assert isinstance(elm, SymbolSpec)

	self.production = production
	self.dotPos = dotPos
	self.lookahead = {}
	for sym in lookahead:
	    self.lookahead[sym] = sym

	self.hash = (dotPos * Production.seq) + production.seq

    def __hash__(self):
	return self.hash

    def __eq__(self, other):
	assert isinstance(other, Item)

	return self.hash == other.hash

    def __cmp__(self, other):
	assert isinstance(other, Item)
	return self.hash.__cmp__(other.hash)

    def __repr__(self):
	strs = []
	strs.append("[%r ::=" % self.production.lhs)
	assert self.dotPos <= len(self.production.rhs)
	i = 0
	while i < self.dotPos:
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(" *")
	while i < len(self.production.rhs):
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	syms = [sym for sym in self.lookahead.iterkeys()]
	syms.sort()
	strs.append("., %s] [%s]" % \
	  ("/".join(["%r" % sym for sym in syms]), \
	  self.production.prec.name))
	
	return "".join(strs)

    def lr0__repr__(self):
	strs = []
	strs.append("%r ::=" % self.production.lhs)
	assert self.dotPos <= len(self.production.rhs)
	i = 0
	while i < self.dotPos:
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(" *")
	while i < len(self.production.rhs):
	    strs.append(" %r" % self.production.rhs[i])
	    i += 1
	strs.append(". [%s]" % self.production.prec.name)

	return "".join(strs)

    def lookaheadInsert(self, sym):
	assert isinstance(sym, SymbolSpec)
	self.lookahead[sym] = sym

    def lookaheadDisjoint(self, other):
	sLookahead = self.lookahead
	oLookahead = other.lookahead

	for sSym in sLookahead.iterkeys():
	    if sSym in oLookahead:
		return False

	for oSym in oLookahead.iterkeys():
	    if oSym in sLookahead:
		return False

	return True

class ItemSet(dict):
    def __init__(self, args=[]):
	dict.__init__(self, args)
	self._added = {}

    def __repr__(self):
	kernel = [item for item in self.iterkeys()]
	kernel.sort()
	added = [item for item in self._added.iterkeys()]
	added.sort()
	return "ItemSet(kernel: %s, added: %r)" % \
	  (", ".join(["%r" % item for item in kernel]), \
	  ", ".join(["%r" % item for item in added]))

    def __hash__(self):
	# This works because integers never overflow, and addition is
	# transitive.
	ret = 0
	for item in self.iterkeys():
	    ret += item.hash
	return ret

    def __eq__(self, other):
	if len(self) != len(other):
	    return False
	for sItem in self.iterkeys():
	    if sItem not in other:
		return False
	return True

    def __iter__(self):
	for item in self.iterkeys():
	    assert item.production.lhs.name == "<S>" or item.dotPos != 0
	    yield item
	for item in self._added.iterkeys():
	    assert item.dotPos == 0
	    assert item.production.lhs.name != "<S>"
	    yield item

    # Merge a kernel item.
    def append(self, item):
	assert item.production.lhs.name == "<S>" or item.dotPos != 0

	if item in self:
	    self[item].lookahead.update(item.lookahead)
	else:
	    tItem = Item(item.production, item.dotPos, item.lookahead.keys())
	    self[tItem] = tItem

    # Merge an added item.
    def addedAppend(self, item):
	assert item.dotPos == 0
	assert item.production.lhs.name != "<S>"

	if item in self._added:
	    lookahead = self._added[item].lookahead
	    oldLen = len(lookahead)
	    lookahead.update(item.lookahead)
	    return (oldLen != len(lookahead))
	else:
	    self._added[item] = item
	    return True

    # Given a list of items, compute their closure and merge the results into
    # the set of added items.
    def _closeItems(self, items):
	# Iterate over the items until no more can be added to the closure.
	i = 0
	while i < len(items):
	    item = items[i]
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) \
	      and isinstance(rhs[dotPos], NontermSpec):
		for lookahead in item.lookahead.keys():
		    string = StringSpec( \
		      String(rhs[dotPos+1:] + [lookahead]))
		    lhs = rhs[dotPos]
		    for prod in lhs.productions:
			tItem = Item(prod, 0, string.firstSet)
			if self.addedAppend(tItem):
			    items.append(tItem)
	    i += 1

    # Calculate and merge the kernel's transitive closure.
    def closure(self):
	items = []
	for item in self.iterkeys():
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) and isinstance(rhs[dotPos], \
	      NontermSpec):
		for lookahead in item.lookahead.iterkeys():
		    string = StringSpec(String(rhs[dotPos+1:] + \
		      [lookahead]))
		    lhs = rhs[dotPos]
		    for prod in lhs.productions:
			tItem = Item(prod, 0, string.firstSet)
			if self.addedAppend(tItem):
			    items.append(tItem)
	self._closeItems(items)

    # Calculate the kernel of the goto set, given a particular symbol.
    def goto(self, sym):
	ret = ItemSet()
	for item in self:
	    rhs = item.production.rhs
	    dotPos = item.dotPos
	    if dotPos < len(rhs) and rhs[dotPos] == sym:
		tItem = Item(item.production, dotPos + 1, item.lookahead.keys())
		ret.append(tItem)
	return ret

    # Merge the kernel of other into this ItemSet, then update the closure.
    # It is not sufficient to copy other's added items, since other has not
    # computed its closure.
    def merge(self, other):
	items = []
	for item in other.iterkeys():
	    if item in self:
		lookahead = self[item].lookahead
		tLookahead = []
		for sym in item.lookahead.iterkeys():
		    if sym not in lookahead:
			lookahead[sym] = sym
			tLookahead.append(sym)
		if len(tLookahead) > 0:
		    tItem = Item(item.production, item.dotPos, tLookahead)
		    items.append(tItem)
	    else:
		tItem = Item(item.production, item.dotPos, \
		  item.lookahead.keys())
		self[tItem] = tItem
		items.append(tItem)

	if len(items) > 0:
	    self._closeItems(items)
	    return True
	else:
	    return False

    # Determine if self and other are weakly compatible, as defined by the
    # Pager(1977) algorithm.
    def weakCompat(self, other):
	# Check for identical kernel LR(0) items, and pair items, for later use.
	if len(self) != len(other):
	    return False
	pairs = []
	for sItem in self.iterkeys():
	    if sItem not in other:
		return False
	    oItem = other[sItem]
	    pairs.append((sItem, oItem))

	# Check for lookahead compatibility.
	for i in xrange(len(pairs)-1):
	    iPair = pairs[i]
	    isItem = iPair[0]
	    ioItem = iPair[1]
	    for j in xrange(i+1, len(pairs)):
		jPair = pairs[j]
		jsItem = jPair[0]
		joItem = jPair[1]

		if isItem.lookaheadDisjoint(joItem) \
		  and ioItem.lookaheadDisjoint(jsItem):
		    pass
		elif not isItem.lookaheadDisjoint(jsItem):
		    pass
		elif not ioItem.lookaheadDisjoint(joItem):
		    pass
		else:
		    return False
	return True

class Action(object):
    """
Abstract base class, subclassed by {Shift,Reduce}Action.
"""
    def __init__(self): pass

class ShiftAction(Action):
    """
Shift action, with assocated nextState.
"""
    def __init__(self, nextState):
	Action.__init__(self)
	self.nextState = nextState

    def __repr__(self):
	return "[shift %r]" % self.nextState

    def __eq__(self, other):
	if not isinstance(other, ShiftAction):
	    return False
	if self.nextState != other.nextState:
	    return False
	return True

class ReduceAction(Action):
    """
Reduce action, with associated production.
"""
    def __init__(self, production):
	Action.__init__(self)
	self.production = production

    def __repr__(self):
	return "[reduce %r]" % self.production

    def __eq__(self, other):
	if not isinstance(other, ReduceAction):
	    return False
	if self.production != other.production:
	    return False
	return True

class Spec(object):
    """
The Spec class contains the read-only data structures that the Parser
class needs in order to parse input.  Parser generation results in a
Spec instance, which can then be shared by multiple Parser instances.
"""
    def __init__(self, modules, pickleFile=None, pickleMode="rw",
		 skinny=True, logFile=None, graphFile=None, verbose=False):
	"""
modules : Either a single module, or a list of modules, wherein to
          look for parser generator directives in docstrings.

pickleFile : The path of a file to use for Spec pickling/unpickling.

pickleMode :  "r" : Unpickle from pickleFile.
              "w" : Pickle to pickleFile.
              "rw" : Unpickle/pickle from/to pickleFile.

skinny : If true, discard all data that are only strictly necessary
         while constructing the parsing tables.  This reduces
         available debugging context, but substantially reduces
         pickle size.

logFile : The path of a file to store a human-readable copy of the
          parsing tables in.

graphFile : The path of a file to store a graphviz representation
            (dot format) of the precedence relationship graph.

verbose : If true, print progress information while generating the
          parsing tables.
"""
	assert pickleFile == None or type(pickleFile) == str
	assert pickleMode in ["rw", "r", "w"]
	assert type(skinny) == bool
	assert logFile == None or type(logFile) == str
	assert graphFile == None or type(graphFile) == str
	assert type(verbose) == bool

	self._skinny = skinny
	self._verbose = verbose

	# Default (no) precedence.
	self._none = Precedence("none", "fail", {})
	self._split = Precedence("split", "split", {})

	# Symbols are maintained as two separate sets so that non-terminals and
	# terminals (tokens) can be operated on separately where needed.
	self._precedences = {self._none.name: self._none,
			     self._split.name: self._split}
	self._nonterms = {}
	self._tokens = {eoi.name: eoi, epsilon.name: epsilon}
	self._sym2spec = {EndOfInput: eoi, Epsilon: epsilon}
	self._productions = []

	self._userStartSym = None
	self._startSym = None
	self._startProd = None

	# Everything below this point is computed from the above (once
	# introspection is complete).

	self._itemSets = [] # Each element corresponds to an element in _action.
	self._itemSetsHash = None
	# LR parsing tables.  The tables conceptually contain one state per row,
	# where each row contains one element per symbol.  The table is
	# conceptually in row-major form, but each row is actually a dictionary.
	# If no entry for a symbol exists for a particular state, then input of
	# that symbol is an error for that state.
	self._action = []
	self._goto = []
	self._startState = None
	self._nActions = 0
	self._nConflicts = 0
	self._nImpure = 0 # Number of LR impurities (does not affect GLR).

	# Introspect modules and generate parse tables.
	if type(modules) == types.ModuleType:
	    # Wrap single module in a list.
	    modules = [modules]
	self._prepare(modules, pickleFile, pickleMode, logFile, graphFile)

    def __getPureLR(self):
	return (self._nConflicts + self._nImpure == 0)
    def __setPureLR(self): raise AttributeError
    pureLR = property(__getPureLR, __setPureLR)

    def __getConflicts(self): return self._nConflicts
    def __setConflicts(self): raise AttributeError
    conflicts = property(__getConflicts, __setConflicts)

    def __repr__(self):
	if self._skinny:
	    # Print a very reduced summary, since most info has been discarded.
	    return "Parsing.Spec: %d states, %d actions (%d split)" % \
	      (len(self._action), self._nActions, self._nImpure)

	lines = []

	#=======================================================================
	lines.append("Precedences:")
	deco = [(prec.name, prec) for prec in self._precedences.itervalues()]
	deco.sort()
	for elm in deco:
	    prec = elm[1]
	    lines.append("  %r" % prec)

	lines.append("Tokens:")
	syms = [sym for sym in self._tokens.itervalues()]
	syms.sort()
	for token in syms:
	    lines.append("  %r %r" % (token, token.prec))
	    lines.append("    First set: %r" % token.firstSet)
	    lines.append("    Follow set: %r" % token.followSet)

	lines.append("Non-terminals:")
	syms = [sym for sym in self._nonterms.itervalues()]
	syms.sort()
	for sym in syms:
	    lines.append("  %r %r" % (sym, sym.prec))
	    lines.append("    First set: %r" % sym.firstSet)
	    lines.append("    Follow set: %r" % sym.followSet)
	    lines.append("    Productions:")
	    prods = sym.productions[:]
	    prods.sort()
	    for prod in prods:
		lines.append("      %r" % prod)

	lines.append("Item sets:")
	for i in xrange(len(self._itemSets)):
	    lines.append("  %d: %r" % (i, self._itemSets[i]))
	#=======================================================================

	ntokens = len(self._tokens) - 1
	nnonterms = len(self._nonterms) - 1
	nproductions = len(self._productions) - 1
	nstates = len(self._action)
	lines.append(("Parsing.Spec: %d token%s, %d non-terminal%s, " + \
	  "%d production%s, %d state%s, %d action%s (%d split):") % \
	  (ntokens, ("s", "")[ntokens == 1], \
	  nnonterms, ("s", "")[nnonterms == 1], \
	  nproductions, ("s", "")[nproductions == 1], \
	  nstates, ("s", "")[nstates == 1], \
	  self._nActions, ("s", "")[self._nActions == 1], \
	  self._nImpure))
	if self.pureLR:
	    lines.append("Algorithm compatibility: GLR, LR")
	elif self._nConflicts == 0:
	    lines.append("Algorithm compatibility: GLR")
	else:
	    lines.append("Algorithm compatibility: None, due to ambiguity")
	lines.append("Parsing tables:")
	for i in xrange(len(self._action)):
	    lines.append("  %s" % ("=" * 78))
	    lines.append("  State %d:%s" % \
	      (i, ("", " (start state)")[self._startState == i]))
	    items = [item for item in self._itemSets[i]]
	    items.sort()
	    for item in items:
		lines.append(" %s%s" % (" " * (len("%d" % i) + 9),
		  item.lr0__repr__()))
	    lines.append("    Goto:")
	    syms = [sym for sym in self._goto[i]]
	    syms.sort()
	    for sym in syms:
		lines.append("    %15r : %r" % (sym, self._goto[i][sym]))
	    lines.append("    Action:")
	    syms = [sym for sym in self._action[i]]
	    syms.sort()
	    for sym in syms:
		for action in self._action[i][sym]:
		    conflict = "   "
		    for other in self._action[i][sym]:
			if action != other:
			    resolution = self._resolve(sym, other, action)
			    if resolution == "err":
				conflict = "XXX"
				break

		    if type(action) == ShiftAction:
			lines.append("%s %15r : %-6s %d [%s]" % \
			  (conflict, sym, "shift", action.nextState, \
			  sym.prec.name))
		    else:
			assert type(action) == ReduceAction
			lines.append("%s %15r : %-6s %r" % \
			  (conflict, sym, "reduce", action.production))

	ret = "\n".join(lines)
	return ret

    def _prepare(self, modules, pickleFile, pickleMode, logFile, graphFile):
	"""
Compile the specification into data structures that can be used by
the Parser class for parsing.
"""
	# Get the grammar specification.
	self._introspect(modules)

	# Augment grammar with a special start symbol and production:
	#
	#   <S> ::= S <$>.
	assert self._startSym == None
	assert isinstance(self._userStartSym, NontermSpec)
	self._startSym = NontermSpec(NontermStart, "<S>",
	  "%s.NontermStart" % __name__, self._none)
	self._startProd = Production(NontermStart.reduce.im_func,
				     "%s.NontermStart.reduce" % __name__,
				     self._none, self._startSym, \
				     [self._userStartSym, eoi])
	self._startSym.productions.append(self._startProd)
	self._nonterms["<S>"] = self._startSym
	self._productions.append(self._startProd)

	# Resolve references in the grammar specification.
	self._references(logFile, graphFile)

	# Check for a compatible pickle.
	compat = self._unpickle(pickleFile, pickleMode)

	if compat == "incompatible":
	    # Create the collection of sets of LR(1) items.
	    self._firstSets()
	    self._followSets()
	    self._items()

	if compat == "compatible":
	    # Just because the pickle was compatible does not mean that it is
	    # valid for parsing.
	    if self._nConflicts != 0:
		raise SpecError, \
		  "Compatible pickle is invalid due to conflicts (%d)" % \
		  self._nConflicts
	if compat in ["itemsets", "incompatible"]:
	    # Generate LR(1) parsing tables.
	    self._lr()

	    # Disambiguate actions.
	    self._disambiguate()

	    # Check for unused or ambiguous definitions, as well as reporting
	    # ambiguities.
	    try:
		self._validate(logFile)
	    finally:
		# Pickle the spec, if method parameters so dictate, even if
		# there were validation errors, so that the pickle might be
		# used in part during later runs.
		self._pickle(pickleFile, pickleMode)
	elif compat == "repickle":
	    # Pickle the spec, if method parameters so dictate.
	    self._pickle(pickleFile, pickleMode)

	if self._skinny:
	    # Discard data that are not needed during parsing.  Note that
	    # _pickle() also discarded data that don't even need to be pickled.
	    del self._precedences
	    del self._nonterms
	    del self._tokens
	    del self._productions

    # Introspect modules and find special parser declarations.  In order to be
    # a special class, the class must both 1) be subclassed from Token or
    # Nonterm, and 2) contain the appropriate %foo docstring.
    def _introspect(self, modules):
	if self._verbose:
	    print ("Parsing.Spec: Introspecting module%s to acquire formal" + \
	    " grammar specification...") % ("s", "")[len(modules) == 1]

	self._precedences["none"] = self._none
	self._precedences["split"] = self._split

	for module in modules:
	    d = module.__dict__
	    for k in d:
		v = d[k]
		if type(v) is types.TypeType and type(v.__doc__) == str:
		    dirtoks = v.__doc__.split(" ")

		    #===========================================================
		    # Precedence.
		    #
		    if issubclass(v, Precedence) and dirtoks[0] in \
		      ["%fail", "%nonassoc", "%left", "%right", "%split"]:
			name = k
			relationships = {}
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'([<>=])([A-Za-z]\w*)').match(tok)
			    if m:
				# Precedence relationship.
				if m.group(2) in relationships:
				    raise SpecError, \
				      ("Duplicate precedence " \
				      + "relationship: %s") \
				      % v.__doc__
				relationships[m.group(2)] = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    if i != 1:
					raise SpecError, \
					  ("Precedence name must come before " \
					  + "relationships: %s") \
					  % v.__doc__
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid precedence specification: %s" % \
				      v.__doc__
			    i += 1

			if name in self._precedences:
			    raise SpecError, \
			      "Duplicate precedence name: %s" % v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Identical token/precedence names: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Identical nonterm/precedence names: %s" % \
			      v.__doc__
			prec = Precedence(name, dirtoks[0][1:], relationships)
			self._precedences[name] = prec
		    #===========================================================
		    # Token.
		    #
		    elif issubclass(v, Token) and dirtoks[0] in ["%token"]:
			name = k
			prec = None
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
			    if m:
				if i < len(dirtoks) - 1:
				    raise SpecError, \
				      ("Precedence must come last in token " \
				      + "specification: %s") % v.__doc__
				prec = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid token specification: %s" % \
				      v.__doc__
			    i += 1
			if name in self._precedences:
			    raise SpecError, \
			      "Identical precedence/token names: %s" % v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Duplicate token name: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Identical nonterm/token names: %s" % v.__doc__
			if prec == None:
			    prec = "none"
			token = TokenSpec(v, name, prec)
			self._tokens[name] = token
			self._sym2spec[v] = token
		    #===========================================================
		    # Nonterm.
		    #
		    elif issubclass(v, Nonterm) and \
		      dirtoks[0] in ["%start", "%nonterm"]:
			name = None
			prec = None
			i = 1
			while i < len(dirtoks):
			    tok = dirtoks[i]
			    m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
			    if m:
				if i < len(dirtoks) - 1:
				    raise SpecError, \
				      ("Precedence must come last in " \
				      + "non-terminal specification: %s") % \
				      v.__doc__
				prec = m.group(1)
			    else:
				m = re.compile(r'([A-Za-z]\w*)').match(tok)
				if m:
				    name = m.group(1)
				else:
				    raise SpecError, \
				      "Invalid non-terminal specification: %s" \
				      % v.__doc__
			    i += 1
			if name == None:
			    name = k
			if prec == None:
			    prec = "none"
			if name in self._precedences:
			    raise SpecError, \
			      "Identical precedence/nonterm names: %s" % \
			      v.__doc__
			if name in self._tokens:
			    raise SpecError, \
			      "Identical token/nonterm names: %s" % v.__doc__
			if name in self._nonterms:
			    raise SpecError, \
			      "Duplicate nonterm name: %s" % v.__doc__
			nonterm = NontermSpec(v, name,
			  "%s.%s" % (module.__name__, name), prec)
			self._nonterms[name] = nonterm
			self._sym2spec[v] = nonterm

			if dirtoks[0] == "%start":
			    # Start symbol.
			    if self._userStartSym != None:
				raise SpecError, \
				  "Only one start non-terminal allowed: %s" \
				  % v.__doc__
			    self._userStartSym = nonterm
		    #===========================================================
	if not isinstance(self._userStartSym, NontermSpec):
	    raise SpecError, "No start symbol specified"

    # Resolve all symbolic (named) references.
    def _references(self, logFile, graphFile):
	# Build the graph of Precedence relationships.
	self._resolvePrec(graphFile)

	# Resolve Token-->Precedence references.
	for token in self._tokens.itervalues():
	    if type(token.prec) == str:
		token.prec = self._precedences[token.prec]

	# Resolve Nonterm-->Precedence references.
	for nonterm in self._nonterms.itervalues():
	    if type(nonterm.prec) == str:
		nonterm.prec = self._precedences[nonterm.prec]

	# Resolve Nonterm-->{Nonterm,Token,Precedence} references.
	for nonterm in self._nonterms.itervalues():
	    d = nonterm.nontermType.__dict__
	    for k in d:
		v = d[k]
		if type(v) is types.FunctionType and type(v.__doc__) == str:
		    dirtoks = v.__doc__.split(" ")
		    if dirtoks[0] == "%reduce":
			rhs = []
			prec = None
			for i in xrange(1, len(dirtoks)):
			    tok = dirtoks[i]
			    m = re.compile(r'([A-Za-z]\w*)').match(tok)
			    if m:
				# Symbolic reference.
				if tok in self._tokens:
				    rhs.append(self._tokens[tok])
				elif tok in self._nonterms:
				    rhs.append(self._nonterms[tok])
				else:
				    raise SpecError, \
				      ("Unknown symbol '%s' in reduction " \
				      + "specification: %s") % (tok, v.__doc__)
			    else:
				m = re.compile(r'\[([A-Za-z]\w*)\]').match(tok)
				if m:
				    # Precedence.
				    if i < len(dirtoks) - 1:
					raise SpecError, \
					  ("Precedence must come last in " \
					  + "reduction specification: %s") % \
					  v.__doc__
				    if m.group(1) not in self._precedences:
					raise SpecError, \
					  ("Unknown precedence in reduction " \
					  + "specification: %s") % v.__doc__
				    prec = self._precedences[m.group(1)]

			if prec == None:
			    # Inherit the non-terminal's precedence.
			    prec = nonterm.prec

			prod = Production(v, "%s.%s" % (nonterm.qualified, k), \
			  prec, nonterm, rhs)
			assert prod not in nonterm.productions
			nonterm.productions.append(prod)
			self._productions.append(prod)
	if self._verbose:
	    ntokens = len(self._tokens) - 1
	    nnonterms = len(self._nonterms) - 1
	    nproductions = len(self._productions) - 1
	    print \
	      "Parsing.Spec: %d token%s, %d non-terminal%s, %d production%s" % \
	      (ntokens, ("s", "")[ntokens == 1], \
	      nnonterms, ("s", "")[nnonterms == 1], \
	      nproductions, ("s", "")[nproductions == 1])

    # Build the graph of Precedence relationships.
    def _resolvePrec(self, graphFile):
	# Resolve symbolic references and populate equiv/dominators.
	for precA in self._precedences.itervalues():
	    for precBName in precA.relationships:
		if precBName not in self._precedences:
		    raise SpecError, \
		      ("Precedence '%s' specifies a relationship with " + \
		      "unknown Precedence '%s'") % (precA, precBName)
		precB = self._precedences[precBName]
		rel = precA.relationships[precBName]
		if rel == "=":
		    precA.equiv.append(precB)
		elif rel == "<":
		    if precB not in precA.dominators:
			precA.dominators.append(precB)
		elif rel == ">":
		    if precA not in precB.dominators:
			precB.dominators.append(precA)
		else:
		    assert False

	# Create equivalence classes for all Precedence classes.  Since the
	# Precedence classes are equivalent, they also share dominator sets.
	for precA in self._precedences.itervalues():
	    for precB in precA.equiv[:]:
		if not precB.equiv is precA.equiv:
		    # Merge the sets of equivalent Precedence classes.
		    for prec in precB.equiv:
			if prec not in precA.equiv:
			    precA.equiv.append(prec)
		    # Share the equiv set.
		    for prec in precA.equiv:
			prec.equiv = precA.equiv

	# Use the equivalence classes to merge dominator sets and share them.
	for precA in self._precedences.itervalues():
	    for precB in precA.equiv[1:]:
		# Merge the sets of dominator Precedence classes.
		for prec in precB.dominators:
		    if prec not in precA.dominators:
			precA.dominators.append(prec)
		# Share the dominator set.
		precB.dominators = precA.dominators

	# Write graphviz precedence graph to graphFile, if graphFile was
	# specified.
	if graphFile != None:
	    f = open(graphFile, "w+")
	    if self._verbose:
		print \
		  "Parsing.Spec: Writing graphviz precedence graph to '%s'..." \
		  % graphFile
	    print >> f, 'digraph Precedence {'
	    print >> f, '    graph [bgcolor=black, labeljust="l"]'
	    print >> f, \
	      ('    node [shape=record, style=filled, color=black, ' + \
	      'fillcolor=gray, fontname=Helvetica, fontsize=10.0]')
	    print >> f, '    edge [color=gray]'
	    for precA in self._precedences.itervalues():
		if precA == precA.equiv[0]:
		    print >> f, \
		      ('    Precedence_%s [label="{%s}"]') % (precA.name, \
		      "\\n".join(["%s (%s)" % (p.name, p.assoc) \
		      for p in precA.equiv]))
		    for precB in precA.dominators:
			print >> f, '    Precedence_%s -> Precedence_%s' % \
			  (precB.equiv[0].name, precA.equiv[0].name)
	    print >> f, '}'
	    f.close()

	# Iteratively build dominator sets until no more work can be done.
	done = False
	while not done:
	    done = True
	    for precA in self._precedences.itervalues():
		if precA == precA.equiv[0]: # No need to do more than this.
		    for precB in precA.dominators[:]:
			for precC in precB.equiv:
			    if precC not in precA.dominators:
				precA.dominators.append(precC)
				done = False
			for precC in precB.dominators:
			    for precD in precC.equiv:
				if precD not in precA.dominators:
				    precA.dominators.append(precD)
				    done = False

	# Check for cycles in the graph.
	cycles = []
	for precA in self._precedences.itervalues():
	    for precB in [precA] + precA.equiv:
		if precB in precA.dominators:
		    cycles.append( \
		      "Precedence relationship cycle involving '%s'" % \
		      precA.name)
	if len(cycles) > 0:
	    raise SpecError, "\n".join(cycles)

    # Store state to a pickle file, if requested.
    def _pickle(self, file, mode):
	if self._skinny:
	    # Discard data that don't need to be pickled.
	    del self._startSym
	    del self._startProd
	    del self._itemSets
	    del self._itemSetsHash
	    del self._startState

	if file != None and "w" in mode:
	    if self._verbose:
		print "Parsing.Spec: Creating %s Spec pickle in %s..." % \
		  (("fat", "skinny")[self._skinny], file)
	    f = open(file, "w")
	    cPickle.dump(self, f, protocol=cPickle.HIGHEST_PROTOCOL)
	    f.close()

    # Restore state from a pickle file, if a compatible one is provided.  This
    # method uses the same set of return values as does _compatible().
    def _unpickle(self, file, mode):
	if file != None and "r" in mode:
	    if self._verbose:
		print \
		  "Parsing.Spec: Attempting to use pickle from file \"%s\"..." \
		  % file
	    try:
		f = open(file, "r")
	    except IOError:
		if self._verbose:
		    error = sys.exc_info()
		    print "Parsing.Spec: Pickle open failed: Exception %s: %s" \
		      % (error[0], error[1])
		return "incompatible"

	    # Any exception at all in unpickling can be assumed to be due to
	    # an incompatible pickle.
	    try:
		spec = cPickle.load(f)
	    except:
		if self._verbose:
		    error = sys.exc_info()
		    print "Parsing.Spec: Pickle load failed: Exception %s: %s" \
		      % (error[0], error[1])
		return "incompatible"

	    compat = self._compatible(spec)
	    if compat == "incompatible":
		if self._verbose:
		    print "Parsing.Spec: Pickle in \"%s\" is incompatible." % \
		      file
		return compat

	    if self._verbose:
		print \
		  "Parsing.Spec: Using %s pickle in \"%s\" (%s)..." \
		  % (("fat", "skinny")[spec._skinny], file, compat)

	    if compat in ["compatible", "repickle"]:
		# Copy spec's data structures.
		self._precedences = spec._precedences
		self._action = spec._action
		self._goto = spec._goto
		if not self._skinny:
		    self._startState = spec._startState
		self._nActions = spec._nActions
		self._nConflicts = spec._nConflicts
		self._nImpure = spec._nImpure
	    elif compat == "itemsets":
		# Precedences are incompatible, so great care has to be taken
		# when copying from the pickle.  Overwrite all precedence
		# specifications in spec with the new ones, then copy over all
		# of the new symbols/productions (but not the new precedences,
		# of course).  This still leaves table generation, which is
		# done by the _prepare() method later.

		# Nonterminals.
		for key in self._nonterms:
		    nontermSelf = self._nonterms[key]
		    nontermSpec = spec._nonterms[key]
		    nontermSpec.prec = nontermSelf.prec
		    # Productions.
		    for prodSelf in nontermSelf.productions:
			for prodSpec in nontermSpec.productions:
			    if prodSelf.qualified == prodSpec.qualified:
				prodSpec.prec = prodSelf.prec
				break
			assert prodSelf.qualified == prodSpec.qualified
		# Tokens.
		for key in self._tokens:
		    tokenSelf = self._tokens[key]
		    tokenSpec = spec._tokens[key]
		    tokenSpec.prec = tokenSelf.prec
	    else:
		assert False

	    # Copy spec data structures that are usable regardless of whether
	    # the parsing tables need to be rebuilt.
	    self._nonterms = spec._nonterms
	    self._tokens = spec._tokens
	    self._sym2spec = spec._sym2spec
	    self._productions = spec._productions
	    self._userStartSym = spec._userStartSym
	    if not self._skinny:
		self._startSym = spec._startSym
		self._startProd = spec._startProd
		self._itemSets = spec._itemSets
		self._itemSetsHash = spec._itemSetsHash

	    return compat
	else:
	    return "incompatible"

    # Determine whether other is compatible with self.  Note that self is not
    # completely initialized; the idea here is to determine whether other's
    # data structures can be copied *before* doing the work of building parsing
    # tables.
    #
    # Itemsets and precedences are not directly related, other than that
    # symbols have precedences associated with them.  Therefore, we check for
    # the following cases:
    #
    #   "compatible" : Completely compatible.
    #
    #   "repickle" : Compatible, but pickle needs to be regenerated.
    #
    #   "itemsets" : Itemsets are compatible, but precedence specifications are
    #                not.
    #
    #   "incompatible" : No useful compatibility.
    def _compatible(self, other):
	ret = "compatible"

	if (not self._skinny) and other._skinny:
	    return "incompatible"
	elif self._skinny != other._skinny:
	    ret = "repickle"

	# Precedences.
	if len(self._precedences) != len(other._precedences):
	    if self._verbose:
		print "Parsing.Spec: Unequal number of precedences (%d vs %d)" \
		  % (len(self._precedences), len(other._precedences))
	    ret = "itemsets"
	for key in self._precedences:
	    if key not in other._precedences:
		if self._verbose:
		    print "Parsing.Spec: Missing precedence: %s" % key
		ret = "itemsets"
		continue
	    precA = self._precedences[key]
	    precB = other._precedences[key]
	    if precA.name != precB.name \
	      or precA.assoc != precB.assoc \
	      or len(precA.relationships) != len(precB.relationships):
		if self._verbose:
		    print "Parsing.Spec: Incompatible precedences: %r vs. %r" \
		      % (precA, precB)
		ret = "itemsets"
		continue
	    for prec in precA.relationships:
		rel = precA.relationships[prec]
		if prec not in precB.relationships \
		  or precB.relationships[prec] != rel:
		    if self._verbose:
			print \
			  "Parsing.Spec: Incompatible precedences: %r vs. %r" \
			  % (precA, precB)
		    ret = "itemsets"
		    break

	# Nonterminals.
	if len(self._nonterms) != len(other._nonterms):
	    if self._verbose:
		print \
		  "Parsing.Spec: Unequal number of non-terminals (%d vs %d)" \
		  % (len(self._nonterms), len(other._nonterms))
	    return "incompatible"
	for key in self._nonterms:
	    if key not in other._nonterms:
		if self._verbose:
		    print "Parsing.Spec: Missing non-terminal: %s" % key
		return "incompatible"
	    nontermA = self._nonterms[key]
	    nontermB = other._nonterms[key]
	    if nontermA.name != nontermB.name \
	      or nontermA.qualified != nontermB.qualified \
	      or nontermA.nontermType != nontermB.nontermType:
		if self._verbose:
		    print \
		      "Parsing.Spec: Incompatible non-terminals: %r vs. %r" \
		      % (nontermA, nontermB)
		return "incompatible"
	    if nontermA.prec.name != nontermB.prec.name:
		if self._verbose:
		    print \
		      ("Parsing.Spec: Differing precedences for " + \
		      "non-terminal: %r") % nontermA
		ret = "itemsets"

	    # Productions.
	    if len(nontermA.productions) != len(nontermB.productions):
		if self._verbose:
		    print \
		      "Parsing.Spec: Unequal number of productions (%d vs %d)" \
		      % (len(self._productions) - 1, \
		      len(other._productions) - 1)
		return "incompatible"
	    for prodA in nontermA.productions:
		match = False
		for prodB in nontermB.productions:
		    if prodA.qualified == prodB.qualified \
		      and prodA.lhs.name == prodB.lhs.name \
		      and len(prodA.rhs) == len(prodB.rhs):
			match = True
			for i in xrange(len(prodA.rhs)):
			    if prodA.rhs[i].name != prodB.rhs[i].name:
				match = False
				if self._verbose:
				    print \
				      ("Parsing.Spec: Incompatible" + \
				      " productions: %r vs. %r") \
				      % (prodA, prodB)
				break
			if prodA.prec.name != prodB.prec.name:
			    if self._verbose:
				print \
				  ("Parsing.Spec: Differing precedences " + \
				  "for production: %r") % prodA
			    ret = "itemsets"
		if not match:
		    return "incompatible"

	# Tokens.
	if len(self._tokens) != len(other._tokens):
	    if self._verbose:
		print "Parsing.Spec: Unequal number of tokens (%d vs %d)" \
		  % (len(self._tokens), len(other._tokens))
	    return "incompatible"
	for key in self._tokens:
	    if key not in other._tokens:
		if self._verbose:
		    print "Parsing.Spec: Missing token: %s" % key
		return "incompatible"
	    tokenA = self._tokens[key]
	    tokenB = other._tokens[key]
	    if tokenA.name != tokenB.name \
	      or tokenA.tokenType != tokenB.tokenType:
		if self._verbose:
		    print \
		      "Parsing.Spec: Incompatible tokens: %r vs. %r" \
		      % (tokenA, tokenB)
		return "incompatible"
	    if tokenA.prec.name != tokenB.prec.name:
		if self._verbose:
		    print \
		      "Parsing.Spec: Differing precedences for token: %r" \
		      % tokenA
		ret = "itemsets"

	# User start symbol.
	if self._userStartSym.name != other._userStartSym.name:
	    if self._verbose:
		print "Parsing.Spec: Differing start symbols: %s vs. %s" \
		  % (self._userStartSym.name, other._userStartSym.name)
	    return "incompatible"

	if other._skinny and ret == "itemsets":
	    # The itemsets have to be regenerated, since they weren't pickled.
	    ret = "incompatible"
	return ret

    # Check for unused prececence/token/nonterm/reduce specifications, then
    # throw a SpecError if any ambiguities exist in the grammar.
    def _validate(self, logFile):
	if self._verbose:
	    print "Parsing.Spec: Validating grammar..."

	lines = []
	if self._nConflicts > 0:
	    lines.append("Parsing.Spec: %d unresolvable conflict%s" % \
	      (self._nConflicts, ("s", "")[self._nConflicts == 1]))

	# Previous code guarantees that all precedence/token/nonterm names are
	# unique.  Therefore, we can build a single dictionary here that keys on
	# names.
	used = {}
	productions = []
	for itemSet in self._itemSets:
	    for item in itemSet:
		productions.append(item.production)
		used[item.production.prec.name] = item.production.prec
		for sym in [item.production.lhs] + item.production.rhs:
		    used[sym.name] = sym
		    used[sym.prec.name] = sym.prec

		for token in item.lookahead.iterkeys():
		    used[token.prec.name] = token.prec

	nUnused = 0

	# Precedences.
	for prec in self._precedences:
	    if prec not in [self._none.name, self._split.name]:
		if prec not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused precedence: %r" % \
		      self._precedences[prec])

	# Tokens.
	for token in self._tokens:
	    if token not in [eoi.name, epsilon.name]:
		if token not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused token: %s" % \
		      self._tokens[token])

	# Nonterms.
	for nonterm in self._nonterms:
	    if nonterm not in [self._startSym.name]:
		if nonterm not in used:
		    nUnused += 1
		    lines.append("Parsing.Spec: Unused nonterm: %s" % \
		      self._nonterms[nonterm])

	# Productions.
	for production in self._productions:
	    if production not in productions:
		nUnused += 1
		lines.append("Parsing.Spec: Unused production: %r" % production)

	if nUnused > 0:
	    lines.insert((1, 0)[self._nConflicts == 0], \
	      "Parsing.Spec: %d unused definition%s" % \
	      (nUnused, ("s", "")[nUnused == 1]))

	# Write to logFile, if one was specified.
	if logFile != None:
	    f = open(logFile, "w+")
	    if self._verbose:
		print "Parsing.Spec: Writing log to '%s'..." % logFile
	    f.write("%s" % "\n".join(lines + ["%r" % self]))
	    f.close()

	# Conflicts are fatal.
	if self._nConflicts > 0:
	    raise SpecError, ("%s" % ("\n".join(lines)))

	# Make sure to let the user know about unused symbols if verbosity is
	# enabled, and there weren't any conflicts to cause notification via an
	# exception.
	if self._verbose:
	    ntokens = len(self._tokens) - 1
	    nnonterms = len(self._nonterms) - 1
	    nproductions = len(self._productions) - 1
	    lines.append(
	      "Parsing.Spec: %d token%s, %d non-terminal%s, %d production%s" \
	      % (ntokens, ("s", "")[ntokens == 1], \
	      nnonterms, ("s", "")[nnonterms == 1], \
	      nproductions, ("s", "")[nproductions == 1]))
	    sys.stdout.write("%s\n" % "\n".join(lines))

    # Compute the first sets for all symbols.
    def _firstSets(self):
	# Terminals.
	# first(X) is X for terminals.
	for sym in self._tokens.itervalues():
	    sym.firstSetMerge(sym)

	# Non-terminals.
	#
	# Repeat the following loop until no more symbols can be added to any
	# first set.
	done = False
	while not done:
	    done = True
	    for name in self._nonterms:
		sym = self._nonterms[name]
		for prod in sym.productions:
		    # Merge epsilon if there is an empty production.
		    if len(prod.rhs) == 0:
			if not sym.firstSetMerge(epsilon):
			    done = False

		    # Iterate through the RHS and merge the first sets into
		    # this symbol's, until a preceding symbol's first set does
		    # not contain epsilon.
		    for elm in prod.rhs:
			containsEpsilon = False
			for elmSym in elm.firstSet:
			    if not sym.firstSetMerge(elmSym):
				done = False
			    if elmSym == epsilon:
				containsEpsilon = True
			if not containsEpsilon:
			    break

    # Compute the follow sets for all symbols.
    def _followSets(self):
	self._startSym.followSet = [epsilon]

	# Repeat the following loop until no more symbols can be added to any
	# follow set.
	done = False
	while not done:
	    done = True
	    for name in self._nonterms:
		sym = self._nonterms[name]
		for prod in sym.productions:
		    # For all A ::= aBb, merge first(b) into follow(B).
		    for i in xrange(len(prod.rhs) - 1):
			for j in xrange(i+1, len(prod.rhs)):
			    if not prod.rhs[i].followSetMerge( \
			      prod.rhs[j].firstSet):
				done = False
			    if epsilon not in prod.rhs[j].firstSet:
				break

		    # For A ::= ab, or A ::= aBb where first(b) contains <e>,
		    # merge follow(A) into follow(B).
		    for i in xrange(len(prod.rhs)-1, -1, -1):
			if not prod.rhs[i].followSetMerge(prod.lhs.followSet):
			    done = False
			if epsilon not in prod.rhs[i].firstSet:
			    break

    # Compute the collection of sets of LR(1) items.
    def _items(self):
	# Add {[S' ::= * S $., <e>]} to _itemSets.
	tItemSet = ItemSet()
	tItem = Item(self._startProd, 0, [epsilon])
	tItemSet.append(tItem)
	tItemSet.closure()
	self._itemSets.append(tItemSet)

	# List of state numbers that need to be processed.
	worklist = [0]
	if self._verbose:
	    nwork = len(worklist)
	    print "Parsing.Spec: Generating LR(1) itemset collection... ",
	    sys.stdout.write("+")
	    sys.stdout.flush()

	# itemSetsHash uses itemsets as keys.  A value is a list of _itemSets
	# indices; these itemsets are the ones referred to the key itemset.
	itemSetsHash = {tItemSet: [0]}

	syms = self._tokens.values() + self._nonterms.values()
	while len(worklist) > 0:
	    if self._verbose:
		if abs(len(worklist) - nwork) >= 10:
		    nwork = len(worklist)
		    sys.stdout.write("[%d/%d]" % \
		      (len(worklist), len(self._itemSets)))
		    sys.stdout.flush()

	    i = worklist.pop(0)
	    itemSet = self._itemSets[i]
	    for sym in syms:
		gotoSet = itemSet.goto(sym)
		if len(gotoSet) > 0:
		    merged = False
		    if gotoSet in itemSetsHash:
			for j in itemSetsHash[gotoSet]:
			    mergeSet = self._itemSets[j]
			    if mergeSet.weakCompat(gotoSet):
				merged = True
				if mergeSet.merge(gotoSet):
				    # Process worklist in MRU order.  This
				    # causes a depth-first traversal.
				    if j in worklist:
					worklist.remove(j)
				    else:
					if self._verbose:
					    sys.stdout.write(".")
					    sys.stdout.flush()
				    worklist.insert(0, j)
				break
		    if not merged:
			gotoSet.closure()
			worklist.append(len(self._itemSets))
			if gotoSet not in itemSetsHash:
			    itemSetsHash[gotoSet] = [len(self._itemSets)]
			else:
			    itemSetsHash[gotoSet].append(len(self._itemSets))
			self._itemSets.append(gotoSet)
			if self._verbose:
			    sys.stdout.write("+")
			    sys.stdout.flush()

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()
	self._itemSetsHash = itemSetsHash

    # Compute LR parsing tables.
    def _lr(self):
	# The collection of sets of LR(1) items already exists.
	assert len(self._itemSets) > 0
	assert len(self._action) == 0
	assert len(self._goto) == 0
	assert self._startState == None
	assert self._nConflicts == 0

	if self._verbose:
	    print \
	      "Parsing.Spec: Generating LR(1) parsing tables (%d state%s)... " \
	      % (len(self._itemSets), \
	      ("s", "")[len(self._itemSets) == 1]),
	    sys.stdout.flush()

	itemSetsHash = self._itemSetsHash

	for itemSet in self._itemSets:
	    if self._verbose:
		sys.stdout.write(".")
		sys.stdout.flush()
	    #===================================================================
	    # _action.
	    state = {}
	    self._action.append(state)
	    for item in itemSet:
		# X ::= a*Ab
		if item.dotPos < len(item.production.rhs):
		    sym = item.production.rhs[item.dotPos]
		    if isinstance(sym, TokenSpec):
			itemSetB = itemSet.goto(sym)
			for i in itemSetsHash[itemSetB]:
			    itemSetC = self._itemSets[i]
			    if itemSetC.weakCompat(itemSetB):
				self._actionAppend(state, sym, ShiftAction(i))

		    # Check if this is the start state.
		    if self._startState == None \
		      and item.production.lhs == self._startSym \
		      and item.dotPos == 0:
			assert len(item.production.rhs) == 2
			self._startState = len(self._action) - 1
		# X ::= a*
		elif item.dotPos == len(item.production.rhs):
		    for lookahead in item.lookahead.iterkeys():
			self._actionAppend(state, lookahead, \
			  ReduceAction(item.production))
		else:
		    assert False
	    #===================================================================
	    # _goto.
	    state = {}
	    self._goto.append(state)
	    for nonterm in self._nonterms.itervalues():
		itemSetB = itemSet.goto(nonterm)
		if itemSetB in itemSetsHash:
		    for i in itemSetsHash[itemSetB]:
			itemSetC = self._itemSets[i]
			if itemSetC.weakCompat(itemSetB):
			    assert nonterm not in state
			    state[nonterm] = i

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()

    # Add a symbol action to state, if the action doesn't already exist.
    def _actionAppend(self, state, sym, action):
	assert type(state) == dict
	assert isinstance(sym, SymbolSpec)
	assert isinstance(action, Action)

	if sym not in state:
	    state[sym] = [action]
	else:
	    actions = state[sym]
	    if action not in actions:
		state[sym].append(action)

    # Look for action ambiguities and resolve them if possible.
    def _disambiguate(self):
	assert self._nActions == 0
	assert self._nConflicts == 0
	assert self._nImpure == 0

	if self._verbose:
	    print "Parsing.Spec: Disambiguating LR(1) parsing tables... ",
	    sys.stdout.flush()

	for stateInd in xrange(len(self._action)):
	    state = self._action[stateInd]
	    if self._verbose:
		vRes = "."
		vNConflicts = 0
	    for sym in state:
		nConflicts = 0
		acts = [act for act in state[sym]]
		# Construct a list that corresponds to acts; each element
		# indicates whether to preserve the action.
		actStats = [True] * len(acts)

		# Fill in the cells of actStats.
		for i in xrange(len(acts)):
		    actI = acts[i]
		    for j in xrange(i+1, len(acts)):
			actJ = acts[j]
			res = self._resolve(sym, actI, actJ)
			if res == "neither":
			    actStats[i] = False
			    actStats[j] = False
			elif res == "old":
			    actStats[j] = False
			elif res == "both":
			    pass
			elif res == "new":
			    actStats[i] = False
			elif res == "err":
			    actStats[i] = False
			    actStats[j] = False
			    nConflicts += 1
			else:
			    assert False

		# Look for actions that can coexist or dominate all other
		# actions.
		newActs = []
		for j in xrange(len(acts)):
		    if actStats[j]:
			newActs.append(acts[j])
		# Replace the action set if there exists a valid resolution
		# among the actions.
		if len(newActs) > 0 or nConflicts == 0:
		    if self._verbose:
			if len(newActs) != len(acts):
			    vRes = "_"
		    state[sym] = newActs
		    nConflicts = 0
		elif self._verbose:
		    vNConflicts += nConflicts

		nActions = len(state[sym])
		if nActions > 1:
		    nImpure = nActions
		else:
		    nImpure = 0

		# Update summary stats.
		self._nActions += nActions
		self._nConflicts += nConflicts
		self._nImpure += nImpure

	    if self._verbose:
		if vNConflicts == 0:
		    sys.stdout.write("%s" % vRes)
		else:
		    sys.stdout.write("[%d:%d]" % (stateInd, vNConflicts))
		sys.stdout.flush()

	if self._verbose:
	    sys.stdout.write("\n")
	    sys.stdout.flush()

    # Compute how to resolve an action conflict.
    #
    # ret: "neither" : Discard both.
    #      "old"     : Keep old.
    #      "both"    : Keep both.
    #      "new"     : Keep new.
    #      "err"     : Unresolvable conflict.
    def _resolve(self, sym, oldAct, newAct):
	if type(oldAct) == ShiftAction:
	    oldPrec = sym.prec
	elif type(oldAct) == ReduceAction:
	    oldPrec = oldAct.production.prec
	else:
	    assert False

	if type(newAct) == ShiftAction:
	    newPrec = sym.prec
	elif type(newAct) == ReduceAction:
	    newPrec = newAct.production.prec
	else:
	    assert False

	if oldPrec in newPrec.dominators:
	    # Discard new action.
	    ret = "old"
	elif newPrec in oldPrec.dominators:
	    # Discard old action.
	    ret = "new"
	elif oldPrec in newPrec.equiv:
	    assert newPrec in oldPrec.equiv

	    if oldPrec.assoc == "split" or newPrec.assoc == "split":
		ret = "both"
	    elif type(newAct) == type(oldAct):
		assert type(newAct) == ReduceAction
		assert type(oldAct) == ReduceAction
		# Fatal reduce/reduce conflict.
		ret = "err"
	    else:
		if oldPrec.assoc != "fail" and newPrec.assoc != "fail" \
		  and oldPrec.assoc != newPrec.assoc:
		    # Conflicting associativity.
		    ret = "err"
		else:
		    # Determine associativity.  If only one of the actions has
		    # %fail associativity, it is overridden by the other.
		    if oldPrec.assoc == "fail":
			assoc = newPrec.assoc
		    else:
			assoc = oldPrec.assoc
		    assert assoc in ["fail", "nonassoc", "left", "right"]

		    if assoc == "fail":
			ret = "err"
		    elif assoc == "left":
			if type(oldAct) == ShiftAction:
			    ret = "new"
			else:
			    assert type(newAct) == ShiftAction
			    ret = "old"
		    elif assoc == "right":
			if type(oldAct) == ShiftAction:
			    ret = "old"
			else:
			    assert type(newAct) == ShiftAction
			    ret = "new"
		    elif assoc == "nonassoc":
			ret = "neither"
		    else:
			assert False
	else:
	    if newPrec in oldPrec.equiv:
		print "%r <--> %r" % (oldPrec, newPrec)
	    assert newPrec not in oldPrec.equiv
	    # No specified relationship between precedences.
	    ret = "err"

	return ret

class Lr(object):
    """
LR(1) parser.  The Lr class uses a Spec instance in order to parse
input that is fed to it via the token() method, and terminated via the
eoi() method.
"""
    def __init__(self, spec):
	if __debug__:
	    if type(self) == Lr:
		assert spec.pureLR
	assert spec._nConflicts == 0
	self._spec = spec
	self.reset()
	self._verbose = False

    def __getSpec(self): return self._spec
    def __setSpec(self, spec): return AttributeError
    spec = property(__getSpec, __setSpec)

    def __getStart(self): return self._start
    def __setStart(self, start): raise AttributeError
    start = property(__getStart, __setStart, """
A list of parsing results.  For LR parsing, there is only ever one
result, but for compatibility with the Glr interface, start is a
list.
""")

    def __getVerbose(self): return self._verbose
    def __setVerbose(self, verbose):
	assert type(verbose) == bool
	self._verbose = verbose
    verbose = property(__getVerbose, __setVerbose)

    def reset(self):
	self._start = None
	self._stack = [(Epsilon(self), 0)]

    def token(self, token):
	"""
Feed a token to the parser.
"""
	tokenSpec = self._spec._sym2spec[type(token)]
	self._act(token, tokenSpec)

    def eoi(self):
	"""
Signal end-of-input to the parser.
"""
	token = EndOfInput(self)
	self.token(token)

	assert self._stack[-1][0] == token # <$>.
	if self._verbose:
	    self._printStack()
	    print "   --> accept"
	self._stack.pop()

	top = self._stack[-1]
	self._start = [self._stack[1][0]]
	assert self._start[0].symSpec == self._spec._userStartSym

    def _act(self, sym, symSpec):
	if self._verbose:
	    self._printStack()
	    print "INPUT: %r" % sym

	while True:
	    top = self._stack[-1]
	    if symSpec not in self._spec._action[top[1]]:
		raise SyntaxError, ("Unexpected token: %r" % sym)

	    actions = self._spec._action[top[1]][symSpec]
	    assert len(actions) == 1
	    action = actions[0]

	    if self._verbose:
		print "   --> %r" % action
	    if type(action) == ShiftAction:
		self._stack.append((sym, action.nextState))
		break
	    else:
		assert type(action) == ReduceAction
		self._reduce(action.production)

	    if self._verbose:
		self._printStack()

    def _printStack(self):
	    print "STACK:",
	    for node in self._stack:
		print "%r" % node[0],
	    print
	    print "      ",
	    for node in self._stack:
		print "%r%s" % (node[1], \
		  (" " * (len("%r" % node[0]) - len("%r" % node[1])))),
	    print

    def _reduce(self, production):
	nRhs = len(production.rhs)
	rhs = []
	for i in xrange(len(self._stack) - nRhs, len(self._stack)):
	    rhs.append(self._stack[i][0])

	r = self._production(production, rhs)

	for i in xrange(nRhs):
	    self._stack.pop()

	top = self._stack[-1]
	self._stack.append((r, self._spec._goto[top[1]][production.lhs]))

    def _production(self, production, rhs):
	sym = production.lhs.nontermType(self)
	nRhs = len(rhs)
	assert nRhs == len(production.rhs)
	r = production.method(sym, *rhs)

	# Python's method definition syntax makes returning self from %reduce
	# methods cumbersome, so translate None here.
	if r == None:
	    r = sym

	return r

#===============================================================================
# Begin graph-structured stack (GSS) classes.
#

class Gss(list):
    """Graph-structured stack."""
    def __init__(self, glr):
	list.__init__(self)

	self._glr = glr

class Gsse(object):
    """Graph-structured stack edge."""
    def __init__(self, below, above, value):
	self.node = below
	above._edges.append(self)
	self.value = value

    def __repr__(self):
	return "{%r}" % self.value

    def __eq__(self, other):
	if self.node != other.node \
	  or self.value != other.value:
	    return False
	return True

class Gssn(object):
    """Graph-structured stack node."""
    def __init__(self, below, value, nextState):
	assert isinstance(below, Gssn) or below == None

	self._edges = []
	if below != None:
	    Gsse(below, self, value)
	self.nextState = nextState

    def __repr__(self):
	return "[%d]" % self.nextState

    def __getEdge(self):
	assert len(self._edges) == 1
	return self._edges[0]
    def __setEdge(self): raise AttributeError
    edge = property(__getEdge, __setEdge)

    def edges(self):
	for edge in self._edges:
	    yield edge

    def nodes(self):
	for edge in self._edges:
	    yield edge.node

    # Iterate over all paths of length pathLen.  Path length is measured as the
    # number of edges in the path, so a path of length 0 still consists of a
    # single node.
    #
    # Each path is encoded as a list that alternates between nodes and edges,
    # where the first and last elements are always nodes.
    #
    # <e>-grammars can cause cycles, which requires that we avoid infinite
    # recursion.
    def paths(self, pathLen=None):
	assert ((type(pathLen) == int and pathLen >= 0) or pathLen == None)

	for path in self._pathsRecurse(pathLen, []):
	    yield path

    def _pathsRecurse(self, pathLen, path):
	path.insert(0, self)
	if pathLen == None and len(self._edges) == 0:
	    yield path[:]
	elif pathLen != None and len(path) - 1 == pathLen * 2:
	    yield path[:]
	else:
	    for edge in self.edges():
		# Avoid infinite recursion due to <e>-production cycles.
		if len(path) < 3 or edge != path[1]:
		    path.insert(0, edge)
		    for x in edge.node._pathsRecurse(pathLen, path):
			yield x
		    path.pop(0)
	path.pop(0)

#
# End graph-structured stack (GSS) classes.
#===============================================================================

class Glr(Lr):
    """
GLR parser.  The Glr class uses a Spec instance in order to parse input
that is fed to it via the token() method, and terminated via the eoi()
method.
"""
    def __init__(self, spec):
	Lr.__init__(self, spec)

    def reset(self):
	self._start = None

	# Initialize with a stack that is in the start state.
	self._gss = Gss(self)
	top = Gssn(None, None, 0)
	self._gss.append(top)

	self._paths = []

    def token(self, token):
	"""
Feed a token to the parser.
"""
	if self._verbose:
	    print "%s" % ("-" * 80)
	    print "INPUT: %r" % token
	tokenSpec = self._spec._sym2spec[type(token)]
	self._act(token, tokenSpec)
	if len(self._gss) == 0:
	    raise SyntaxError, ("Unexpected token: %r" % token)

    def eoi(self):
	"""
Signal end-of-input to the parser.
"""
	token = EndOfInput(self)
	self.token(token)

	# Gather the start symbols from the stacks.
	self._start = []
	for top in self._gss:
	    for path in top.paths():
		assert len(path) == 5
		if self._verbose:
		    print "   --> accept %r" % path
		edge = path[1]
		assert isinstance(edge.value, Nonterm)
		assert edge.value.symSpec == self._spec._userStartSym
		self._start.append(edge.value)

	if len(self._start) == 0:
	    raise SyntaxError, "Unexpected end of input"

	if self._verbose:
	    print "Start: %r" % self._start
	    print "%s" % ("-" * 80)

    def _act(self, sym, symSpec):
	self._reductions(sym, symSpec)
	self._shifts(sym, symSpec)

    def _reductions(self, sym, symSpec):
	# epsilons is a dictionary that maps production-->[tops].  The purpose
	# is to avoid repeating the same epsilon production on a particular
	# stack top.  Ordinary productions do not require this care because we
	# can notice when a path has already been used for a production.
	epsilons = {}

	if self._verbose:
	    nReduces = 0

	# Enqueue work.
	workQ = []
	i = 0
	while i < len(self._gss):
	    top = self._gss[i]
	    if symSpec not in self._spec._action[top.nextState]:
		# Unexpected token for this stack.
		self._gss.pop(i)
	    else:
		for action in self._spec._action[top.nextState][symSpec]:
		    if type(action) == ReduceAction:
			if len(action.production.rhs) == 0:
			    if action.production not in epsilons:
				assert len([path for path in top.paths(0)]) == 1
				path = [p for p in top.paths(0)][0]
				epsilons[action.production] = [top]
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(a) %r" % \
				      action.production
				    print "                  %r" % path
			    elif top not in epsilons[action.production]:
				assert len([path for path in top.paths(0)]) == 1
				path = [p for p in top.paths(0)][0]
				epsilons[action.production].append(top)
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(b) %r" % \
				      action.production
				    print "                  %r" % path
			else:
			    # Iterate over all reduction paths through stack and
			    # enqueue them.
			    for path in top.paths(len(action.production.rhs)):
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(c) %r" % \
				      action.production
				    print "                  %r" % path
		i += 1

	# Process the work queue.
	while len(workQ) > 0:
	    (path, production) = workQ.pop(0)

	    if self._verbose:
		print "   --> reduce %r" % production
		print "              %r" % path
		nReduces += 1

	    self._reduce(workQ, epsilons, path, production, symSpec)

	if self._verbose:
	    if nReduces > 0:
		self._printStack()

    def _reduce(self, workQ, epsilons, path, production, symSpec):
	assert len(path[1::2]) == len(production.rhs)

	# Build the list of RHS semantic values to pass to the reduction action.
	rhs = [edge.value for edge in path[1::2]]

	# Call the user reduction method.
	r = self._production(production, rhs)

	below = path[0]
	done = False
	for top in self._gss:
	    if top.nextState == \
	      self._spec._goto[below.nextState][production.lhs]:
		# top is compatible with the reduction result we want to add to
		# the set of stack tops.
		for edge in top.edges():
		    if edge.node == below:
			# There is already a below<--top link, so merge
			# competing interpretations.
			if self._verbose:
			    print "   --> merge %r <--> %r" % (edge.value, r)
			value = production.lhs.nontermType.merge(edge.value, r)
			if self._verbose:
			    if value == edge.value:
				print "             %s" % \
				  ("-" * len("%r" % edge.value))
			    else:
				print "             %s      %s" % \
				  ((" " * len("%r" % edge.value)), \
				  "-" * len("%r" % r))
			edge.value = value
			done = True
			break
		if not done:
		    # Create a new below<--top link.
		    edge = Gsse(below, top, r)
		    if self._verbose:
			print "   --> shift(b) %r" % top

		    # Enqueue reduction paths that were created as a result of
		    # the new link.
		    self._enqueueLimitedReductions(workQ, epsilons, edge, \
		      symSpec)
		    done = True
		break
	if not done:
	    # There is no compatible stack top, so create a new one.
	    top = Gssn(below, r, \
	      self._spec._goto[below.nextState][production.lhs])
	    self._gss.append(top)
	    if self._verbose:
		print "   --> shift(c) %r" % \
		  self._spec._goto[below.nextState][production.lhs]
	    self._enqueueLimitedReductions(workQ, epsilons, top.edge, symSpec)

    # Enqueue paths that incorporate edge.
    def _enqueueLimitedReductions(self, workQ, epsilons, edge, symSpec):
	for top in self._gss:
	    if symSpec in self._spec._action[top.nextState]:
		for action in self._spec._action[top.nextState][symSpec]:
		    if type(action) == ReduceAction:
			if len(action.production.rhs) == 0:
			    if self._spec._goto[top.nextState] \
			      [action.production.lhs] == top.nextState:
				# Do nothing, since enqueueing a reduction
				# would result in performing the same reduction
				# twice.
				pass
			    elif action.production not in epsilons:
				path = [top]
				epsilons[action.production] = [top]
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(d) %r" % \
				      action.production
				    print "                  %r" % path
			    elif top not in epsilons[action.production]:
				path = [top]
				epsilons[action.production].append(top)
				workQ.append((path, action.production))
				if self._verbose:
				    print "   --> enqueue(e) %r" % \
				      action.production
				    print "                  %r" % path
			else:
			    # Iterate over all reduction paths through stack and
			    # enqueue them if they incorporate edge.
			    for path in top.paths(len(action.production.rhs)):
				if edge in path[1::2]:
				    workQ.append((path, action.production))
				    if self._verbose:
					print "   --> enqueue(f) %r" % \
					  action.production
					print "                  %r" % path

    def _shifts(self, sym, symSpec):
	prevGss = self._gss
	self._gss = Gss(self)

	if self._verbose:
	    nShifts = 0

	for topA in prevGss:
	    if symSpec in self._spec._action[topA.nextState]:
		for action in self._spec._action[topA.nextState][symSpec]:
		    if type(action) == ShiftAction:
			merged = False
			for topB in self._gss:
			    if topB.nextState == topA.nextState:
				Gsse(topA, topB, sym)
				merged = True
				break
			if not merged:
			    top = Gssn(topA, sym, action.nextState)
			    self._gss.append(top)
			    if self._verbose:
				print "   --> shift(a) %d" % action.nextState
				nShifts += 1
	if self._verbose:
	    if nShifts > 0:
		self._printStack()

    def _printStack(self):
	i = 0
	for top in self._gss:
	    for path in top.paths():
		if i == 0:
		    print "STK 0:",
		else:
		    print "    %d:" % i,
		for elm in path:
		    print "%r" % elm,
		print
		i += 1
#=============================================================================== # Copyright (c) 2007 <NAME> <<EMAIL>> # # 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. #=============================================================================== # # Release history: # # 1.3 (8 August 2007): Retroactively number public releases. # #                      Back-port to Python 2.4. # #                      Remove some magic surrounding epsilon, in order to #                      generalize/simplify. # # 1.2 (6 May 2007): Fix some off-by-one errors in production count reporting. # #                   Add some missing code that helps detect which definitions #                   are used/unused when building the parser. # # 1.1 (22 March 2007): Optimize/generalize Lr._production() by using argument #                      list expansion. # # 1.0 (19 March 2007): Initial public release. # #=============================================================================== The Parsing module implements an LR(1) parser generator, as well as the runtime support for using a generated parser, via the Lr and Glr parser drivers.  There is no special parser generator input file format, but the parser generator still needs to know what classes/methods correspond to various aspects of the parser.  This information is specified via docstrings, which the parser generator introspects in order to generate a parser.  Only one parser specification can be embedded in each module, but it is possible to share modules between parser specifications so that, for example, the same token definitions can be used by multiple parser specifications.  The parsing tables are LR(1), but they are generated using a fast algorithm that avoids creating duplicate states that result when using the generic LR(1) algorithm.  Creation time and table size are on par with the LALR(1) algorithm.  However, LALR(1) can create reduce/reduce conflicts that don't exist in a true LR(1) parser.  For more information on the algorithm, see:      A Practical General Method for Constructing LR(k) Parsers     <NAME>     Acta Informatica 7, 249-268 (1977)  Parsing table generation requires non-trivial amounts of time for large grammars.  Internal pickling support makes it possible to cache the most recent version of the parsing table on disk, and use the table if the current parser specification is still compatible with the one that was used to generate the pickled parsing table.  Since the compatibility checking is quite fast, even for large grammars, this removes the need to use the standard code generation method that is used by most parser generators.  Parser specifications are encapsulated by the Spec class.  Parser instances use Spec instances, but are themselves based on separate classes.  This allows multiple parser instances to exist simultaneously, without requiring multiple copies of the parsing tables.  There are two separate parser driver classes:    Lr : Standard Characteristic Finite State Machine (CFSM) driver, based on        unambiguous LR(1) parsing tables.  This driver is faster than the Glr        driver, but it cannot deal with all parsing tables that the Glr        driver can.    Glr : Generalized LR driver, capable of tracking multiple parse trees         simultaneously, if the %split precedence is used to mark ambiguous         actions.  This driver is closely based on Elkhound's design, which         is described in a technical report:              Elkhound: A Fast, Practical GLR Parser Generator             <NAME>             Report No. UCB/CSD-2-1214 (December 2002)             http://www.cs.berkeley.edu/~smcpeak/elkhound/  Parser generator directives are embedded in docstrings, and must begin with a '%' character, followed immediately by one of several keywords:      Precedence : %fail %nonassoc %left %right %split          Token : %token   Non-terminal : %start %nonterm     Production : %reduce  All of these directives are associated with classes except for %reduce. %reduce is associated with methods within non-terminal classes.  The Parsing module provides base classes from which precedences, tokens, and non-terminals must be derived.  This is not as restrictive as it sounds, since there is nothing preventing, for example, a master Token class that subclasses Parsing.Token, which all of the actual token types then subclass. Also, nothing prevents using multiple inheritance.  Folowing are the base classes to be subclassed by parser specifications:    * Precedence   * Token   * Nonterm  The Parsing module implements the following exception classes:    * Exception   * SpecError   * SyntaxError   * AttributeError #=============================================================================== # Begin exceptions. # Top level Parsing exception class, from which all other Parsing exception classes inherit. Attribute error, no different from the builtin exception, except that it also derives from Parsing.Exception. Specification error exception.  SpecError arises when the Spec introspection machinery detects an error either during docstring parsing or parser specification generation. Parser syntax error.  SyntaxError arises when a Parser instance detects a syntax error according to the Spec it is using, for the input being fed to it. # # End exceptions. #=============================================================================== Precedences can be associated with tokens, non-terminals, and productions.  Precedence isn't as important for GLR parsers as for LR parsers, since GLR parsing allows for parse-time resolution of ambiguity.  Still, precedence can be useful for reducing the volume of ambiguities that must be dealt with at run-time.  There are five precedence types: %fail, %nonassoc, %left, %right, and %split.  Each precedence can have relationships with other precedences: <, >, or =.  These relationships specify a directed acyclic graph (DAG), which is used to compute the transitive closures of relationships among precedences.  If no path exists between two precedences that are compared during conflict resolution, parser generation fails.  < and > are reflexive; it does not matter which is used.  Conceptually, the = relationship causes precedences to share a node in the DAG.  During conflict resolution, an error results if no path exists in the DAG between the precedences under consideration.  When such a path exists, the highest precedence non-terminal or production takes precedence.  Associativity only comes into play for shift/reduce conflicts, where the terminal and the production have equivalent precedences (= relationship).  In this case, the non-terminal's associativity determines how the conflict is resolved.  The %fail and %split associativities are special because they can be mixed with other associativities.  During conflict resolution, if another action has non-%fail associativity, then the %fail (lack of) associativity is overridden.  Similarly, %split associativity overrides any other associativity.  In contrast, any mixture of associativity between %nonassoc/%left/%right causes an unresolvable conflict.         %fail : Any conflict is a parser-generation-time error.                 A pre-defined precedence, [none], is provided.  It has                %fail associativity, and has no pre-defined precedence                relationships.     %nonassoc : Resolve shift/reduce conflicts by removing both                possibilities, thus making conflicts a parse-time error.         %left : Resolve shift/reduce conflicts by reducing.        %right : Resolve shift/reduce conflicts by shifting.        %split : Do not resolve conflicts; the GLR algorithm will split                the parse stack when necessary.                 A pre-defined precedence, [split], is provided.  It has                %split associativity, and has no pre-defined precedence                relationships.  By default, all symbols have [none] precedence.  Each production inherits the precedence of its left-hand-side nonterminal's precedence unless a precedence is manually specified for the production.  Following are some examples of how to specify precedence classes:    class P1(Parsing.Precedence):       "%split p1"    class p2(Parsing.Precedence):       "%left" # Name implicitly same as class name.    class P3(Parsing.Precedence):       "%left p3 >p2" # No whitespace is allowed between > and p2.    class P4(Parsing.Precedence):       "%left p4 =p3" # No whitespace is allowed between = and p3. # Raw relationships specification. # Set.  Precedences that have equivalent precedence. # Set.  Precedences that have higher precedence. # Important for pickling/unpickling. # Set. # Set. # Used for ordering symbols and hashing. # Prefixes are identical.  Handle trailing characters, if any. # Calculate the first set for the string encoded by the s vector. # Set. # Merge epsilon if it was in the first set of every symbol. # Cache the result. # Add forward decl for Lyken. # Set. Non-terminal symbols have sets of productions associated with them.  The productions induce a parse forest on an input token stream.  There is one special non-terminal, which is denoted via the %start directive, whereas all other non-terminals are denoted via the %nonterm directive. In addition to productions (%reduce directives associated with class methods), the merge() method may be called during resolution of ambiguous parses.  See the merge() documentation for further details.  Following are examples of how to specify non-terminal classes and their associated productions:    class E(Parsing.Nonterm):       "%start E"       def __init__(self):           Parsing.Nonterm.__init__(self)           # ...        # Productions.       def reduceA(self, E, plus, T):           "%reduce E plus T [split]"           print "%r ::= %r %r %r." % (self, E, plus, T)        def reduceB(self, T):           "%reduce T"    class T(Parsing.Nonterm):         "%nonterm" # Name implicitly same as class name.       def reduceA(self, T, star, F):           "%reduce T star F"        def reduceB(self, F):           "%reduce F [p1]"    class F(Parsing.Nonterm):       "%nonterm F [p2]"       def reduceA(self, lparen, E, rparen):           "%reduce lparen E rparen"        def reduceB(self, id):           "%reduce id" Merging happens when there is an ambiguity in the input that allows non-terminals to be part of multiple overlapping series of reductions.  If no merge() method is specified, the parser will throw a syntax error upon encountering an ambiguity that confounds reduction processing.  However, it may be useful to either discard one of the possible parses, or to explicitly record the ambiguity in the data structures being created during parsing.  In both of these cases, the non-terminal-specific merge() is the place to do the work; merge() returns an object that is stored by the parser onto the parse stack.  In the case where merge() discards one of the possible parses, it need only return the parse that is to be preserved (self or other).  If multiple merges are necessary, they cause a series of merge() calls.  The first alternative (self) may be the result of a previous merge() call, whereas other will not have not been merged yet (unless as the result of merging further down in the parse forest).  The alternative that is discarded is never touched by the parser again, so if any immediate cleanup is necessary, it should be done in merge(). Tokens are terminal symbols.  The parser is fed Token instances, which is what drives parsing.  Typically, the user will define a class that subclasses Parsing.Token and implement parser-specific machinery there, then derive all actual token types from that class.    class Token(Parsing.Token):       def __init__(self, parser): 	  Parsing.Token.__init__(self, parser) 	  # ...    class Plus(Token):       "%token plus [p1]"    class star(Token):       "%token star [p2]" # Name implicitly same as class name.    class lparen(Token):       "%token [split]"    class rparen(Token):       "%token [none]" # [none] not necessary, since it's the default.    class id(Token):       "%token" # AKA terminal symbol. # <$>. # <e>. # Used for hashing. # Convert qualified name to a function reference. # Set state. # Optional callback method. # # Called when a production is reduced. # This works because integers never overflow, and addition is # transitive. # Merge a kernel item. # Merge an added item. # Given a list of items, compute their closure and merge the results into # the set of added items. # Iterate over the items until no more can be added to the closure. # Calculate and merge the kernel's transitive closure. # Calculate the kernel of the goto set, given a particular symbol. # Merge the kernel of other into this ItemSet, then update the closure. # It is not sufficient to copy other's added items, since other has not # computed its closure. # Determine if self and other are weakly compatible, as defined by the # Pager(1977) algorithm. # Check for identical kernel LR(0) items, and pair items, for later use. # Check for lookahead compatibility. Abstract base class, subclassed by {Shift,Reduce}Action. Shift action, with assocated nextState. Reduce action, with associated production. The Spec class contains the read-only data structures that the Parser class needs in order to parse input.  Parser generation results in a Spec instance, which can then be shared by multiple Parser instances. modules : Either a single module, or a list of modules, wherein to           look for parser generator directives in docstrings.  pickleFile : The path of a file to use for Spec pickling/unpickling.  pickleMode :  "r" : Unpickle from pickleFile.               "w" : Pickle to pickleFile.               "rw" : Unpickle/pickle from/to pickleFile.  skinny : If true, discard all data that are only strictly necessary          while constructing the parsing tables.  This reduces          available debugging context, but substantially reduces          pickle size.  logFile : The path of a file to store a human-readable copy of the           parsing tables in.  graphFile : The path of a file to store a graphviz representation             (dot format) of the precedence relationship graph.  verbose : If true, print progress information while generating the           parsing tables. # Default (no) precedence. # Symbols are maintained as two separate sets so that non-terminals and # terminals (tokens) can be operated on separately where needed. # Everything below this point is computed from the above (once # introspection is complete). # Each element corresponds to an element in _action. # LR parsing tables.  The tables conceptually contain one state per row, # where each row contains one element per symbol.  The table is # conceptually in row-major form, but each row is actually a dictionary. # If no entry for a symbol exists for a particular state, then input of # that symbol is an error for that state. # Number of LR impurities (does not affect GLR). # Introspect modules and generate parse tables. # Wrap single module in a list. # Print a very reduced summary, since most info has been discarded. #======================================================================= #======================================================================= Compile the specification into data structures that can be used by the Parser class for parsing. # Get the grammar specification. # Augment grammar with a special start symbol and production: # #   <S> ::= S <$>. # Resolve references in the grammar specification. # Check for a compatible pickle. # Create the collection of sets of LR(1) items. # Just because the pickle was compatible does not mean that it is # valid for parsing. # Generate LR(1) parsing tables. # Disambiguate actions. # Check for unused or ambiguous definitions, as well as reporting # ambiguities. # Pickle the spec, if method parameters so dictate, even if # there were validation errors, so that the pickle might be # used in part during later runs. # Pickle the spec, if method parameters so dictate. # Discard data that are not needed during parsing.  Note that # _pickle() also discarded data that don't even need to be pickled. # Introspect modules and find special parser declarations.  In order to be # a special class, the class must both 1) be subclassed from Token or # Nonterm, and 2) contain the appropriate %foo docstring. #=========================================================== # Precedence. # # Precedence relationship. #=========================================================== # Token. # #=========================================================== # Nonterm. # # Start symbol. #=========================================================== # Resolve all symbolic (named) references. # Build the graph of Precedence relationships. # Resolve Token-->Precedence references. # Resolve Nonterm-->Precedence references. # Resolve Nonterm-->{Nonterm,Token,Precedence} references. # Symbolic reference. # Precedence. # Inherit the non-terminal's precedence. # Build the graph of Precedence relationships. # Resolve symbolic references and populate equiv/dominators. # Create equivalence classes for all Precedence classes.  Since the # Precedence classes are equivalent, they also share dominator sets. # Merge the sets of equivalent Precedence classes. # Share the equiv set. # Use the equivalence classes to merge dominator sets and share them. # Merge the sets of dominator Precedence classes. # Share the dominator set. # Write graphviz precedence graph to graphFile, if graphFile was # specified. # Iteratively build dominator sets until no more work can be done. # No need to do more than this. # Check for cycles in the graph. # Store state to a pickle file, if requested. # Discard data that don't need to be pickled. # Restore state from a pickle file, if a compatible one is provided.  This # method uses the same set of return values as does _compatible(). # Any exception at all in unpickling can be assumed to be due to # an incompatible pickle. # Copy spec's data structures. # Precedences are incompatible, so great care has to be taken # when copying from the pickle.  Overwrite all precedence # specifications in spec with the new ones, then copy over all # of the new symbols/productions (but not the new precedences, # of course).  This still leaves table generation, which is # done by the _prepare() method later. # Nonterminals. # Productions. # Tokens. # Copy spec data structures that are usable regardless of whether # the parsing tables need to be rebuilt. # Determine whether other is compatible with self.  Note that self is not # completely initialized; the idea here is to determine whether other's # data structures can be copied *before* doing the work of building parsing # tables. # # Itemsets and precedences are not directly related, other than that # symbols have precedences associated with them.  Therefore, we check for # the following cases: # #   "compatible" : Completely compatible. # #   "repickle" : Compatible, but pickle needs to be regenerated. # #   "itemsets" : Itemsets are compatible, but precedence specifications are #                not. # #   "incompatible" : No useful compatibility. # Precedences. # Nonterminals. # Productions. # Tokens. # User start symbol. # The itemsets have to be regenerated, since they weren't pickled. # Check for unused prececence/token/nonterm/reduce specifications, then # throw a SpecError if any ambiguities exist in the grammar. # Previous code guarantees that all precedence/token/nonterm names are # unique.  Therefore, we can build a single dictionary here that keys on # names. # Precedences. # Tokens. # Nonterms. # Productions. # Write to logFile, if one was specified. # Conflicts are fatal. # Make sure to let the user know about unused symbols if verbosity is # enabled, and there weren't any conflicts to cause notification via an # exception. # Compute the first sets for all symbols. # Terminals. # first(X) is X for terminals. # Non-terminals. # # Repeat the following loop until no more symbols can be added to any # first set. # Merge epsilon if there is an empty production. # Iterate through the RHS and merge the first sets into # this symbol's, until a preceding symbol's first set does # not contain epsilon. # Compute the follow sets for all symbols. # Repeat the following loop until no more symbols can be added to any # follow set. # For all A ::= aBb, merge first(b) into follow(B). # For A ::= ab, or A ::= aBb where first(b) contains <e>, # merge follow(A) into follow(B). # Compute the collection of sets of LR(1) items. # Add {[S' ::= * S $., <e>]} to _itemSets. # List of state numbers that need to be processed. # itemSetsHash uses itemsets as keys.  A value is a list of _itemSets # indices; these itemsets are the ones referred to the key itemset. # Process worklist in MRU order.  This # causes a depth-first traversal. # Compute LR parsing tables. # The collection of sets of LR(1) items already exists. #=================================================================== # _action. # X ::= a*Ab # Check if this is the start state. # X ::= a* #=================================================================== # _goto. # Add a symbol action to state, if the action doesn't already exist. # Look for action ambiguities and resolve them if possible. # Construct a list that corresponds to acts; each element # indicates whether to preserve the action. # Fill in the cells of actStats. # Look for actions that can coexist or dominate all other # actions. # Replace the action set if there exists a valid resolution # among the actions. # Update summary stats. # Compute how to resolve an action conflict. # # ret: "neither" : Discard both. #      "old"     : Keep old. #      "both"    : Keep both. #      "new"     : Keep new. #      "err"     : Unresolvable conflict. # Discard new action. # Discard old action. # Fatal reduce/reduce conflict. # Conflicting associativity. # Determine associativity.  If only one of the actions has # %fail associativity, it is overridden by the other. # No specified relationship between precedences. LR(1) parser.  The Lr class uses a Spec instance in order to parse input that is fed to it via the token() method, and terminated via the eoi() method. A list of parsing results.  For LR parsing, there is only ever one result, but for compatibility with the Glr interface, start is a list. Feed a token to the parser. Signal end-of-input to the parser. # <$>. # Python's method definition syntax makes returning self from %reduce # methods cumbersome, so translate None here. #=============================================================================== # Begin graph-structured stack (GSS) classes. # Graph-structured stack. Graph-structured stack edge. Graph-structured stack node. # Iterate over all paths of length pathLen.  Path length is measured as the # number of edges in the path, so a path of length 0 still consists of a # single node. # # Each path is encoded as a list that alternates between nodes and edges, # where the first and last elements are always nodes. # # <e>-grammars can cause cycles, which requires that we avoid infinite # recursion. # Avoid infinite recursion due to <e>-production cycles. # # End graph-structured stack (GSS) classes. #=============================================================================== GLR parser.  The Glr class uses a Spec instance in order to parse input that is fed to it via the token() method, and terminated via the eoi() method. # Initialize with a stack that is in the start state. Feed a token to the parser. Signal end-of-input to the parser. # Gather the start symbols from the stacks. # epsilons is a dictionary that maps production-->[tops].  The purpose # is to avoid repeating the same epsilon production on a particular # stack top.  Ordinary productions do not require this care because we # can notice when a path has already been used for a production. # Enqueue work. # Unexpected token for this stack. # Iterate over all reduction paths through stack and # enqueue them. # Process the work queue. # Build the list of RHS semantic values to pass to the reduction action. # Call the user reduction method. # top is compatible with the reduction result we want to add to # the set of stack tops. # There is already a below<--top link, so merge # competing interpretations. # Create a new below<--top link. # Enqueue reduction paths that were created as a result of # the new link. # There is no compatible stack top, so create a new one. # Enqueue paths that incorporate edge. # Do nothing, since enqueueing a reduction # would result in performing the same reduction # twice. # Iterate over all reduction paths through stack and # enqueue them if they incorporate edge.