WebSVN – programming – Diff – /school/cs311/proj4/proj4.py

 #   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.
+#
 # Check for <Python-2.3 compatibility (boolean values)
 try:
   True, False
 except NameError:
   (True, False) = (1, 0)
 import sys
-class Queue:
-    """Implements a basic FIFO queue"""
-    def __init__(self):
+# Default Symbols
-        self.q = []
+SYM_E = "A" # "E"
-    def empty(self):
+SYM_T = "B" # "T"
-        """Empty the queue"""
+SYM_P = "C" # "P"
-        self.q = []
+SYM_F = "F"
-    def enqueue(self, elem):
+SYM_N = "N"
-        """Enqueue an element"""
+SYM_V = "V"
-        self.q.append(elem)
+SYM_D = "D"
-    def dequeue(self):
+SYM_EPRM = "E'"
-        """Get the object at the front of the queue"""
-        elem = self.q[0]
+SYM_TPRM = "T'"
-        self.q = self.q[1:]
+SYM_PPRM = "P'"
-        return elem
+SYM_EMPTY = ""
 class RecursiveDescentParser:
     def __init__(self):
         self.__clear()
         self.derivation = ""
     def __replace_sym(self, to_repl, with_this):
         """Replace a string in the derivation with another string"""
-        pos = s.find(to_repl)
+        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 = s[:pos] + str(with_this) + s[pos+len(to_repl):]
+        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]
     def __input_test_str(self):
         self.str = raw_input("input str: ")
     def main_menu(self):
                 done = True
             else:
                 print 'Bad Selection'
                 print
+    def __print_deriv(self, with_arrow=True):
+        if with_arrow:
+            print "%s ->" % (self.derivation, ),
+        else:
+            print "%s" % (self.derivation, )
     def __test_str(self):
+        self.derivation = SYM_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' % ((self.procE() and len(self.str) == self.strpos) and 'Completed' or 'Failed', )
+        print 'Parsing: %s' % (ans and 'Completed' or 'Failed', )
+        if not ans:
+            print 'All input used: %s' % (all_input_used and 'True' or 'False', )
         print
     def procE(self):
-        print 'procE(%s) ->' % (self.str[self.strpos:])
+        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
-        print 'procEprm(%s) ->' % (self.str[self.strpos:])
         # 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):
-        print 'procT(%s) ->' % (self.str[self.strpos:])
+        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
-        print 'procTprm(%s) ->' % (self.str[self.strpos:])
         # 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):
-        print 'procP(%s) ->' % (self.str[self.strpos:])
+        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
-        print 'procPprm(%s) -> ' % (self.str[self.strpos:])
         # 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):
-        print 'procF(%s) ->' % (self.str[self.strpos:])
+        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):
-        print 'procN(%s) ->' % (self.str[self.strpos:])
+        self.__print_deriv()
-        if self.procD(): # we have one digit
+        nums = range(100) # get 0-99
-            if self.procD(): # two digits
+        nums.reverse()    # make it 99-0
-                return True
+        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 True
         return False
     def procV(self):
-        print 'procV(%s) ->' % (self.str[self.strpos:])
+        self.__print_deriv()
-        return self.procD()
-    def procD(self):
-        print 'procD(%s) ->' % (self.str[self.strpos:])
-        try:
-            # Check if we are a single digit
-            if self.str[self.strpos] in '0123456789':
+        if self.str[self.strpos] in '0123456789':
-                self.strpos += 1
+            self.strpos += 1
-                return True
-        except IndexError: # ran out of input
+            self.__replace_sym(SYM_V, self.str[self.strpos-1])
-            return False
+            return True
         return False
 if __name__ == '__main__':
     rdp = RecursiveDescentParser()
     rdp.main_menu()

Subversion Repositories programming

(root)/school/cs311/proj4/proj4.py – Rev 166 → 167