class Accept(Exception):
    "this exception is raised if a Grammar recognizes a string"
    def __init__(self, pda):
        Exception.__init__(self)
        self.pda = pda
        
class Reject(Exception):
    "this exception is raised if a Grammar rejects a string"

class Grammar:
    def __init__(self, vars, terms, start):
        """vars and terms are disjoint sets of strings;
        start is a member of terms.  rules is a mapping from
        vars to lists of strings of terms and vars.
        """
        self.vars = vars
        self.terms = terms
        self.start = start
        self.rules = dict()
    
    def add_rule(self, var, rhs):
        """add a new rule of the form '(var) can be a (rhs)'""" 
        self.rules.setdefault(var, []).append(rhs)

    def process(self, string):
        """process the given string and print 'accept' or 'reject' """
        try:
            self._process(string)
        except Accept, e:
            print 'accept', e.pda
            
        except Reject:
            print 'reject'

    def _process(self, string):
        """process the given string and raise Accept or Reject"""

        # initialize the queue with one PDA
        q = Queue()
        pda = PDA(self, string)
        q.push(pda)
        
        while q.not_empty():
            # get the first PDA
            pda = q.pop()

            # process it and add the results to the queue
            for new in pda.step():
                q.push(new)

        # if the queue is empty, that means we ran out of
        # viable PDAs, so we reject
        raise Reject

import copy

class PDA:
    def __init__(self, grammar, string):
        """grammar is a Grammar; string is the unprocessed part
        of the input string.  stack is a Stack, which is initialized
        with None (as a marker for an empty stack) and the start
        variable.
        """
        self.grammar = grammar
        self.string = string
        self.stack = Stack()
        self.stack.push(None)
        self.stack.push(grammar.start)

    def copy(self):
        """make a copy of this PDA"""
        return copy.deepcopy(self)

    def step(self):
        """perform one processing step on this PDA and return a list
        of viable PDAs"""

        top = self.stack.pop()

        # if the stack is empty
        if top == None:

            # and there is leftover input
            if self.string:
                
                # then this PDA is not viable
                return []
            else:
                # if there is no more input, raise an
                # Accept object that contains a ref to this PDA
                raise Accept(self)

        # if the top of the stack is a terminal
        elif top in self.grammar.terms:

            # and there is no more input
            if self.string == '':

                # then this PDA is not viable
                return []

            # if the terminal matches the input
            if top == self.string[0]:

                # then consume the input and return this PDA
                self.string = self.string[1:]
                return [self]

            else:
                # otherwise this PDA is not viable
                return []

        # if the top of the stack is a variable
        elif top in self.grammar.vars:

            # return a list of PDAs, one for each rule
            return self.branch(top)
            
        else:
            raise Exception, "this shouldn't happen"

    def branch(self, top):
        """process a variable by creating one PDA for each rule"""
        pdas = []

        # for each right hand side
        for rhs in self.grammar.rules[top]:

            # copy the current PDA
            pda = self.copy()

            # push the right hand side
            pda.stack.pushrhs(rhs)

            # add this PDA to the list
            pdas.append(pda)

        return pdas


class Sequence:
    """the parent class for Stack and Queue"""
    def __init__(self):
        self.elts = []

    def not_empty(self):
        return self.elts

    def push(self, elt):
        self.elts.append(elt)

class Stack(Sequence):
    """a first-in last-out stack"""
    def pop(self):
        return self.elts.pop(-1)

    def pushrhs(self, seq):
        """add the symbols for the right hand side in reverse order"""
        for symbol in reversed(seq):
            self.push(symbol)

class Queue(Sequence):
    """a first-in first-out queue"""
    def pop(self):
        return self.elts.pop(0)


def main():

    # create a grammar that recognizes strings with
    # nested pairs of 0 and 1
    vars = set(['S', 'T'])
    terms = set(['0', '1'])
    start = 'S'
    g = Grammar(vars, terms, start)
    g.add_rule('S', 'TS')
    g.add_rule('S', '')
    g.add_rule('T', '0S1')

    # test Grammar.process
    g.process('01')
    g.process('0011')
    g.process('0101')
    g.process('001')
    g.process('00111')

        
if __name__ == '__main__':
    main()