Subversion Repositories programming

#!/usr/bin/env python
# Copyright: Ira W. Snyder
# Start Date: 2005-11-18
# End Date: 2005-11-30
# License: Public Domain
#
# Changelog Follows:
#
# 2005-11-18
# * Just getting the basics in place, since we haven't been given
#   the whole description of the project yet.
#
# 2005-11-26
# * Got the whole class working, now to implement pretty-printing
#
# 2005-11-28
# * This has pretty-printing now. (The derivation looks correct)
# * Needs testing still, but for every case I can come up with, it works.
#
# 2005-11-29
# * Add error checking to the input.
# * Add comments to all of the methods.
#

# Check for <Python-2.3 compatibility (boolean values)
try:
  True, False
except NameError:
  (True, False) = (1, 0)

import sys

# Default Symbols
SYM_E = "A" # "E"  --  These next few symbols were renamed to make
SYM_T = "B" # "T"  --  output easier.
SYM_P = "C" # "P"
SYM_F = "F"
SYM_N = "N"
SYM_V = "V"
SYM_D = "D"
SYM_EPRM = "E'"
SYM_TPRM = "T'"
SYM_PPRM = "P'"
SYM_EMPTY = ""

class RecursiveDescentParser:
    """An implementation of a Recursive Descent Parser for a simple
    algebraic language, with both variables and numbers."""
    
    def __init__(self):
        self.__clear()

    def __clear(self):
        self.str = ""   # the string of input to test
        self.strpos = 0 # the current position in str
        self.derivation = "" # the current state the grammar is in

    def __replace_sym(self, to_repl, with_this):
        """Replace a string in the derivation with another string"""

        pos = self.derivation.find(to_repl)
    
        if pos == -1:
            #print 'str: %s' % (self.derivation, )
            #print 'to_repl: %s' % (to_repl, )
            #print 'with_this: %s' % (with_this, )
            raise ValueError
    
        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]

    def __input_test_str(self):
        """Read a test string from the user"""

        while len(self.str) <= 0:
            self.str = raw_input("input str: ")

    def main_menu(self):

        done = False

        while not done:
            print 'Menu:'
            print '========================================'
            print '1. Test a string'
            print '2. Quit'
            print
            s = raw_input('Choice >>> ')
            print

            if s == '1':
                self.__clear()
                self.__input_test_str()
                self.__test_str()
            elif s == '2':
                done = True
            else:
                print 'Bad Selection'
                print

    def __print_deriv(self, with_arrow=True):
        """Print out the derivation as it is at this moment, either
        with or without the arrow."""

        if with_arrow:
            print "%s ->" % (self.derivation, ),
        else:
            print "%s" % (self.derivation, )
                
    def __test_str(self):
        """Run test.str through the parser"""

        self.derivation = SYM_E[:] # set the initial symbol: E
        
        procE_ans = self.procE()
        all_input_used = (len(self.str) == self.strpos)
        ans = procE_ans and all_input_used

        self.__print_deriv(with_arrow=False)
        print
        print 'Parsing: %s' % (ans and 'Completed' or 'Failed', )

        if not ans:
            print 'All input used: %s' % (all_input_used and 'True' or 'False', )

        print

    ####
    ####
    #### NOTE: for all of the proc_X rules, see the grammar provided. They
    #### explain what is going on, I think. These functions are just direct
    #### implementations of the grammar.
    ####
    ####
        
    def procE(self):
        self.__print_deriv()

        # Catch the exception generated below if we don't have enough
        # input to 'look ahead'
        try:
            self.__replace_sym(SYM_E, SYM_T + SYM_EPRM)
            return self.procT() and self.procEprm()
        except IndexError:
            print 'Not enough input to continue, failed.'
            return False

    def procEprm(self):
        self.__print_deriv()

        # Check empty str
        if self.strpos >= len(self.str):
            self.__replace_sym(SYM_EPRM, SYM_EMPTY)
            return True

        # Check +
        if self.str[self.strpos] == '+':
            self.strpos += 1
            self.__replace_sym(SYM_EPRM, '+' + SYM_T + SYM_EPRM)
            return self.procT() and self.procEprm()

        # Check -
        if self.str[self.strpos] == '-':
            self.strpos += 1
            self.__replace_sym(SYM_EPRM, '-' + SYM_T + SYM_EPRM)
            return self.procT() and self.procEprm()

        # We accept empty str, so take it
        self.__replace_sym(SYM_EPRM, SYM_EMPTY)
        return True

    def procT(self):
        self.__print_deriv()

        self.__replace_sym(SYM_T, SYM_P + SYM_TPRM)
        return self.procP() and self.procTprm()

    def procTprm(self):
        self.__print_deriv()
        
        # Check empty str
        if self.strpos >= len(self.str):
            self.__replace_sym(SYM_TPRM, SYM_EMPTY)
            return True

        # Check *
        if self.str[self.strpos] == '*':
            self.strpos += 1
            self.__replace_sym(SYM_TPRM, '*' + SYM_P + SYM_TPRM)
            return self.procP() and self.procTprm()

        # we accept empty str, so take it
        self.__replace_sym(SYM_TPRM, SYM_EMPTY)
        return True

    def procP(self):
        self.__print_deriv()

        self.__replace_sym(SYM_P, SYM_F + SYM_PPRM)
        return self.procF() and self.procPprm()

    def procPprm(self):
        self.__print_deriv()

        # Check empty str
        if self.strpos >= len(self.str):
            self.__replace_sym(SYM_PPRM, SYM_EMPTY)
            return True

        # check exp symbol
        if self.str[self.strpos] == '^':
            self.strpos += 1
            self.__replace_sym(SYM_PPRM, '^' + SYM_F + SYM_PPRM)
            return self.procF() and self.procPprm()

        # we accept empty str, so take it
        self.__replace_sym(SYM_PPRM, SYM_EMPTY)
        return True

    def procF(self):
        self.__print_deriv()

        # Check x
        if self.str[self.strpos] == 'x':
            self.strpos += 1
            self.__replace_sym(SYM_F, 'x' + SYM_V)
            return self.procV()

        # Check (E)
        if self.str[self.strpos] == '(':
            self.strpos += 1
            self.__replace_sym(SYM_F, '(' + SYM_E + ')')

            if self.procE():
                if self.str[self.strpos] == ')':
                    self.strpos += 1
                    return True

                return False

            return False

        # Must be a number
        self.__replace_sym(SYM_F, SYM_N)
        return self.procN()

    def procN(self):
        self.__print_deriv()

        nums = range(100) # get 0-99
        nums.reverse()    # make it 99-0

        for n in nums:
            if self.str[self.strpos:self.strpos+len(str(n))] == str(n):
                self.strpos += len(str(n))
                self.__replace_sym(SYM_N, str(n))
                return True

        return False
    
    def procV(self):
        self.__print_deriv()

        if self.str[self.strpos] in '0123456789':
            self.strpos += 1
            self.__replace_sym(SYM_V, self.str[self.strpos-1])
            return True

        return False
    
if __name__ == '__main__':
    rdp = RecursiveDescentParser()
    rdp.main_menu()