Subversion Repositories programming

Rev

Rev 167 | 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
172 ira 4 
# End Date: 2005-11-30
161 ira 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 
#
172 ira 20 
# 2005-11-29
21 
# * Add error checking to the input.
22 
# * Add comments to all of the methods.
23 
#
161 ira 24 
 
25 
# Check for <Python-2.3 compatibility (boolean values)
26 
try:
27 
  True, False
28 
except NameError:
29 
  (True, False) = (1, 0)
30 
 
162 ira 31 
import sys
163 ira 32 
 
167 ira 33 
# Default Symbols
172 ira 34 
SYM_E = "A" # "E"  --  These next few symbols were renamed to make
35 
SYM_T = "B" # "T"  --  output easier.
167 ira 36 
SYM_P = "C" # "P"
37 
SYM_F = "F"
38 
SYM_N = "N"
39 
SYM_V = "V"
40 
SYM_D = "D"
41 
SYM_EPRM = "E'"
42 
SYM_TPRM = "T'"
43 
SYM_PPRM = "P'"
44 
SYM_EMPTY = ""
164 ira 45 
 
162 ira 46 
class RecursiveDescentParser:
172 ira 47 
    """An implementation of a Recursive Descent Parser for a simple
48 
    algebraic language, with both variables and numbers."""
49 
 
161 ira 50 
    def __init__(self):
162 ira 51 
        self.__clear()
161 ira 52 
 
53 
    def __clear(self):
54 
        self.str = ""   # the string of input to test
55 
        self.strpos = 0 # the current position in str
172 ira 56 
        self.derivation = "" # the current state the grammar is in
161 ira 57 
 
166 ira 58 
    def __replace_sym(self, to_repl, with_this):
59 
        """Replace a string in the derivation with another string"""
60 
 
167 ira 61 
        pos = self.derivation.find(to_repl)
166 ira 62 
 
63 
        if pos == -1:
167 ira 64 
            #print 'str: %s' % (self.derivation, )
65 
            #print 'to_repl: %s' % (to_repl, )
66 
            #print 'with_this: %s' % (with_this, )
166 ira 67 
            raise ValueError
68 
 
167 ira 69 
        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]
166 ira 70 
 
161 ira 71 
    def __input_test_str(self):
172 ira 72 
        """Read a test string from the user"""
161 ira 73 
 
172 ira 74 
        while len(self.str) <= 0:
75 
            self.str = raw_input("input str: ")
76 
 
161 ira 77 
    def main_menu(self):
78 
 
79 
        done = False
80 
 
81 
        while not done:
82 
            print 'Menu:'
83 
            print '========================================'
84 
            print '1. Test a string'
85 
            print '2. Quit'
86 
            print
87 
            s = raw_input('Choice >>> ')
88 
            print
89 
 
90 
            if s == '1':
162 ira 91 
                self.__clear()
161 ira 92 
                self.__input_test_str()
93 
                self.__test_str()
94 
            elif s == '2':
95 
                done = True
96 
            else:
97 
                print 'Bad Selection'
98 
                print
99 
 
167 ira 100 
    def __print_deriv(self, with_arrow=True):
172 ira 101 
        """Print out the derivation as it is at this moment, either
102 
        with or without the arrow."""
103 
 
167 ira 104 
        if with_arrow:
105 
            print "%s ->" % (self.derivation, ),
106 
        else:
107 
            print "%s" % (self.derivation, )
108 
 
162 ira 109 
    def __test_str(self):
172 ira 110 
        """Run test.str through the parser"""
111 
 
112 
        self.derivation = SYM_E[:] # set the initial symbol: E
167 ira 113 
 
114 
        procE_ans = self.procE()
115 
        all_input_used = (len(self.str) == self.strpos)
116 
        ans = procE_ans and all_input_used
117 
 
118 
        self.__print_deriv(with_arrow=False)
163 ira 119 
        print
167 ira 120 
        print 'Parsing: %s' % (ans and 'Completed' or 'Failed', )
161 ira 121 
 
167 ira 122 
        if not ans:
123 
            print 'All input used: %s' % (all_input_used and 'True' or 'False', )
124 
 
125 
        print
126 
 
172 ira 127 
    ####
128 
    ####
129 
    #### NOTE: for all of the proc_X rules, see the grammar provided. They
130 
    #### explain what is going on, I think. These functions are just direct
131 
    #### implementations of the grammar.
132 
    ####
133 
    ####
134 
 
162 ira 135 
    def procE(self):
167 ira 136 
        self.__print_deriv()
163 ira 137 
 
164 ira 138 
        # Catch the exception generated below if we don't have enough
139 
        # input to 'look ahead'
140 
        try:
167 ira 141 
            self.__replace_sym(SYM_E, SYM_T + SYM_EPRM)
164 ira 142 
            return self.procT() and self.procEprm()
143 
        except IndexError:
144 
            print 'Not enough input to continue, failed.'
145 
            return False
162 ira 146 
 
163 ira 147 
    def procEprm(self):
167 ira 148 
        self.__print_deriv()
149 
 
163 ira 150 
        # Check empty str
151 
        if self.strpos >= len(self.str):
167 ira 152 
            self.__replace_sym(SYM_EPRM, SYM_EMPTY)
163 ira 153 
            return True
154 
 
155 
        # Check +
156 
        if self.str[self.strpos] == '+':
157 
            self.strpos += 1
167 ira 158 
            self.__replace_sym(SYM_EPRM, '+' + SYM_T + SYM_EPRM)
163 ira 159 
            return self.procT() and self.procEprm()
160 
 
161 
        # Check -
162 
        if self.str[self.strpos] == '-':
163 
            self.strpos += 1
167 ira 164 
            self.__replace_sym(SYM_EPRM, '-' + SYM_T + SYM_EPRM)
163 ira 165 
            return self.procT() and self.procEprm()
166 
 
167 
        # We accept empty str, so take it
167 ira 168 
        self.__replace_sym(SYM_EPRM, SYM_EMPTY)
163 ira 169 
        return True
170 
 
162 ira 171 
    def procT(self):
167 ira 172 
        self.__print_deriv()
162 ira 173 
 
167 ira 174 
        self.__replace_sym(SYM_T, SYM_P + SYM_TPRM)
164 ira 175 
        return self.procP() and self.procTprm()
162 ira 176 
 
163 ira 177 
    def procTprm(self):
167 ira 178 
        self.__print_deriv()
179 
 
162 ira 180 
        # Check empty str
181 
        if self.strpos >= len(self.str):
167 ira 182 
            self.__replace_sym(SYM_TPRM, SYM_EMPTY)
162 ira 183 
            return True
184 
 
163 ira 185 
        # Check *
186 
        if self.str[self.strpos] == '*':
162 ira 187 
            self.strpos += 1
167 ira 188 
            self.__replace_sym(SYM_TPRM, '*' + SYM_P + SYM_TPRM)
164 ira 189 
            return self.procP() and self.procTprm()
162 ira 190 
 
163 ira 191 
        # we accept empty str, so take it
167 ira 192 
        self.__replace_sym(SYM_TPRM, SYM_EMPTY)
163 ira 193 
        return True
194 
 
164 ira 195 
    def procP(self):
167 ira 196 
        self.__print_deriv()
164 ira 197 
 
167 ira 198 
        self.__replace_sym(SYM_P, SYM_F + SYM_PPRM)
164 ira 199 
        return self.procF() and self.procPprm()
200 
 
201 
    def procPprm(self):
167 ira 202 
        self.__print_deriv()
203 
 
164 ira 204 
        # Check empty str
205 
        if self.strpos >= len(self.str):
167 ira 206 
            self.__replace_sym(SYM_PPRM, SYM_EMPTY)
164 ira 207 
            return True
208 
 
209 
        # check exp symbol
210 
        if self.str[self.strpos] == '^':
211 
            self.strpos += 1
167 ira 212 
            self.__replace_sym(SYM_PPRM, '^' + SYM_F + SYM_PPRM)
164 ira 213 
            return self.procF() and self.procPprm()
214 
 
215 
        # we accept empty str, so take it
167 ira 216 
        self.__replace_sym(SYM_PPRM, SYM_EMPTY)
164 ira 217 
        return True
218 
 
163 ira 219 
    def procF(self):
167 ira 220 
        self.__print_deriv()
163 ira 221 
 
222 
        # Check x
223 
        if self.str[self.strpos] == 'x':
224 
            self.strpos += 1
167 ira 225 
            self.__replace_sym(SYM_F, 'x' + SYM_V)
163 ira 226 
            return self.procV()
227 
 
228 
        # Check (E)
229 
        if self.str[self.strpos] == '(':
230 
            self.strpos += 1
167 ira 231 
            self.__replace_sym(SYM_F, '(' + SYM_E + ')')
163 ira 232 
 
233 
            if self.procE():
234 
                if self.str[self.strpos] == ')':
164 ira 235 
                    self.strpos += 1
163 ira 236 
                    return True
237 
 
164 ira 238 
                return False
239 
 
163 ira 240 
            return False
241 
 
242 
        # Must be a number
167 ira 243 
        self.__replace_sym(SYM_F, SYM_N)
163 ira 244 
        return self.procN()
245 
 
246 
    def procN(self):
167 ira 247 
        self.__print_deriv()
163 ira 248 
 
167 ira 249 
        nums = range(100) # get 0-99
250 
        nums.reverse()    # make it 99-0
251 
 
252 
        for n in nums:
253 
            if self.str[self.strpos:self.strpos+len(str(n))] == str(n):
254 
                self.strpos += len(str(n))
255 
                self.__replace_sym(SYM_N, str(n))
164 ira 256 
                return True
257 
 
162 ira 258 
        return False
167 ira 259 
 
163 ira 260 
    def procV(self):
167 ira 261 
        self.__print_deriv()
163 ira 262 
 
167 ira 263 
        if self.str[self.strpos] in '0123456789':
264 
            self.strpos += 1
265 
            self.__replace_sym(SYM_V, self.str[self.strpos-1])
266 
            return True
163 ira 267 
 
164 ira 268 
        return False
167 ira 269 
 
161 ira 270 
if __name__ == '__main__':
162 ira 271 
    rdp = RecursiveDescentParser()
272 
    rdp.main_menu()
161 ira 273