text: import sys
  from collections import deque
  from itertools import chain
  from util.mixin import Keyed, Comparable
  from util.moreitertools import alternations
  from cfg.core import ParseTree
  from cfg.table import build_slr_table, END_MARKER
  
  class InputNotRecognized(Exception):
      '''An exception indicating that the input string to a parsing algorithm is
      not recognized by the parser.'''
      pass
  
  def enumerate_trees(v):
      '''Given a vertex from a packed shared parse forest, enumerate all of the
      parse trees encoded therein. Cyclic parses are encoded as cyclic trees.'''
      return _enumerate_trees(v, {})
  
  def _enumerate_trees(v, seen):
      if v.children:
          for child_set in v.children:
              for alt in alternations(map(lambda x: list(_enumerate_trees(x, seen)), child_set)):
                  yield ParseTree(v.symbol, alt)
      else:
          yield ParseTree(v.symbol)
  
  class Node(Comparable, Keyed):
      '''A node in the parse graph of the GLR algorithm.'''
  
      def __init__(self, state, cnode=None, cvertex=None):
          self._state = state
          self._children = [] if cnode is None else [(cnode, cvertex)]
  
      @property
      def state(self): return self._state
  
      @property
      def children(self): return self._children
  
      def link_to(self, other, vertex):
          self._children.append((other, vertex))
  
      def __key__(self): return id(self)
  
      def __repr__(self): return 'Node(%s)' % (self.state)
  
  class Vertex(Comparable, Keyed):
      '''A vertex in the packed shared parse forest generated by the GLR
      algorithm.'''
  
      def __init__(self, symbol, children=None):
          self._symbol = symbol
          self._children = [] if children is None else [children]
  
      @property
      def symbol(self): return self._symbol
  
      @property
      def children(self): return self._children
  
      def add_children(self, c): self._children.append(c)
  
      def __key__(self): return id(self)
  
      def __repr__(self): return 'Vertex(%s)' % (self.symbol)
  
  def glr_parse(table, input_string):
      '''Parse an input string with respect to a parse table using the GLR
      algorithm. If the string is recognized by the grammar, return a list of
      Vertex objects representing the roots of the packed shared parse forest
      generated by the algorithm. If the string is not recognized, raise an
      InputNotRecognized error.'''
  
      def enqueue_paths(node, production):
          def r(node, length, path):
              if length > 0:
                  for child, vertex in node.children:
                      path[length - 1] = vertex
                      r(child, length - 1, path)
              else: R.append((node, production, path[:]))
          length = len(production.right_side)
          r(node, length, [None] * length)
  
      def enqueue_paths_through(node, production, vertex):
          def r(node, length, passed, path):
              if length > 0:
                  for cnode, cvertex in node.children:
                      path[length - 1] = cvertex
                      r(cnode, length - 1, passed or cvertex is vertex, path)
              elif passed:
                  R.append((node, production, path[:]))
          length = len(production.right_side)
          r(node, length, False, [None] * length)
  
      U = { 0 : Node(0) }
      R = deque()
      Q = deque()
      r = None
      for ai in chain(input_string, [END_MARKER]):
          A = deque(U.values())
          while True:
              if A:
                  v = A.popleft()
                  if table.has_accept(v.state, ai): r = v
                  Q.extend((v, s) for s in table.get_shifts(v.state, ai))
                  for p in table.get_reductions(v.state, ai):
                      enqueue_paths(v, p)
              elif R:
                  w, p, path = R.popleft()
                  N = p.left_side
                  s = table.get_goto(w.state, N)
                  if s in U:
                      u = U[s]
                      for cnode, z in u.children:
                          if cnode is w:
                              z.add_children(path)
                              break
                      else:
                          z = Vertex(N, path)
                          u.link_to(w, z)
                          for v in set(U.values()) - set(A):
                              for q in table.get_reductions(v.state, ai):
                                  enqueue_paths_through(v, q, z)
                  else:
                      z = Vertex(N, path)
                      u = Node(s, w, z)
                      A.append(u)
                      U[s] = u
              else: break
          if r is not None:
              return [cvertex for cnode, cvertex in r.children]
          if not Q:
              raise InputNotRecognized('the input string is not recognized by the grammar')
          else:
              U.clear()
              x = Vertex(ai)
              while Q:
                  v, s = Q.popleft()
                  if s in U:
                      u = U[s]
                      u.link_to(v, x)
                  else:
                      u = Node(s, v, x)
                      U[s] = u
  
  def parse(grammar, input_string):
      '''Parse an input string of Terminals with respect to some context free
      grammar, enumerating all of its valid parse trees. If the language of the
      grammar does not recognize the input, an InputNotRecognized error is
      raised. At most one parse tree will be returned if the grammar is
      unambiguous. The parsing algorithm imposes no restrictions on the class of
      CFG used; however, cyclic grammars may cause an infinite loop during the
      parse tree enumeration process. A future implementation will instead encode
      such cyclicities as cycles in the parse tree data structure.'''
      for v in glr_parse(build_slr_table(grammar), input_string):
          for t in enumerate_trees(v):
              yield t
  
  