1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
<!doctype html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module FSM</title>
</head><body bgcolor="#f0f0f8">
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"> <br><big><big><strong>FSM</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/noah/documents/export/engineering/source/python/pexpect/trunk/pexpect/FSM.py">/home/noah/documents/export/engineering/source/python/pexpect/trunk/pexpect/FSM.py</a></font></td></tr></table>
<p><tt>This module implements a Finite State Machine (<a href="#FSM">FSM</a>).<br>
In addition to state this <a href="#FSM">FSM</a> also maintains a user defined "something".<br>
This "something" is effectively memory, so this <a href="#FSM">FSM</a> could be considered<br>
a Push-down Automata (PDA) since a PDA is a <a href="#FSM">FSM</a> + memory.<br>
<br>
The following describes how the <a href="#FSM">FSM</a> works, but you will probably also need<br>
to see the example function to understand how the <a href="#FSM">FSM</a> is used in practice.<br>
<br>
You define an <a href="#FSM">FSM</a> by building tables of transitions.<br>
For a given input symbol the process() method uses these tables <br>
to decide what action to call and what the next state will be. <br>
The <a href="#FSM">FSM</a> has a table of transitions that associate:<br>
(input_symbol, current_state) --> (action, next_state)<br>
where "action" is a function you define. The symbols and states <br>
can be any objects. You use the add_transition() and add_transition_list() <br>
methods to add to the transition table. The <a href="#FSM">FSM</a> also has a table<br>
of transitions that associate:<br>
(current_state) --> (action, next_state)<br>
You use the add_transition_any() method to add to this transition table.<br>
The <a href="#FSM">FSM</a> also has one default transition that is not associated<br>
with any specific input_symbol or state. You use the <br>
set_default_transition() method to set the default transition.<br>
<br>
When an action function is called it is passed a reference to the <a href="#FSM">FSM</a>.<br>
The action function may then access attributes of the <a href="#FSM">FSM</a> such as<br>
input_symbol, current_state, or "something". The "something" attribute <br>
can be any object that you want to pass along to the action functions.<br>
It is not used by the <a href="#FSM">FSM</a>. For parsing you would typically pass a list <br>
to be used as a stack.<br>
<br>
The processing sequence is as follows.<br>
The process() method is given an input_symbol to process.<br>
The <a href="#FSM">FSM</a> will search the table of transitions that associate:<br>
(input_symbol, current_state) --> (action, next_state) <br>
If the pair (input_symbol, current_state) is found then <br>
process() will call the associated action function and then set the <br>
current state to the next_state.<br>
<br>
If the <a href="#FSM">FSM</a> cannot find a match for (input_symbol, current_state)<br>
it will then search the table of transitions that associate:<br>
(current_state) --> (action, next_state)<br>
If the current_state is found then the process() method will call <br>
the associated action function and then set the current state to <br>
the next_state. Notice that this table lacks an input_symbol. <br>
It lets you define transitions for a current_state and ANY input_symbol.<br>
Hence, it is called the "any" table. Remember, it is always checked<br>
after first searching the table for a specific (input_symbol, current_state).<br>
<br>
For the case where the <a href="#FSM">FSM</a> did not match either of the previous two cases<br>
the <a href="#FSM">FSM</a> will try to use the default transition. If the default transition<br>
is defined then the process() method will call the associated action function<br>
and then set the current state to the next_state. This lets you define <br>
a default transition as a catch-all case. You can think of it as an <br>
exception handler. There can be only one default transition.<br>
<br>
Finally, if none of the previous cases are defined for an input_symbol <br>
and current_state then the <a href="#FSM">FSM</a> will raise an exception. <br>
This may be desirable, but you can always prevent this just by <br>
defining a default transition.<br>
<br>
Noah Spurrier<br>
<br>
$Revision: 33 $<br>
$Date: 2002-08-28 12:07:03 -0700 (Wed, 28 Aug 2002) $</tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#aa55cc">
<td colspan=3 valign=bottom> <br>
<font color="#fffff" face="helvetica, arial"><big><strong>Modules</strong></big></font></td></tr>
<tr><td bgcolor="#aa55cc"><tt> </tt></td><td> </td>
<td width="100%"><table width="100%" summary="list"><tr><td width="25%" valign=top><a href="string.html">string</a><br>
</td><td width="25%" valign=top></td><td width="25%" valign=top></td><td width="25%" valign=top></td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
<tr><td bgcolor="#ee77aa"><tt> </tt></td><td> </td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="FSM.html#FSM">FSM</a>
</font></dt><dt><font face="helvetica, arial"><a href="exceptions.html#Exception">exceptions.Exception</a>
</font></dt><dd>
<dl>
<dt><font face="helvetica, arial"><a href="FSM.html#ExceptionFSM">ExceptionFSM</a>
</font></dt></dl>
</dd>
</dl>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom> <br>
<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>
<tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
<td colspan=2><tt>This is the <a href="#FSM">FSM</a> <a href="exceptions.html#Exception">Exception</a> class.<br> </tt></td></tr>
<tr><td> </td>
<td width="100%">Methods defined here:<br>
<dl><dt><a name="ExceptionFSM-__init__"><strong>__init__</strong></a>(self, value)</dt></dl>
<dl><dt><a name="ExceptionFSM-__str__"><strong>__str__</strong></a>(self)</dt></dl>
<hr>
Methods inherited from <a href="exceptions.html#Exception">exceptions.Exception</a>:<br>
<dl><dt><a name="ExceptionFSM-__getitem__"><strong>__getitem__</strong></a>(...)</dt></dl>
</td></tr></table> <p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom> <br>
<font color="#000000" face="helvetica, arial"><a name="FSM">class <strong>FSM</strong></a></font></td></tr>
<tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
<td colspan=2><tt>This is a Finite State Machine (<a href="#FSM">FSM</a>).<br> </tt></td></tr>
<tr><td> </td>
<td width="100%">Methods defined here:<br>
<dl><dt><a name="FSM-__init__"><strong>__init__</strong></a>(self, initial_state, something)</dt><dd><tt>This creates the <a href="#FSM">FSM</a>. <br>
You set the initial state here. The "something" attribute is any<br>
object that you want to pass along to the action functions.<br>
It is not used by the <a href="#FSM">FSM</a>. For parsing you would typically pass <br>
a list to be used as a stack.</tt></dd></dl>
<dl><dt><a name="FSM-add_transition"><strong>add_transition</strong></a>(self, input_symbol, state, action, next_state)</dt><dd><tt>This adds a transition that associates<br>
(input_symbol, current_state) --> (action, next_state)<br>
The action may be set to None in which case the <a href="#FSM-process">process</a>() method <br>
will ignore the action and only set the next_state.<br>
<br>
You can also set transitions for a list of symbols by using<br>
<a href="#FSM-add_transition_list">add_transition_list</a>().</tt></dd></dl>
<dl><dt><a name="FSM-add_transition_any"><strong>add_transition_any</strong></a>(self, state, action, next_state)</dt><dd><tt>This adds a transition that associates<br>
(current_state) --> (action, next_state)<br>
The <a href="#FSM-process">process</a>() method checks these associations if it cannot<br>
first find a match of an (input_symbol, current_state).</tt></dd></dl>
<dl><dt><a name="FSM-add_transition_list"><strong>add_transition_list</strong></a>(self, list_input_symbols, state, action, next_state)</dt><dd><tt>This adds the same transition for lots of different input symbols.<br>
You can pass a list or a string. Note that it is handy to use<br>
string.digits, string.whitespace, string.letters, etc. to add<br>
transitions that match character classes.</tt></dd></dl>
<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>
This leaves the <a href="#FSM">FSM</a> unchanged. This does not update the current state <br>
nor does it trigger the output action. Normally you do not call <br>
this method. It is called by <a href="#FSM-process">process</a>().<br>
<br>
The sequence of steps to check for a defined transition goes from <br>
the most specific to the least specific. <br>
1. Check state_transitions[] that match (input_symbol, state)<br>
2. Check state_transitions_any[] that match (state)<br>
In other words, match a specific state and ANY input_symbol.<br>
3. Check if the default_transition is defined.<br>
This catches any input_symbol and any state.<br>
This is a handler for errors, undefined states, or defaults.<br>
4. No transition was defined. If we get here then raise an exception.</tt></dd></dl>
<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.<br>
This may cause the <a href="#FSM">FSM</a> to change state and call an action.<br>
This method calls <a href="#FSM-get_transition">get_transition</a>() to find the action and next_state<br>
associated with the input_symbol and current_state.<br>
If the action is None then the action is not called and<br>
only the current state is changed.<br>
This method processes one input symbol. You can process a list of<br>
symbols (or a string) by calling <a href="#FSM-process_list">process_list</a>().</tt></dd></dl>
<dl><dt><a name="FSM-process_list"><strong>process_list</strong></a>(self, s)</dt><dd><tt>This takes a list and sends each element to <a href="#FSM-process">process</a>().<br>
The list may be a string.</tt></dd></dl>
<dl><dt><a name="FSM-reset"><strong>reset</strong></a>(self)</dt><dd><tt>This sets the current_state to the initial_state and<br>
sets input_symbol to None.<br>
The initial state was set by the constructor <a href="#FSM-__init__">__init__</a>().</tt></dd></dl>
<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. <br>
This defines an action and next_state if the <a href="#FSM">FSM</a> cannot find the<br>
input symbol and the current state in the transition list and <br>
if the <a href="#FSM">FSM</a> cannot find the current_state in the transition_any list.<br>
This is useful for catching errors and undefined states. <br>
<br>
The default transition can be removed by setting the attribute<br>
default_transition to None.</tt></dd></dl>
</td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#eeaa77">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Functions</strong></big></font></td></tr>
<tr><td bgcolor="#eeaa77"><tt> </tt></td><td> </td>
<td width="100%"><dl><dt><a name="-BeginBuildNumber"><strong>BeginBuildNumber</strong></a>(fsm)</dt><dd><tt># These define the actions. <br>
# Note that "something" is a list being used as a stack.</tt></dd></dl>
<dl><dt><a name="-BuildNumber"><strong>BuildNumber</strong></a>(fsm)</dt></dl>
<dl><dt><a name="-DoEqual"><strong>DoEqual</strong></a>(fsm)</dt></dl>
<dl><dt><a name="-DoOperator"><strong>DoOperator</strong></a>(fsm)</dt></dl>
<dl><dt><a name="-EndBuildNumber"><strong>EndBuildNumber</strong></a>(fsm)</dt></dl>
<dl><dt><a name="-Error"><strong>Error</strong></a>(fsm)</dt></dl>
<dl><dt><a name="-example"><strong>example</strong></a>()</dt><dd><tt># This is where the example starts and the <a href="#FSM">FSM</a> state transitions are defined.<br>
# Note that states (such as 'INIT') are strings. This is not necessary, but<br>
# it makes the example easier to read.</tt></dd></dl>
</td></tr></table>
</body></html>
|
