Miscellany

#!/usr/bin/env python


class rule:
    lhs = ""
    rhs = []
    def __init__(self,lhs, rhs):
        self.lhs = lhs
        self.rhs = rhs


rules = []

rules.append(rule("S", ["NP", "VP"]))
rules.append(rule("NP", ["DET", "N"]))
rules.append(rule("NP", ["PN"]))
rules.append(rule("NP", ["NP", "and", "NP"]))
rules.append(rule("VP", ["V"]))
#rules.append(rule("VP", ["V", "NP"]))
rules.append(rule("PN", ["Hector"]))
#rules.append(rule("V", ["barked"]))
rules.append(rule("V", ["chased"]))
rules.append(rule("DET", ["some"]))
rules.append(rule("DET", ["few"]))
rules.append(rule("N", ["cats"]))
rules.append(rule("N", ["birds"]))


# main loop

input = ["Hector", "chased"]

stack = []

history = []

delim = "====================="

# do .. while
while True:

    print delim
    print "STACK!"
    print str(stack)
    print delim
    print "INPUT!"
    print str(input)
    print delim

    
    # always try to reduce once
    # if we were able to reduce once, let's try again
    # if we can't reduce, then goto shift 
    while True and not len(stack)== 0:
        print "trying to reduce"
        reduce = False
        # we start counting at 1
        for rule in rules:
            print "rule is " + str(rule)
            rhs = rule.rhs
            print "rule RHS is " + str(rhs)

            # temp copies
            r = list(reversed(rhs))
            s = list(reversed(stack))

            try:
                res = True
                # look at every constituent in RHS
                # they all need to match the top of the stack
                for index in range(0, len(r)):
                    rhs_constituent = r[index]
                    constituent = s[index]
                    print "RHS constituent " + str(rhs_constituent)
                    print "stack constituent " + str(constituent)
                    if rhs_constituent != constituent:
                        res = False
                if res:
                    print "RHS matched"
                    # remove RHS side from stack
                    for foo in rhs:
                        stack.pop()
                    print "Reducing.."
                    reduce = True
                    # now that we've eaten as much as possible, 
                    # push rule LHS to stack
                    stack.append(rule.lhs)
                    # we're done here - next shift/reduce cycle
                    break
            except IndexError:
                print "index out of bounds"
                print "that's ok with me if it's ok with you"

        if not reduce:
            break
        
    # shift
    
    print "Shifting.."
    if len(input) == 0:
        print "iput is empty"
    else:
        token = input.pop(0)
        stack.append(token)
    reduce = True       
            
    if  (len(stack) == 1 and stack[0] == "S"):
        print "input parsed succesfully"
        break
    else:
        if (len(stack) == 0):
            print "stack is empty, this should not happen"
            break
        #if (len(input) == 0):
        #    print "input is empty, this should not happen"
        #    print str(stack)
        #    break
        print str(stack)