fsa_recognizer.class_fsa

1 """ 2 Classes used by class-based implementations of various kinds of finite state 3 recognizer. 4 5 This module introduces the classes fsa and fsa_recognizer. 6 Instances of fsa compute their alphabet and check 7 their transition tables for consistency at initialization 8 time. 9 10 Trace-printing and print methods are provided for both classes, 11 with print methods supplied via C{__repr__}. 12 """ 13 14 import sets, types 15 16 ## X= sets.set([]) 17 ## >>> employees = engineers | programmers | managers # union 18 ## >>> engineering_management = engineers & managers # intersection 19 ## >>> fulltime_management = managers - engineers - programmers # difference 20 ## >>> engineers.add('Marvin') # add element 21 ## >>> print engineers 22 ## Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack']) 23 ## >>> employees.issuperset(engineers) # superset test 24 ## False 25 ## >>> employees.union_update(engineers) # update from another set 26 ## >>> employees.issuperset(engineers) 27 ## True 28

29 -class fsa:

30

31 - def __init__(self,transitions,finals,initial=0):

32 """ 33 @parameter transitions: a list of dictionaries, one for each state 34 @type transitions: list 35 @parameter finals: a set of final states 36 @type finals: a set of int 37 @parameter initial: initial state 38 @type initial: int 39 """ 40 self.transitions = transitions 41 self.finals=sets.Set([]) 42 self.finals.union_update(finals) 43 self.initial = initial 44 self.check_finals_and_initial() 45 self.alphabet=sets.Set([]) 46 self.compute_alphabet()

47

48 - def compute_alphabet(self):

49 """ 50 Loop through states collecting all symbols 51 with transitions defined for them. 52 53 Update self.alphabet. 54 """ 55 transitions = self.transitions 56 for state in range(len(transitions)): 57 state_transit_table = transitions[state] 58 for key in state_transit_table: 59 self.alphabet.add(key)

60

61 - def add_to_alphabet(self,new_symbol_set):

62 """ 63 Union in new_symbol_set to current alphabet. 64 65 @parameter new_symbol_set: a set of new symbols to be added to malphabet 66 @type new_symbol_set: a set 67 """ 68 self.alphabet.union_update(new_symbol_set) 69 ## Probably unnecessary 70 self.compute_alphabet()

71

72 - def minimize_alphabet(self):

73 """ 74 Recompute alphabet.to be only those symbols with defined transitions. 75 """ 76 self.alphabet=sets.Set([]) 77 self.compute_alphabet()

78

79 - def check_finals_and_initial (self):

80 """ 81 Return True if both C{initial} and C{finals} are 82 valid states for the machine. Else False. 83 84 @rtype: Boolean 85 """ 86 num_states = len(self.transitions) 87 if isinstance(self.initial,types.IntType) and self.initial < num_states: 88 initial_ok = True 89 else: 90 initial_ok = False 91 print 'Initial state %s is not an integer less than the number of states %s' % (self.initial, num_states) 92 finals_ok = True 93 for state in self.finals: 94 if isinstance(state,types.IntType) and self.initial < num_states: 95 continue 96 else: 97 finals_ok = False 98 print 'final state %s is not an integer less than the number of states %s' % (state, num_states) 99 return initial_ok and finals_ok

100

101 - def add_finals(self,finals):

102 """ 103 @parameter finals: a set of final states 104 @type finals: a set of integers 105 """ 106 self.finals=sets.Set([]) 107 self.finals.union_update(finals)

108

109 - def __repr__ (self, indent=0):

110 """ 111 Returns a string Python uses for various puproses. 112 For example, to print. 113 """ 114 first_spaces = ' ' * indent 115 spaces = ' ' * (indent + 2) 116 strn = first_spaces + '{%s \n' % (self.__class__.__name__,) 117 for index in range(len(self.transitions)): 118 strn += (spaces +"%s:" % index) 119 if index == self.initial: 120 strn += " initial state" 121 if index in self.finals: 122 strn += " final state" 123 strn += "\n" 124 for key in self.transitions[index]: 125 val = self.transitions[index][key] 126 if val <> self.undefined_value(): 127 strn += (spaces +" %s => %s\n" % (key,val)) 128 return strn + first_spaces + '}'

129

130 - def undefined_value (self):

131 return 'und'

132

133 -class fsa_recognizer:

134 """ 135 Class for finite-state recognizers. 136 137 Each fsa_recognizer instance has an fsa stored 138 in self.fsa, which must be supplied at initialization time. 139 140 The recognize method defined here is just a stub for recognize 141 methods that must be defined for the various subclasses 142 of fsa_recognizer. Such stubs are sometimes called 143 abstract methods. 144 """ 145

146 - def __init__(self,fsa,trace=False):

147 """ 148 @parameter fsa: The fsa to be used for recognizing 149 @parameter trace: If True, gives verbose output on recognizing 150 @type trace: Boolean 151 """ 152 self.fsa = fsa 153 self.transitions = fsa.transitions 154 self.finals = fsa.finals 155 self.initial = fsa.initial 156 self.fsa.check_finals_and_initial() 157 self.fsa.compute_alphabet() 158 self.alphabet = fsa.alphabet 159 self.__trace__ = trace

160

161 - def recognize(self, string):

162 """Abstract class method, implemented by each subclass.""" 163 164 print 'recognize is an abstract method not implemented for class fsa_recognizer'

165

166 - def __repr__(self):

167 """ 168 Each class instance should report the most 169 specific class it belongs to on printing. 170 171 Each shd print out its fsa. 172 """ 173 strn = '[%s \n' % (self.__class__.__name__,) 174 return strn + self.fsa.__repr__(2) + ']'

175

176 - def not_in_alphabet_message (self,obs):

177 if self.__trace__: 178 print ' %s not in input alphabet' % obs

179

180 - def state_not_defined_for_message (self,state, obs):

181 if self.__trace__: 182 print ' State %s not defined for %s' % (state, obs)

183

184 - def non_final_state_message (self,state):

185 if self.__trace__: 186 print ' Ending in non-final state %s' % state

187

188 - def trace(self,value=True):

189 self.__trace__ = value

190

Source Code for Module fsa_recognizer.class_fsa_recognize