2 <!doctype html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
3 <html><head><title>Python: module FSM</title>
4 </head><body bgcolor="#f0f0f8">
6 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
8 <td valign=bottom> <br>
9 <font color="#ffffff" face="helvetica, arial"> <br><big><big><strong>FSM</strong></big></big></font></td
10 ><td align=right valign=bottom
11 ><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/noah/pexpect/trunk/pexpect/FSM.py">/home/noah/pexpect/trunk/pexpect/FSM.py</a></font></td></tr></table>
12 <p><tt>This module implements a Finite State Machine (<a href="#FSM">FSM</a>). In addition to state<br>
13 this <a href="#FSM">FSM</a> also maintains a user defined "memory". So this <a href="#FSM">FSM</a> can be used as a<br>
14 Push-down Automata (PDA) since a PDA is a <a href="#FSM">FSM</a> + memory.<br>
16 The following describes how the <a href="#FSM">FSM</a> works, but you will probably also need to<br>
17 see the example function to understand how the <a href="#FSM">FSM</a> is used in practice.<br>
19 You define an <a href="#FSM">FSM</a> by building tables of transitions. For a given input symbol<br>
20 the process() method uses these tables to decide what action to call and what<br>
21 the next state will be. The <a href="#FSM">FSM</a> has a table of transitions that associate:<br>
23 (input_symbol, current_state) --> (action, next_state)<br>
25 Where "action" is a function you define. The symbols and states can be any<br>
26 objects. You use the add_transition() and add_transition_list() methods to add<br>
27 to the transition table. The <a href="#FSM">FSM</a> also has a table of transitions that<br>
30 (current_state) --> (action, next_state)<br>
32 You use the add_transition_any() method to add to this transition table. The<br>
33 <a href="#FSM">FSM</a> also has one default transition that is not associated with any specific<br>
34 input_symbol or state. You use the set_default_transition() method to set the<br>
35 default transition.<br>
37 When an action function is called it is passed a reference to the <a href="#FSM">FSM</a>. The<br>
38 action function may then access attributes of the <a href="#FSM">FSM</a> such as input_symbol,<br>
39 current_state, or "memory". The "memory" attribute can be any object that you<br>
40 want to pass along to the action functions. It is not used by the <a href="#FSM">FSM</a> itself.<br>
41 For parsing you would typically pass a list to be used as a stack.<br>
43 The processing sequence is as follows. The process() method is given an<br>
44 input_symbol to process. The <a href="#FSM">FSM</a> will search the table of transitions that<br>
47 (input_symbol, current_state) --> (action, next_state)<br>
49 If the pair (input_symbol, current_state) is found then process() will call the<br>
50 associated action function and then set the current state to the next_state.<br>
52 If the <a href="#FSM">FSM</a> cannot find a match for (input_symbol, current_state) it will then<br>
53 search the table of transitions that associate:<br>
55 (current_state) --> (action, next_state)<br>
57 If the current_state is found then the process() method will call the<br>
58 associated action function and then set the current state to the next_state.<br>
59 Notice that this table lacks an input_symbol. It lets you define transitions<br>
60 for a current_state and ANY input_symbol. Hence, it is called the "any" table.<br>
61 Remember, it is always checked after first searching the table for a specific<br>
62 (input_symbol, current_state).<br>
64 For the case where the <a href="#FSM">FSM</a> did not match either of the previous two cases the<br>
65 <a href="#FSM">FSM</a> will try to use the default transition. If the default transition is<br>
66 defined then the process() method will call the associated action function and<br>
67 then set the current state to the next_state. This lets you define a default<br>
68 transition as a catch-all case. You can think of it as an exception handler.<br>
69 There can be only one default transition.<br>
71 Finally, if none of the previous cases are defined for an input_symbol and<br>
72 current_state then the <a href="#FSM">FSM</a> will raise an exception. This may be desirable, but<br>
73 you can always prevent this just by defining a default transition.<br>
75 Noah Spurrier 20020822</tt></p>
77 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
78 <tr bgcolor="#aa55cc">
79 <td colspan=3 valign=bottom> <br>
80 <font color="#fffff" face="helvetica, arial"><big><strong>Modules</strong></big></font></td></tr>
82 <tr><td bgcolor="#aa55cc"><tt> </tt></td><td> </td>
83 <td width="100%"><table width="100%" summary="list"><tr><td width="25%" valign=top><a href="optparse.html">optparse</a><br>
84 <a href="os.html">os</a><br>
85 </td><td width="25%" valign=top><a href="string.html">string</a><br>
86 <a href="sys.html">sys</a><br>
87 </td><td width="25%" valign=top><a href="time.html">time</a><br>
88 <a href="traceback.html">traceback</a><br>
89 </td><td width="25%" valign=top></td></tr></table></td></tr></table><p>
90 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
91 <tr bgcolor="#ee77aa">
92 <td colspan=3 valign=bottom> <br>
93 <font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
95 <tr><td bgcolor="#ee77aa"><tt> </tt></td><td> </td>
97 <dt><font face="helvetica, arial"><a href="FSM.html#FSM">FSM</a>
98 </font></dt><dt><font face="helvetica, arial"><a href="exceptions.html#Exception">exceptions.Exception</a>(<a href="exceptions.html#BaseException">exceptions.BaseException</a>)
101 <dt><font face="helvetica, arial"><a href="FSM.html#ExceptionFSM">ExceptionFSM</a>
106 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
107 <tr bgcolor="#ffc8d8">
108 <td colspan=3 valign=bottom> <br>
109 <font color="#000000" face="helvetica, arial"><a name="ExceptionFSM">class <strong>ExceptionFSM</strong></a>(<a href="exceptions.html#Exception">exceptions.Exception</a>)</font></td></tr>
111 <tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
112 <td colspan=2><tt>This is the <a href="#FSM">FSM</a> <a href="exceptions.html#Exception">Exception</a> class.<br> </tt></td></tr>
114 <td width="100%"><dl><dt>Method resolution order:</dt>
115 <dd><a href="FSM.html#ExceptionFSM">ExceptionFSM</a></dd>
116 <dd><a href="exceptions.html#Exception">exceptions.Exception</a></dd>
117 <dd><a href="exceptions.html#BaseException">exceptions.BaseException</a></dd>
118 <dd><a href="__builtin__.html#object">__builtin__.object</a></dd>
121 Methods defined here:<br>
122 <dl><dt><a name="ExceptionFSM-__init__"><strong>__init__</strong></a>(self, value)</dt></dl>
124 <dl><dt><a name="ExceptionFSM-__str__"><strong>__str__</strong></a>(self)</dt></dl>
127 Data descriptors defined here:<br>
128 <dl><dt><strong>__weakref__</strong></dt>
129 <dd><tt>list of weak references to the object (if defined)</tt></dd>
132 Data and other attributes inherited from <a href="exceptions.html#Exception">exceptions.Exception</a>:<br>
133 <dl><dt><strong>__new__</strong> = <built-in method __new__ of type object at 0x81400e0><dd><tt>T.<a href="#ExceptionFSM-__new__">__new__</a>(S, ...) -> a new object with type S, a subtype of T</tt></dl>
136 Methods inherited from <a href="exceptions.html#BaseException">exceptions.BaseException</a>:<br>
137 <dl><dt><a name="ExceptionFSM-__delattr__"><strong>__delattr__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__delattr__">__delattr__</a>('name') <==> del x.name</tt></dd></dl>
139 <dl><dt><a name="ExceptionFSM-__getattribute__"><strong>__getattribute__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__getattribute__">__getattribute__</a>('name') <==> x.name</tt></dd></dl>
141 <dl><dt><a name="ExceptionFSM-__getitem__"><strong>__getitem__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__getitem__">__getitem__</a>(y) <==> x[y]</tt></dd></dl>
143 <dl><dt><a name="ExceptionFSM-__getslice__"><strong>__getslice__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__getslice__">__getslice__</a>(i, j) <==> x[i:j]<br>
145 Use of negative indices is not supported.</tt></dd></dl>
147 <dl><dt><a name="ExceptionFSM-__reduce__"><strong>__reduce__</strong></a>(...)</dt></dl>
149 <dl><dt><a name="ExceptionFSM-__repr__"><strong>__repr__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__repr__">__repr__</a>() <==> repr(x)</tt></dd></dl>
151 <dl><dt><a name="ExceptionFSM-__setattr__"><strong>__setattr__</strong></a>(...)</dt><dd><tt>x.<a href="#ExceptionFSM-__setattr__">__setattr__</a>('name', value) <==> x.name = value</tt></dd></dl>
153 <dl><dt><a name="ExceptionFSM-__setstate__"><strong>__setstate__</strong></a>(...)</dt></dl>
156 Data descriptors inherited from <a href="exceptions.html#BaseException">exceptions.BaseException</a>:<br>
157 <dl><dt><strong>__dict__</strong></dt>
159 <dl><dt><strong>args</strong></dt>
161 <dl><dt><strong>message</strong></dt>
162 <dd><tt>exception message</tt></dd>
164 </td></tr></table> <p>
165 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
166 <tr bgcolor="#ffc8d8">
167 <td colspan=3 valign=bottom> <br>
168 <font color="#000000" face="helvetica, arial"><a name="FSM">class <strong>FSM</strong></a></font></td></tr>
170 <tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
171 <td colspan=2><tt>This is a Finite State Machine (<a href="#FSM">FSM</a>).<br> </tt></td></tr>
173 <td width="100%">Methods defined here:<br>
174 <dl><dt><a name="FSM-__init__"><strong>__init__</strong></a>(self, initial_state, memory<font color="#909090">=None</font>)</dt><dd><tt>This creates the <a href="#FSM">FSM</a>. You set the initial state here. The "memory"<br>
175 attribute is any object that you want to pass along to the action<br>
176 functions. It is not used by the <a href="#FSM">FSM</a>. For parsing you would typically<br>
177 pass a list to be used as a stack.</tt></dd></dl>
179 <dl><dt><a name="FSM-add_transition"><strong>add_transition</strong></a>(self, input_symbol, state, action<font color="#909090">=None</font>, next_state<font color="#909090">=None</font>)</dt><dd><tt>This adds a transition that associates:<br>
181 (input_symbol, current_state) --> (action, next_state)<br>
183 The action may be set to None in which case the <a href="#FSM-process">process</a>() method will<br>
184 ignore the action and only set the next_state. The next_state may be<br>
185 set to None in which case the current state will be unchanged.<br>
187 You can also set transitions for a list of symbols by using<br>
188 <a href="#FSM-add_transition_list">add_transition_list</a>().</tt></dd></dl>
190 <dl><dt><a name="FSM-add_transition_any"><strong>add_transition_any</strong></a>(self, state, action<font color="#909090">=None</font>, next_state<font color="#909090">=None</font>)</dt><dd><tt>This adds a transition that associates:<br>
192 (current_state) --> (action, next_state)<br>
194 That is, any input symbol will match the current state.<br>
195 The <a href="#FSM-process">process</a>() method checks the "any" state associations after it first<br>
196 checks for an exact match of (input_symbol, current_state).<br>
198 The action may be set to None in which case the <a href="#FSM-process">process</a>() method will<br>
199 ignore the action and only set the next_state. The next_state may be<br>
200 set to None in which case the current state will be unchanged.</tt></dd></dl>
202 <dl><dt><a name="FSM-add_transition_list"><strong>add_transition_list</strong></a>(self, list_input_symbols, state, action<font color="#909090">=None</font>, next_state<font color="#909090">=None</font>)</dt><dd><tt>This adds the same transition for a list of input symbols.<br>
203 You can pass a list or a string. Note that it is handy to use<br>
204 string.digits, string.whitespace, string.letters, etc. to add<br>
205 transitions that match character classes.<br>
207 The action may be set to None in which case the <a href="#FSM-process">process</a>() method will<br>
208 ignore the action and only set the next_state. The next_state may be<br>
209 set to None in which case the current state will be unchanged.</tt></dd></dl>
211 <dl><dt><a name="FSM-get_transition"><strong>get_transition</strong></a>(self, input_symbol, state)</dt><dd><tt>This returns (action, next state) given an input_symbol and state.<br>
212 This does not modify the <a href="#FSM">FSM</a> state, so calling this method has no side<br>
213 effects. Normally you do not call this method directly. It is called by<br>
214 <a href="#FSM-process">process</a>().<br>
216 The sequence of steps to check for a defined transition goes from the<br>
217 most specific to the least specific.<br>
219 1. Check state_transitions[] that match exactly the tuple,<br>
220 (input_symbol, state)<br>
222 2. Check state_transitions_any[] that match (state)<br>
223 In other words, match a specific state and ANY input_symbol.<br>
225 3. Check if the default_transition is defined.<br>
226 This catches any input_symbol and any state.<br>
227 This is a handler for errors, undefined states, or defaults.<br>
229 4. No transition was defined. If we get here then raise an exception.</tt></dd></dl>
231 <dl><dt><a name="FSM-process"><strong>process</strong></a>(self, input_symbol)</dt><dd><tt>This is the main method that you call to process input. This may<br>
232 cause the <a href="#FSM">FSM</a> to change state and call an action. This method calls<br>
233 <a href="#FSM-get_transition">get_transition</a>() to find the action and next_state associated with the<br>
234 input_symbol and current_state. If the action is None then the action<br>
235 is not called and only the current state is changed. This method<br>
236 processes one complete input symbol. You can process a list of symbols<br>
237 (or a string) by calling <a href="#FSM-process_list">process_list</a>().</tt></dd></dl>
239 <dl><dt><a name="FSM-process_list"><strong>process_list</strong></a>(self, input_symbols)</dt><dd><tt>This takes a list and sends each element to <a href="#FSM-process">process</a>(). The list may<br>
240 be a string or any iterable object.</tt></dd></dl>
242 <dl><dt><a name="FSM-reset"><strong>reset</strong></a>(self)</dt><dd><tt>This sets the current_state to the initial_state and sets<br>
243 input_symbol to None. The initial state was set by the constructor<br>
244 <a href="#FSM-__init__">__init__</a>().</tt></dd></dl>
246 <dl><dt><a name="FSM-set_default_transition"><strong>set_default_transition</strong></a>(self, action, next_state)</dt><dd><tt>This sets the default transition. This defines an action and<br>
247 next_state if the <a href="#FSM">FSM</a> cannot find the input symbol and the current<br>
248 state in the transition list and if the <a href="#FSM">FSM</a> cannot find the<br>
249 current_state in the transition_any list. This is useful as a final<br>
250 fall-through state for catching errors and undefined states.<br>
252 The default transition can be removed by setting the attribute<br>
253 default_transition to None.</tt></dd></dl>
255 </td></tr></table></td></tr></table><p>
256 <table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
257 <tr bgcolor="#eeaa77">
258 <td colspan=3 valign=bottom> <br>
259 <font color="#ffffff" face="helvetica, arial"><big><strong>Functions</strong></big></font></td></tr>
261 <tr><td bgcolor="#eeaa77"><tt> </tt></td><td> </td>
262 <td width="100%"><dl><dt><a name="-BeginBuildNumber"><strong>BeginBuildNumber</strong></a>(fsm)</dt></dl>
263 <dl><dt><a name="-BuildNumber"><strong>BuildNumber</strong></a>(fsm)</dt></dl>
264 <dl><dt><a name="-DoEqual"><strong>DoEqual</strong></a>(fsm)</dt></dl>
265 <dl><dt><a name="-DoOperator"><strong>DoOperator</strong></a>(fsm)</dt></dl>
266 <dl><dt><a name="-EndBuildNumber"><strong>EndBuildNumber</strong></a>(fsm)</dt></dl>
267 <dl><dt><a name="-Error"><strong>Error</strong></a>(fsm)</dt></dl>
268 <dl><dt><a name="-main"><strong>main</strong></a>()</dt><dd><tt>This is where the example starts and the <a href="#FSM">FSM</a> state transitions are<br>
269 defined. Note that states are strings (such as 'INIT'). This is not<br>
270 necessary, but it makes the example easier to read.</tt></dd></dl>