Subversion Repositories programming

Rev

Rev 130 | Rev 135 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 130 Rev 131
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-10-08
 3 
# Start Date: 2005-10-08
4 
# End Date:
4 
# End Date:
5 
# License: Public Domain
 5 
# License: Public Domain
6 
#
 6 
#
7 
# Changelog Follows:
 7 
# Changelog Follows:
- 
 
 8 
# - 2005-10-16
- 
 
 9 
# - Implemented the nfa class. It's mostly complete at this point.
- 
 
 10 
# - E() function works for circular loops now.
- 
 
 11 
# - Made the nfa.__next_states() function always return a valid reference
- 
 
 12 
#   to a list in the dictionary. This means you should NEVER use
- 
 
 13 
#   self.trans_func[(state, letter)] in code anywhere now :)
- 
 
 14 
# - Final states are now checked for validity.
8 
#
 15 
#
9 
 
 16 
 
10 
################################################################################
 17 
################################################################################
11 
# IMPORTANT NOTES
 18 
# IMPORTANT NOTES
12 
################################################################################
 19 
################################################################################
Line 20... Line 27...
20 
    def __init__(self):
 27 
    def __init__(self):
21 
        self.trans_func = {}
 28 
        self.trans_func = {}
22 
        self.num_states = 0
 29 
        self.num_states = 0
23 
        self.final_states = []
 30 
        self.final_states = []
24 
        self.initial_state = 0
 31 
        self.initial_state = 0
25
32 
 
26 
    def __state_in_range(self, state):
 33 
    def __state_in_range(self, state):
27 
        """Check if a given state is in the acceptable range"""
 34 
        """Check if a given state is in the acceptable range"""
28 
 
 35 
 
29 
        try:
 36 
        try:
30 
            temp = int(state)
 37 
            temp = int(state)
Line 33... Line 40...
33 
 
 40 
 
34 
        if temp >= 0 and temp < self.num_states:
 41 
        if temp >= 0 and temp < self.num_states:
35 
            return True
 42 
            return True
36 
 
 43 
 
37 
        return False
 44 
        return False
38
45 
 
39 
    def __input_num_states(self):
 46 
    def __input_num_states(self):
40 
        """Get the number of states this automaton will have"""
 47 
        """Get the number of states this automaton will have"""
41 
 
 48 
 
42 
        done = False
 49 
        done = False
43 
        while not done:
 50 
        while not done:
Line 52... Line 59...
52 
 
 59 
 
53 
    def __input_final_states(self):
 60 
    def __input_final_states(self):
54 
        """Get final states for this automaton"""
 61 
        """Get final states for this automaton"""
55 
 
 62 
 
56 
        print 'Enter final states on one line, seperated by spaces'
 63 
        print 'Enter final states on one line, seperated by spaces'
57
64 
 
58 
        done = False
 65 
        done = False
59 
        while not done:
 66 
        while not done:
60 
            final_states = raw_input('Final states: ')
 67 
            final_states = raw_input('Final states: ')
61
68 
 
62 
            bad_data = False
 69 
            bad_data = False
63 
            for i in final_states.split():
 70 
            for i in final_states.split():
64 
                if not self.__state_in_range(i):
 71 
                if not self.__state_in_range(i):
65 
                    print 'State %s out of range. All input discarded.' % (i, )
 72 
                    print 'State %s out of range. All input discarded.' % (i, )
66 
                    print 'Try again please'
 73 
                    print 'Try again please'
Line 72... Line 79...
72 
            if bad_data:
 79 
            if bad_data:
73 
                continue
 80 
                continue
74 
 
 81 
 
75 
            # all data is good
 82 
            # all data is good
76 
            for i in final_states.split():
 83 
            for i in final_states.split():
- 
 
 84 
                if self.__state_in_range(i):
77 
                self.final_states.append(int(i))
 85 
                    self.final_states.append(int(i))
78 
 
 86 
 
79 
            done = True
 87 
            done = True
80 
 
 88 
 
81 
    def __input_all_edges(self):
 89 
    def __input_all_edges(self):
82 
        """Read all of the edges for this automaton"""
 90 
        """Read all of the edges for this automaton"""
Line 94... Line 102...
94 
            edge = raw_input('Edge: ')
 102 
            edge = raw_input('Edge: ')
95 
 
 103 
 
96 
            if len(edge) == 0:
 104 
            if len(edge) == 0:
97 
                done = True
 105 
                done = True
98 
                continue
 106 
                continue
99
107 
 
100 
            if len(edge.split()) != 3:
 108 
            if len(edge.split()) != 3:
101 
                print 'Bad edge entered'
 109 
                print 'Bad edge entered'
102 
                print
 110 
                print
103 
                continue
 111 
                continue
104
- 
 
- 
 
 112 
 
105 
            (cur_st, letter, next_st) = edge.split()
 113 
            (cur_st, letter, next_st) = edge.split()
106 
 
 114 
 
- 
 
 115 
            # Make sure the states entered are in range
107 
            if self.__state_in_range(cur_st) and self.__state_in_range(next_st):
 116 
            if self.__state_in_range(cur_st) and self.__state_in_range(next_st):
108 
                new_state = False
 117 
                new_state = False
- 
 
 118 
                cur_st = int(cur_st)
- 
 
 119 
                next_st = int(next_st)
109 
 
 120 
 
110 
                try:
 - 
 
111 
                    self.trans_func[(int(cur_st), letter)]
 121 
                # Add the state to the list if it's not there already
112 
                except KeyError:
 - 
 
113 
                    new_state = True
 - 
 
114 
 
 - 
 
115 
                if new_state:
 - 
 
116 
                    self.trans_func[(int(cur_st), letter)] = [int(next_st)]
 122 
                if next_st not in self.__next_states(cur_st, letter):
117 
                else:
 - 
 
118 
                    self.trans_func[(int(cur_st), letter)].append(int(next_st))
 123 
                    self.__next_states(cur_st, letter).append(next_st)
119 
 
 124 
 
120 
            else:
 125 
            else:
121 
                print 'Invalid current or next state entered'
 126 
                print 'Invalid current or next state entered'
122 
                print
 127 
                print
123 
                continue
 128 
                continue
124
- 
 
- 
 
 129 
 
125 
    def __input_automaton(self):
 130 
    def __input_automaton(self):
126 
        """Read this entire automaton's input"""
 131 
        """Read this entire automaton's input"""
127 
 
 132 
 
128 
        self.__input_num_states()
 133 
        self.__input_num_states()
129 
        self.__input_final_states()
 134 
        self.__input_final_states()
130 
        self.__input_all_edges()
 135 
        self.__input_all_edges()
131 
 
 136 
 
132 
    def main_menu(self):
 137 
    def main_menu(self):
- 
 
 138 
        #NOTE: All of this code is not what it's supposed to be.
- 
 
 139 
        #      It is for TESTING ONLY.
- 
 
 140 
        #
- 
 
 141 
        #TODO: Generate a menu :)
- 
 
 142 
 
133 
        self.__input_automaton()
 143 
        self.__input_automaton()
134 
 
 144 
 
135 
        print self.trans_func
 145 
        print self.trans_func
136 
        print self.num_states
 146 
        print self.num_states
137 
        print self.final_states
 147 
        print self.final_states
138 
        print self.initial_state
 148 
        print self.initial_state
- 
 
 149 
        print
- 
 
 150 
 
139 
        print 'E(0): %s' % (self.__E(0), )
 151 
        for i in range(self.num_states):
140 
        print 'E(1): %s' % (self.__E(1), )
 152 
            print 'E(%d): %s' % (i, self.__E(i))
141 
 
 153 
 
142 
    def __next_states(self, state, letter):
 154 
    def __next_states(self, state, letter):
143 
        next = []
 155 
        """Return the next states for the key (state, letter)"""
144
156 
 
145 
        try:
 157 
        try:
146 
            next = self.trans_func[(state, letter)]
 158 
            next = self.trans_func[(state, letter)]
147 
        except KeyError:
 159 
        except KeyError:
- 
 
 160 
            # Create a new empty list for this state if it doesn't exist yet
- 
 
 161 
            next = self.trans_func[(state, letter)] = []
- 
 
 162 
 
- 
 
 163 
        if letter == '^' and state not in next:
148 
            pass
 164 
            next.append(state)
149 
 
 165 
 
150 
        return next
 166 
        return next
151
167 
 
152 
    def __E(self, state, storage=[], visited=[]):
 168 
    def __E(self, state, storage=None, visited=None):
- 
 
 169 
        """Calculate E(state) and return it. This handles circular E()
153
170 
        calculations."""
- 
 
 171 
 
154 
        # If nothing was inputted for the null string from this state
 172 
        # Work around weird mutable default argument stuff
155 
        # return itself only (as a list)
 173 
        if storage is None:
156 
        if len(self.__next_states(state, '^')) == 0:
 174 
            storage = []
- 
 
 175 
 
157 
            print 'stop rec: %s' % ([state], )
 176 
        # Work around weird mutable default argument stuff
158 
            return [state]
 177 
        if visited is None:
159
178 
            visited = []
- 
 
 179 
 
- 
 
 180 
        # Find all of the direct next states that we can get to by
- 
 
 181 
        # the empty string, and append anything that is not already there
160 
        for i in self.__next_states(state, '^'):
 182 
        for i in self.__next_states(state, '^'):
- 
 
 183 
            if i not in storage:
161 
            print 'next state: %s -- storage: %s -- visited: %s' % (i, storage, visited)
 184 
                storage.append(i)
162 
 
 185 
 
163 
            if i not in storage and i not in visited:
 186 
        # Visit everything in storage that has not been visited already
- 
 
 187 
        for i in storage:
164 
                storage.append(state) #add yourself to the list
 188 
            if i not in visited:
165 
                visited.append(i)
 189 
                visited.append(i)
166 
                print 'making the call: (%s, %s, %s)' % (i, storage, visited)
 190 
                temp = self.__E(i, storage, visited)
- 
 
 191 
 
167 
                storage.extend(self.__E(i, storage, visited))
 192 
                # Avoid duplicating things in storage
- 
 
 193 
                for j in temp:
- 
 
 194 
                    if j not in storage:
- 
 
 195 
                        storage.append(j)
168 
 
 196 
 
169 
        return storage
 197 
        return storage
170
198 
 
171 
    def output_dfa(self):
 199 
    def output_dfa(self):
172 
        #stuff here
 200 
        #stuff here
173 
        pass
 201 
        pass
174 
 
 202 
 
175 
if __name__ == '__main__':
 203 
if __name__ == '__main__':