#===============================================================================
# Copyright (c) 2007 Jason Evans <jasone@canonware.com>
#
# 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
    David Pager
    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
            Scott McPeak
            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 pickle
# 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 __lt__(self, other):
      return self.seq<other.seq

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

    def __hash__(self):
      return hash(self.name)

    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 range(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 range(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 __lt__(self, other):
      return self.seq < other.seq

    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 __lt__(self, other):
      assert isinstance(other, Item)
      return self.hash.__lt__(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.keys()]
      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.keys():
          if sSym in oLookahead:
            return False

      for oSym in oLookahead.keys():
          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.keys()]
      kernel.sort()
      added = [item for item in self._added.keys()]
      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.keys():
          ret += item.hash
      return ret

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

    def __iter__(self):
      for item in self.keys():
          assert item.production.lhs.name == "<S>" or item.dotPos != 0
          yield item
      for item in self._added.keys():
          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, list(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 list(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.keys():
          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)
      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, list(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.keys():
          if item in self:
            lookahead = self[item].lookahead
            tLookahead = []
            for sym in item.lookahead.keys():
                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, \
              list(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.keys():
          if sItem not in other:
            return False
          oItem = other[sItem]
          pairs.append((sItem, oItem))

      # Check for lookahead compatibility.
      for i in range(len(pairs)-1):
          iPair = pairs[i]
          isItem = iPair[0]
          ioItem = iPair[1]
          for j in range(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.values()]
      deco.sort()
      for elm in deco:
          prec = elm[1]
          lines.append("  %r" % prec)

      lines.append("Tokens:")
      syms = [sym for sym in self._tokens.values()]
      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.values()]
      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 range(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 range(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,     # Was: .__func__, or .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 type 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.values():
          if type(token.prec) == str:
            token.prec = self._precedences[token.prec]

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

      # Resolve Nonterm-->{Nonterm,Token,Precedence} references.
      for nonterm in self._nonterms.values():
          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 range(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.values():
          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.values():
          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.values():
          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('digraph Precedence {', file=f)
          print('    graph [bgcolor=black, labeljust="l"]', file=f)
          print(('    node [shape=record, style=filled, color=black, ' + \
            'fillcolor=gray, fontname=Helvetica, fontsize=10.0]'), file=f)
          print('    edge [color=gray]', file=f)
          for precA in self._precedences.values():
            if precA == precA.equiv[0]:
                print(('    Precedence_%s [label="{%s}"]') % (precA.name, \
                  "\\n".join(["%s (%s)" % (p.name, p.assoc) \
                  for p in precA.equiv])), file=f)
                for precB in precA.dominators:
                  print('    Precedence_%s -> Precedence_%s' % \
                    (precB.equiv[0].name, precA.equiv[0].name), file=f)
          print('}', file=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.values():
            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.values():
          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, "wb")
          pickle.dump(self, f, protocol=pickle.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 = pickle.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 range(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.keys():
                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.values():
          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 range(len(prod.rhs) - 1):
                  for j in range(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 range(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... ", end=' ')
          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 = list(self._tokens.values()) + list(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]), end=' ')
          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.keys():
                  self._actionAppend(state, lookahead, \
                    ReduceAction(item.production))
            else:
                assert False
          #===================================================================
          # _goto.
          state = {}
          self._goto.append(state)
          for nonterm in self._nonterms.values():
            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... ", end=' ')
          sys.stdout.flush()

      for stateInd in range(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 range(len(acts)):
                actI = acts[i]
                for j in range(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 range(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:", end=' ')
          for node in self._stack:
            print("%r" % node[0], end=' ')
          print()
          print("      ", end=' ')
          for node in self._stack:
            print("%r%s" % (node[1], \
              (" " * (len("%r" % node[0]) - len("%r" % node[1])))), end=' ')
          print()

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

      r = self._production(production, rhs)

      for i in range(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:", end=' ')
            else:
                print("    %d:" % i, end=' ')
            for elm in path:
                print("%r" % elm, end=' ')
            print()
            i += 1
