Subversion Repositories programming

Rev

Rev 167 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 167 Rev 172
Line 1... Line 1...
1 
#!/usr/bin/env python
 1 
#!/usr/bin/env python
2 
# Copyright: Ira W. Snyder
 2 
# Copyright: Ira W. Snyder
3 
# Start Date: 2005-11-18
 3 
# Start Date: 2005-11-18
4 
# End Date:
 4 
# End Date: 2005-11-30
5 
# License: Public Domain
 5 
# License: Public Domain
6 
#
 6 
#
7 
# Changelog Follows:
 7 
# Changelog Follows:
8 
#
 8 
#
9 
# 2005-11-18
 9 
# 2005-11-18
Line 15... Line 15...
15 
#
 15 
#
16 
# 2005-11-28
 16 
# 2005-11-28
17 
# * This has pretty-printing now. (The derivation looks correct)
 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.
 18 
# * Needs testing still, but for every case I can come up with, it works.
19 
#
 19 
#
- 
 
 20 
# 2005-11-29
- 
 
 21 
# * Add error checking to the input.
- 
 
 22 
# * Add comments to all of the methods.
- 
 
 23 
#
20 
 
 24 
 
21 
# Check for <Python-2.3 compatibility (boolean values)
 25 
# Check for <Python-2.3 compatibility (boolean values)
22 
try:
 26 
try:
23 
  True, False
 27 
  True, False
24 
except NameError:
 28 
except NameError:
25 
  (True, False) = (1, 0)
 29 
  (True, False) = (1, 0)
26 
 
 30 
 
27 
import sys
 31 
import sys
28 
 
 32 
 
29 
# Default Symbols
 33 
# Default Symbols
30 
SYM_E = "A" # "E"
 34 
SYM_E = "A" # "E"  --  These next few symbols were renamed to make
31 
SYM_T = "B" # "T"
 35 
SYM_T = "B" # "T"  --  output easier.
32 
SYM_P = "C" # "P"
 36 
SYM_P = "C" # "P"
33 
SYM_F = "F"
 37 
SYM_F = "F"
34 
SYM_N = "N"
 38 
SYM_N = "N"
35 
SYM_V = "V"
 39 
SYM_V = "V"
36 
SYM_D = "D"
 40 
SYM_D = "D"
Line 38... Line 42...
38 
SYM_TPRM = "T'"
 42 
SYM_TPRM = "T'"
39 
SYM_PPRM = "P'"
 43 
SYM_PPRM = "P'"
40 
SYM_EMPTY = ""
 44 
SYM_EMPTY = ""
41 
 
 45 
 
42 
class RecursiveDescentParser:
 46 
class RecursiveDescentParser:
- 
 
 47 
    """An implementation of a Recursive Descent Parser for a simple
- 
 
 48 
    algebraic language, with both variables and numbers."""
- 
 
 49
43 
    def __init__(self):
 50 
    def __init__(self):
44 
        self.__clear()
 51 
        self.__clear()
45 
 
 52 
 
46 
    def __clear(self):
 53 
    def __clear(self):
47 
        self.str = ""   # the string of input to test
 54 
        self.str = ""   # the string of input to test
48 
        self.strpos = 0 # the current position in str
 55 
        self.strpos = 0 # the current position in str
49 
        self.derivation = ""
 56 
        self.derivation = "" # the current state the grammar is in
50 
 
 57 
 
51 
    def __replace_sym(self, to_repl, with_this):
 58 
    def __replace_sym(self, to_repl, with_this):
52 
        """Replace a string in the derivation with another string"""
 59 
        """Replace a string in the derivation with another string"""
53 
 
 60 
 
54 
        pos = self.derivation.find(to_repl)
 61 
        pos = self.derivation.find(to_repl)
Line 60... Line 67...
60 
            raise ValueError
 67 
            raise ValueError
61
68
62 
        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]
 69 
        self.derivation = self.derivation[:pos] + str(with_this) + self.derivation[pos+len(to_repl):]
63 
 
 70 
 
64 
    def __input_test_str(self):
 71 
    def __input_test_str(self):
- 
 
 72 
        """Read a test string from the user"""
- 
 
 73 
 
- 
 
 74 
        while len(self.str) <= 0:
65 
        self.str = raw_input("input str: ")
 75 
            self.str = raw_input("input str: ")
66 
 
 76 
 
67 
    def main_menu(self):
 77 
    def main_menu(self):
68 
 
 78 
 
69 
        done = False
 79 
        done = False
70 
 
 80 
 
Line 86... Line 96...
86 
            else:
 96 
            else:
87 
                print 'Bad Selection'
 97 
                print 'Bad Selection'
88 
                print
 98 
                print
89 
 
 99 
 
90 
    def __print_deriv(self, with_arrow=True):
 100 
    def __print_deriv(self, with_arrow=True):
- 
 
 101 
        """Print out the derivation as it is at this moment, either
- 
 
 102 
        with or without the arrow."""
- 
 
 103 
 
91 
        if with_arrow:
 104 
        if with_arrow:
92 
            print "%s ->" % (self.derivation, ),
 105 
            print "%s ->" % (self.derivation, ),
93 
        else:
 106 
        else:
94 
            print "%s" % (self.derivation, )
 107 
            print "%s" % (self.derivation, )
95
108
96 
    def __test_str(self):
 109 
    def __test_str(self):
- 
 
 110 
        """Run test.str through the parser"""
- 
 
 111 
 
97 
        self.derivation = SYM_E[:]
 112 
        self.derivation = SYM_E[:] # set the initial symbol: E
98
113
99 
        procE_ans = self.procE()
 114 
        procE_ans = self.procE()
100 
        all_input_used = (len(self.str) == self.strpos)
 115 
        all_input_used = (len(self.str) == self.strpos)
101 
        ans = procE_ans and all_input_used
 116 
        ans = procE_ans and all_input_used
102 
 
 117 
 
Line 107... Line 122...
107 
        if not ans:
 122 
        if not ans:
108 
            print 'All input used: %s' % (all_input_used and 'True' or 'False', )
 123 
            print 'All input used: %s' % (all_input_used and 'True' or 'False', )
109 
 
 124 
 
110 
        print
 125 
        print
111 
 
 126 
 
- 
 
 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
112 
    def procE(self):
 135 
    def procE(self):
113 
        self.__print_deriv()
 136 
        self.__print_deriv()
114 
 
 137 
 
115 
        # Catch the exception generated below if we don't have enough
 138 
        # Catch the exception generated below if we don't have enough
116 
        # input to 'look ahead'
 139 
        # input to 'look ahead'