Subversion Repositories programming

Rev

Rev 166 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
161 ira 1 
#!/usr/bin/env python
2 
# Copyright: Ira W. Snyder
3 
# Start Date: 2005-11-18
4 
# End Date:
5 
# License: Public Domain
6 
#
7 
# Changelog Follows:
8 
#
9 
# 2005-11-18
10 
# * Just getting the basics in place, since we haven't been given
11 
#   the whole description of the project yet.
12 
#
166 ira 13 
# 2005-11-26
14 
# * Got the whole class working, now to implement pretty-printing
15 
#
167 ira 16 
# 2005-11-28
17 
# * This has pretty-printing now. (The derivation looks correct)
18 
# * Needs testing still, but for every case I can come up with, it works.
19 
#
161 ira 20 
 
21 
# Check for <Python-2.3 compatibility (boolean values)
22 
try:
23 
  True, False
24 
except NameError:
25 
  (True, False) = (1, 0)
26 
 
162 ira 27 
import sys
163 ira 28 
 
167 ira 29 
# Default Symbols
30 
SYM_E = "A" # "E"
31 
SYM_T = "B" # "T"
32 
SYM_P = "C" # "P"
33 
SYM_F = "F"
34 
SYM_N = "N"
35 
SYM_V = "V"
36 
SYM_D = "D"
37 
SYM_EPRM = "E'"
38 
SYM_TPRM = "T'"
39 
SYM_PPRM = "P'"
40 
SYM_EMPTY = ""
164 ira 41 
 
162 ira 42 
class RecursiveDescentParser:
161 ira 43 
    def __init__(self):
162 ira 44 
        self.__clear()
161 ira 45 
 
46 
    def __clear(self):
47 
        self.str = ""   # the string of input to test
48 
        self.strpos = 0 # the current position in str
166 ira 49 
        self.derivation = ""
161 ira 50 
 
166 ira 51 
    def __replace_sym(self, to_repl, with_this):
52 
        """Replace a string in the derivation with another string"""
53 
 
167 ira 54 
        pos = self.derivation.find(to_repl)
166 ira 55 
 
56 
        if pos == -1:
167 ira 57 
            #print 'str: %s' % (self.derivation, )
58 
            #print 'to_repl: %s' % (to_repl, )
59 
            #print 'with_this: %s' % (with_this, )
166 ira 60 
            raise ValueError
61 
 
167 ira 62 
        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]
166 ira 63 
 
161 ira 64 
    def __input_test_str(self):
162 ira 65 
        self.str = raw_input("input str: ")
161 ira 66 
 
67 
    def main_menu(self):
68 
 
69 
        done = False
70 
 
71 
        while not done:
72 
            print 'Menu:'
73 
            print '========================================'
74 
            print '1. Test a string'
75 
            print '2. Quit'
76 
            print
77 
            s = raw_input('Choice >>> ')
78 
            print
79 
 
80 
            if s == '1':
162 ira 81 
                self.__clear()
161 ira 82 
                self.__input_test_str()
83 
                self.__test_str()
84 
            elif s == '2':
85 
                done = True
86 
            else:
87 
                print 'Bad Selection'
88 
                print
89 
 
167 ira 90 
    def __print_deriv(self, with_arrow=True):
91 
        if with_arrow:
92 
            print "%s ->" % (self.derivation, ),
93 
        else:
94 
            print "%s" % (self.derivation, )
95 
 
162 ira 96 
    def __test_str(self):
167 ira 97 
        self.derivation = SYM_E[:]
98 
 
99 
        procE_ans = self.procE()
100 
        all_input_used = (len(self.str) == self.strpos)
101 
        ans = procE_ans and all_input_used
102 
 
103 
        self.__print_deriv(with_arrow=False)
163 ira 104 
        print
167 ira 105 
        print 'Parsing: %s' % (ans and 'Completed' or 'Failed', )
161 ira 106 
 
167 ira 107 
        if not ans:
108 
            print 'All input used: %s' % (all_input_used and 'True' or 'False', )
109 
 
110 
        print
111 
 
162 ira 112 
    def procE(self):
167 ira 113 
        self.__print_deriv()
163 ira 114 
 
164 ira 115 
        # Catch the exception generated below if we don't have enough
116 
        # input to 'look ahead'
117 
        try:
167 ira 118 
            self.__replace_sym(SYM_E, SYM_T + SYM_EPRM)
164 ira 119 
            return self.procT() and self.procEprm()
120 
        except IndexError:
121 
            print 'Not enough input to continue, failed.'
122 
            return False
162 ira 123 
 
163 ira 124 
    def procEprm(self):
167 ira 125 
        self.__print_deriv()
126 
 
163 ira 127 
        # Check empty str
128 
        if self.strpos >= len(self.str):
167 ira 129 
            self.__replace_sym(SYM_EPRM, SYM_EMPTY)
163 ira 130 
            return True
131 
 
132 
        # Check +
133 
        if self.str[self.strpos] == '+':
134 
            self.strpos += 1
167 ira 135 
            self.__replace_sym(SYM_EPRM, '+' + SYM_T + SYM_EPRM)
163 ira 136 
            return self.procT() and self.procEprm()
137 
 
138 
        # Check -
139 
        if self.str[self.strpos] == '-':
140 
            self.strpos += 1
167 ira 141 
            self.__replace_sym(SYM_EPRM, '-' + SYM_T + SYM_EPRM)
163 ira 142 
            return self.procT() and self.procEprm()
143 
 
144 
        # We accept empty str, so take it
167 ira 145 
        self.__replace_sym(SYM_EPRM, SYM_EMPTY)
163 ira 146 
        return True
147 
 
162 ira 148 
    def procT(self):
167 ira 149 
        self.__print_deriv()
162 ira 150 
 
167 ira 151 
        self.__replace_sym(SYM_T, SYM_P + SYM_TPRM)
164 ira 152 
        return self.procP() and self.procTprm()
162 ira 153 
 
163 ira 154 
    def procTprm(self):
167 ira 155 
        self.__print_deriv()
156 
 
162 ira 157 
        # Check empty str
158 
        if self.strpos >= len(self.str):
167 ira 159 
            self.__replace_sym(SYM_TPRM, SYM_EMPTY)
162 ira 160 
            return True
161 
 
163 ira 162 
        # Check *
163 
        if self.str[self.strpos] == '*':
162 ira 164 
            self.strpos += 1
167 ira 165 
            self.__replace_sym(SYM_TPRM, '*' + SYM_P + SYM_TPRM)
164 ira 166 
            return self.procP() and self.procTprm()
162 ira 167 
 
163 ira 168 
        # we accept empty str, so take it
167 ira 169 
        self.__replace_sym(SYM_TPRM, SYM_EMPTY)
163 ira 170 
        return True
171 
 
164 ira 172 
    def procP(self):
167 ira 173 
        self.__print_deriv()
164 ira 174 
 
167 ira 175 
        self.__replace_sym(SYM_P, SYM_F + SYM_PPRM)
164 ira 176 
        return self.procF() and self.procPprm()
177 
 
178 
    def procPprm(self):
167 ira 179 
        self.__print_deriv()
180 
 
164 ira 181 
        # Check empty str
182 
        if self.strpos >= len(self.str):
167 ira 183 
            self.__replace_sym(SYM_PPRM, SYM_EMPTY)
164 ira 184 
            return True
185 
 
186 
        # check exp symbol
187 
        if self.str[self.strpos] == '^':
188 
            self.strpos += 1
167 ira 189 
            self.__replace_sym(SYM_PPRM, '^' + SYM_F + SYM_PPRM)
164 ira 190 
            return self.procF() and self.procPprm()
191 
 
192 
        # we accept empty str, so take it
167 ira 193 
        self.__replace_sym(SYM_PPRM, SYM_EMPTY)
164 ira 194 
        return True
195 
 
163 ira 196 
    def procF(self):
167 ira 197 
        self.__print_deriv()
163 ira 198 
 
199 
        # Check x
200 
        if self.str[self.strpos] == 'x':
201 
            self.strpos += 1
167 ira 202 
            self.__replace_sym(SYM_F, 'x' + SYM_V)
163 ira 203 
            return self.procV()
204 
 
205 
        # Check (E)
206 
        if self.str[self.strpos] == '(':
207 
            self.strpos += 1
167 ira 208 
            self.__replace_sym(SYM_F, '(' + SYM_E + ')')
163 ira 209 
 
210 
            if self.procE():
211 
                if self.str[self.strpos] == ')':
164 ira 212 
                    self.strpos += 1
163 ira 213 
                    return True
214 
 
164 ira 215 
                return False
216 
 
163 ira 217 
            return False
218 
 
219 
        # Must be a number
167 ira 220 
        self.__replace_sym(SYM_F, SYM_N)
163 ira 221 
        return self.procN()
222 
 
223 
    def procN(self):
167 ira 224 
        self.__print_deriv()
163 ira 225 
 
167 ira 226 
        nums = range(100) # get 0-99
227 
        nums.reverse()    # make it 99-0
228 
 
229 
        for n in nums:
230 
            if self.str[self.strpos:self.strpos+len(str(n))] == str(n):
231 
                self.strpos += len(str(n))
232 
                self.__replace_sym(SYM_N, str(n))
164 ira 233 
                return True
234 
 
162 ira 235 
        return False
167 ira 236 
 
163 ira 237 
    def procV(self):
167 ira 238 
        self.__print_deriv()
163 ira 239 
 
167 ira 240 
        if self.str[self.strpos] in '0123456789':
241 
            self.strpos += 1
242 
            self.__replace_sym(SYM_V, self.str[self.strpos-1])
243 
            return True
163 ira 244 
 
164 ira 245 
        return False
167 ira 246 
 
161 ira 247 
if __name__ == '__main__':
162 ira 248 
    rdp = RecursiveDescentParser()
249 
    rdp.main_menu()
161 ira 250