Subversion Repositories programming

Rev

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

Rev 142 Rev 143
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: 2005-10-24
5 
# License: Public Domain
 5 
# License: Public Domain
6 
#
 6 
#
7 
# Changelog Follows:
 7 
# Changelog Follows:
8 
# - 2005-10-16
 8 
# - 2005-10-16
9 
# - Implemented the nfa class. It's mostly complete at this point.
 9 
# - Implemented the nfa class. It's mostly complete at this point.
Line 21... Line 21...
21 
# - Commented the source more.
 21 
# - Commented the source more.
22 
#
 22 
#
23 
# - 2005-10-22
 23 
# - 2005-10-22
24 
# - Removed an unnecessary call in input_autmaton()
 24 
# - Removed an unnecessary call in input_autmaton()
25 
#
 25 
#
- 
 
 26 
# - 2005-10-24
- 
 
 27 
# - Realized that I need to call E(states) after I find out where I'm going.
- 
 
 28 
#   The program wasn't working at all before, now it is. See class notes from
- 
 
 29 
#   2005-10-24 for some examples that weren't working.
- 
 
 30 
# - Made 'True' and 'False' print correctly even if we are on pre-boolean
- 
 
 31 
#   version of python.
- 
 
 32 
# - Added a 'Verbose Mode' toggle to the menu. This makes the outputted DFA
- 
 
 33 
#   table have more information: the NFA Equiv. State
- 
 
 34 
# - It's ready to be turned in now :)
- 
 
 35 
#
26 
 
 36 
 
27 
################################################################################
 37 
################################################################################
28 
# IMPORTANT NOTES
 38 
# IMPORTANT NOTES
29 
################################################################################
 39 
################################################################################
30 
# The DFA table format:
 40 
# The DFA table format:
Line 52... Line 62...
52 
    """Implements a Non-Deterministic Finite Automaton"""
 62 
    """Implements a Non-Deterministic Finite Automaton"""
53 
 
 63 
 
54 
    def __init__(self):
 64 
    def __init__(self):
55 
        """Constructor for the nfa object"""
 65 
        """Constructor for the nfa object"""
56 
        self.__clear()
 66 
        self.__clear()
- 
 
 67 
        self.verbose = False
57 
 
 68 
 
58 
    def __clear(self):
 69 
    def __clear(self):
59 
        """Clear all instance variables of the nfa class"""
 70 
        """Clear all instance variables of the nfa class"""
60 
        self.trans_func = {}
 71 
        self.trans_func = {}
61 
        self.num_states = 0
 72 
        self.num_states = 0
Line 195... Line 206...
195 
        while not done:
 206 
        while not done:
196 
            print 'Menu:'
 207 
            print 'Menu:'
197 
            print '========================================'
 208 
            print '========================================'
198 
            print '1. Enter an NFA'
 209 
            print '1. Enter an NFA'
199 
            print '2. Output corresponding DFA'
 210 
            print '2. Output corresponding DFA'
- 
 
 211 
            print '3. %s Verbose Mode' % (self.verbose and 'Disable' or 'Enable', )
200 
            print '3. Quit'
 212 
            print '4. Quit'
201 
            print
 213 
            print
202 
            s = raw_input('Choice >>> ')
 214 
            s = raw_input('Choice >>> ')
203 
            print
 215 
            print
204 
 
 216 
 
205 
            if s == '1':
 217 
            if s == '1':
Line 212... Line 224...
212 
                    self.__output_dfa()
 224 
                    self.__output_dfa()
213 
                else:
 225 
                else:
214 
                    print 'Enter a NFA first'
 226 
                    print 'Enter a NFA first'
215 
                print
 227 
                print
216 
            elif s == '3':
 228 
            elif s == '3':
- 
 
 229 
                self.verbose = not self.verbose
- 
 
 230 
                print 'Verbose Mode %s' % (self.verbose and 'Enabled' or 'Disabled', )
- 
 
 231 
                print
- 
 
 232 
            elif s == '4':
217 
                done = True
 233 
                done = True
218 
            else:
 234 
            else:
219 
                print 'Bad Selection'
 235 
                print 'Bad Selection'
220 
                print
 236 
                print
221 
 
 237 
 
Line 230... Line 246...
230 
        print
 246 
        print
231 
 
 247 
 
232 
    def __print_dfa_table(self):
 248 
    def __print_dfa_table(self):
233 
        """Print out a nicely spaced representation of the DFA's table"""
 249 
        """Print out a nicely spaced representation of the DFA's table"""
234 
 
 250 
 
- 
 
 251 
        if self.verbose:
235 
        #header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv')
 252 
            header1 = '%-8s%-8s%-20s' % ('Final', 'Number', 'NFA Equiv. State')
- 
 
 253 
        else:
236 
        header1 = '%-8s%-8s' % ('Final', 'State #')
 254 
            header1 = '%-8s%-8s' % ('Final', 'State #')
- 
 
 255 
 
237 
        header2 = ''
 256 
        header2 = ''
238 
 
 257 
 
239 
        for l in self.possible_letters:
 258 
        for l in self.possible_letters:
240 
            header2 = '%s%-4s' % (header2, l)
 259 
            header2 = '%s%-4s' % (header2, l)
241 
 
 260 
 
Line 247... Line 266...
247 
 
 266 
 
248 
        print heading
 267 
        print heading
249 
        print hdr_line
 268 
        print hdr_line
250 
 
 269 
 
251 
        for rec in self.dfa_table:
 270 
        for rec in self.dfa_table:
- 
 
 271 
            if self.verbose:
252 
            #line1 = '%-8s%-8s%-20s' % (rec[0], rec[1], rec[2])
 272 
                line1 = '%-8s%-8s%-20s' % (rec[0] and 'True' or 'False', rec[1], rec[2])
- 
 
 273 
            else:
253 
            line1 = '%-8s%-8s' % (rec[0], rec[1])
 274 
                line1 = '%-8s%-8s' % (rec[0] and 'True' or 'False', rec[1])
- 
 
 275 
 
254 
            line2 = ''
 276 
            line2 = ''
255 
 
 277 
 
256 
            for l in range(len(self.possible_letters)):
 278 
            for l in range(len(self.possible_letters)):
257 
                line2 = '%s%-4s' % (line2, rec[l+3])
 279 
                line2 = '%s%-4s' % (line2, rec[l+3])
258 
 
 280 
 
Line 302... Line 324...
302 
                    if j not in storage:
 324 
                    if j not in storage:
303 
                        storage.append(j)
 325 
                        storage.append(j)
304 
 
 326 
 
305 
        return storage
 327 
        return storage
306 
 
 328 
 
307 
    def __by_letter(self, states, letter):
 - 
 
308 
        """Returns a list of states to where you can go from a group (list)
 - 
 
309 
        of states, with a certain letter"""
 - 
 
310 
 
 - 
 
311 
        from_states = []
 - 
 
312 
 
 - 
 
313 
        # Make sure E() has been called on every state here.
 - 
 
314 
        # It should have been already, but just to make sure,
 - 
 
315 
        # we'll do it here, too :)
 - 
 
316 
        for s in states:
 - 
 
317 
            from_states.extend(self.__E(s))
 - 
 
318 
 
 - 
 
319 
        from_states = self.__unique_sort(from_states)
 - 
 
320 
 
 - 
 
321 
        new_states = []
 - 
 
322 
 
 - 
 
323 
        # For each state, find the next states, and add them to the list
 - 
 
324 
        for s in from_states:
 - 
 
325 
            new_states.extend(self.__next_states(s, letter))
 - 
 
326 
 
 - 
 
327 
        new_states = self.__unique_sort(new_states)
 - 
 
328 
 
 - 
 
329 
        return new_states
 - 
 
330 
 
 - 
 
331 
    def __unique_sort(self, li):
 329 
    def __unique_sort(self, li):
332 
        """Make sure everything in a list is unique, and then sort it"""
 330 
        """Make sure everything in a list is unique, and then sort it"""
333 
 
 331 
 
334 
        newlist = []
 332 
        newlist = []
335 
 
 333 
 
Line 400... Line 398...
400 
 
 398 
 
401 
        # Get the NFA equivalent multi-state
 399 
        # Get the NFA equivalent multi-state
402 
        fromstates = self.dfa_table[record][2]
 400 
        fromstates = self.dfa_table[record][2]
403 
        tostates = []
 401 
        tostates = []
404 
 
 402 
 
405 
        # Find all the states we can go to from our multi-state
 403 
        # Find all the states we can go to from our multi-state.
- 
 
 404 
        # It is _EXTREMELY_ important that you call E(s) for every state that
- 
 
 405 
        # you can get to, otherwise you miss certain situations.
406 
        for s in fromstates:
 406 
        for from_s in fromstates:
407 
            tostates.extend(self.__next_states(s, self.possible_letters[letter_pos-3]))
 407 
            for next_s in self.__next_states(from_s, self.possible_letters[letter_pos-3]):
- 
 
 408 
                tostates.extend(self.__E(next_s))
408 
 
 409 
 
409 
        tostates = self.__unique_sort(tostates)
 410 
        tostates = self.__unique_sort(tostates)
410 
 
 411 
 
411 
        # Make the letter we are trying to resolve point to a record in the table.
 412 
        # Make the letter we are trying to resolve point to a record in the table.
412 
        # make_basic_record() will return the correct record, even if it needs to
 413 
        # make_basic_record() will return the correct record, even if it needs to