This is an example of using the FSM library to evaluate simple arithmetic expressions. The example is based on work originally found in a Libero Example. This class defines methods within an FSM to accept an arithmetic expression, parse the expression and calculate the result from expression. The program accepts strings like "8+sqrt(4*4 - 4*8*5) and calculates the result.
CCalculator combines several basic programming techniques: token parsing, push-down stacks for the operands and operators, and FSM states to indicate what tokens are valid and how valid tokens are handled. The basic idea is to parse the expression into tokens that are either an operand or operator one by one, then stack and evaluate the tokens according to the priority rules until reaching the end of the expression. The tokens are classified as:
Within a given state, it can accept specific tokens and reject others. For instance, at the start of the expression, an operator such as '(', sqrt, or an operand like '8.24' are valid while operators like '*' or ')' are not valid. The primary CCalculator states are EXPECTING-OPERAND, EXPECTING-OPERATOR, and TERMINATE-PROGRAM.
When in the EXPECTING-OPERAND state, it will accept an operand token and push its value onto the operand push-down stack. The EXPECTING-OPERAND state will accept a unaryoperator token (i.e., ' +' or '-' ), and uses a guardian condition to determine the next state in which to transition. The guardian condition uses the lookahead token to detemine if the next token is a number. If the lookahead token is a number, the transition action is to do a stacksignednumber action and place the number on the operand stack, otherwise the transition action is logs the FAILED state where it logs an error message. The same condition is used for both transitions and the fail transition uses the "invert" of the guardian function to determine an error condition.
The EXPECTING-OPERAND state will accept a '(' operator and place it on the operator stack, that will be later matched when unstacking the operators with a ')' operator. When in the EXPECTING-OPERATOR state, it will accept an operator token, but before it will stack the operator, it evaluates any previous operators that have the same, or higher priority on the operator, (such as '*' and '/' higher priority than '+' and '-') and push its value onto the operand push-down stack. When evaluating the top operator and the operand stack are passed to opeEVAL, which pops one or two operands depending on the number required by the operator, does the calculation and pushed the new value onto the operand stack.
A special end-mark token signals the end of the expression and from most states causes a transition to the TERMINATE-PROGRAM state, whereby it evaluates any remaining operators, which leaves the result of the expression on top of the operand stack. Some error checking is performed while parsing and evaluating the expression so that any errors cause the FSM to transition to the FAILED state, enters an error message and then quit.
The calculate uses the following state logic to parse expressions:
FSM Calculator First State = EXPECTING-OPERAND | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Beginning State | Event | Conditions | Ending State | Actions |
EXPECTING-OPERAND | operator | checkSignedNumber | EXPECTING-OPERATOR | stacksignednumber |
EXPECTING-OPERAND | operator | NOT(checkSignedNumber) | EXPECTING-OPERATOR | failedSignedNumber |
EXPECTING-OPERAND | unaryoperator | EXPECTING-OPERAND | allowunaryoperator | |
EXPECTING-OPERAND | number | EXPECTING-OPERATOR | stackNumber | |
EXPECTING-OPERAND | left-paren | EXPECTING-OPERAND | stackLeftParen | |
EXPECTING-OPERAND | end-mark | TERMINATE-PROGRAM | terminate | |
EXPECTING-OPERAND | fail | FAILED | fail | |
EXPECTING-OPERATOR | operator | EXPECTING-OPERAND | unstackGEOperator stackOperator | |
EXPECTING-OPERATOR | number | FAILED | noOperation | |
EXPECTING-OPERATOR | right-paren | EXPECTING-OPERATOR | unstackAllOperators unstackIfLeftParen | |
EXPECTING-OPERATOR | end-mark | TERMINATE-PROGRAM | unstackAllOperators | |
EXPECTING-OPERATOR | fail | FAILED | fail | |
TERMINATE-PROGRAM | end-mark | TERMINATE-PROGRAM | terminate | |
TERMINATE-PROGRAM | fail | FAILED | fail | |
Examples of the potential calculations that can be performed include:
printf("Calculate -224= %S\n", (BSTR)calc->calculate(L"-224"));
printf("Calculate -22+4= %S\n", (BSTR)calc->calculate(L"22+4"));
printf("Calculate 2+2+4= %S\n",(BSTR)calc->calculate(L"2+2+4"));
printf("Calculate1==1= %S\n", (BSTR)calc->calculate(L"1==1"));
printf("Calculate0==1= %S\n", (BSTR)calc->calculate(L"0==1"));
printf("Calculate!(0==1)= %S\n", (BSTR)calc->calculate(L"!(0==1)"));
printf("Calculate (6-2)5= %S\n", (BSTR)calc->calculate(L"(6-2)5"));
printf("Calculate sqrt(2+2)+6= %S\n", (BSTR)calc->calculate(L"sqrt(2+2)+6"));
Using the calculator to compute (6 - 2) * 5, we can follow the execution to see how the states changes evolve over time. Nothing fancy is happening, however, note that multiple actions can occur per state transitions.
Current State EXPECTING-OPERAND
Event = left-paren
stackLeftParen action
Current State EXPECTING-OPERAND
Event = numberToken Value = 6.000000
stackNumber action
Current State EXPECTING-OPERATOR
Event = operator Token Value = -
unstackGEOperator action
stackOperator action
Current State EXPECTING-OPERAND
Event = numberToken Value = 2.000000
stackNumber action
Current State EXPECTING-OPERATOR
Event = right-paren
unstackAllOperators action
Evaluate Op - with 2.000000 and [6.000000] to give Result 4.000000
Current State EXPECTING-OPERATOR
Event = operator Token Value =
unstackGEOperator action
stackOperator action
Current State EXPECTING-OPERAND
Event = number Token Value = 5.000000
stackNumber action
Current State EXPECTING-OPERATOR
Event = end-mark
unstackAllOperators action
Evaluate Op with 5.000000 and [4.000000] to give Result 20.000000
Current State TERMINATE-PROGRAM
Event = end-mark
terminate action
Calculate (6-2)5 = 20.000000
Performance timing and execution statistics are maintained automatically within the FiniteStateMachine. Statistics that are provided include the duration information while in a state: average, worst case and total elapsed, and processing profile while in a state: average, worst case and total. The duration measures the total time in a state, while the processing profile measures the CPU time per state. Every update logs the statistics associated with the updated state and within the overall FiniteStateMachine preformance. The performance timing provides a simple analysis of the FiniteStateMachine states visited, which you can use to assess the run-time behavior of your programs. By using execution statistics information, you can determine which states of your code are being used frequently, whether the states have bounded performance, and if they use the CPU efficiently.
Performance timing, like profiling, is a tuning process, that helps you make your programs run better, but unlike profiling, can help you determine program correctness bugs. Some potential logic problems that may be found include unused states, states that exceed hard-real-time processing constraints, and timing consuming states.
To dump the FSM performance timing, the information can be dumped after the FSM has completed by invoking the method timingToHTM and easily saved to file..
String timing=calc->timingToHTML();
timing.saveFile("FSM Performance Statistics");
The performance timing is given as a table in HTML format, which can easily be copied and pasted into other word processing formats. Below is an example of the calculator timing (which is so fast the state CPU processing is zero).
FSM Calculator Processing (in seconds) | ||||||||||||||||||||||||||||||||||
State | Average Duration | Worst Case Duration | Total Elapsed Duration | Average Processing | Worst Case Processing | Total Processing |
EXPECTING-OPERAND | 0.030389 | 0.547000 | 4.472000 | 0.000696 | 0.016000 | 0.250000 |
EXPECTING-OPERATOR | 0.033118 | 0.563000 | 4.738000 | 0.000800 | 0.016000 | 0.313000 |
FAILED | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
TERMINATE-PROGRAM | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
Method Summary | |
|
CCalculator(String expr=L"") |
|
~CCalculator() |
String |
calculate(String expression) Calculate is the main function for the class. |
bool |
checkSignedNumber() Condition to check if valid signed number, when expecting regular number/operand. |
HRESULT |
fail(CFiniteStateMachine * fsm,
CFSMEvent * event) Failure of some sort. |
HRESULT |
failedSignedNumber(CFiniteStateMachine * fsm,
CFSMEvent * event) Failure of some signed number sort. |
CToken |
getNextToken() Get the next token from the line. |
HRESULT |
noOperation(CFiniteStateMachine * fsm,
CFSMEvent * event) Dummy nop action. |
static int |
opEVAL(OPTYPE op,
std::mystack Evaluates a operation as given by an OPTYPE op, and operands from the operand stack. |
HRESULT |
resetFSM() Reset calculator FSM and looping logic. |
void |
setupFSM() Setup assigns event, actions, and state transition to all states in the calculator. |
HRESULT |
stackLeftParen(CFiniteStateMachine * fsm,
CFSMEvent * event) Stack left parenthesis action. |
HRESULT |
stackNumber(CFiniteStateMachine * fsm,
CFSMEvent * event) Stack number action. |
HRESULT |
stackOperator(CFiniteStateMachine * fsm,
CFSMEvent * event) Stack operator action. |
HRESULT |
stacksignednumber(CFiniteStateMachine * fsm,
CFSMEvent * event) Stack signed number, when expecting regular number/operand. |
HRESULT |
stackunaryoperator(CFiniteStateMachine * fsm,
CFSMEvent * event) Action to stack unary operator on operator stack. |
HRESULT |
terminate(CFiniteStateMachine * fsm,
CFSMEvent * event) Terminate calculation. |
HRESULT |
unstackAllOperators(CFiniteStateMachine * fsm,
CFSMEvent * event) Unstack all operators on the operator stack. |
HRESULT |
unstackGEOperator(CFiniteStateMachine * fsm,
CFSMEvent * event) Unstack operators that are of greater precedence than the current operator. |
HRESULT |
unstackIfLeftParen(CFiniteStateMachine * fsm,
CFSMEvent * event) If top operator is left parenthesis, then unstack and evaluate operators. |
Methods in class CFiniteStateMachine |
~CFiniteStateMachine () CFSMTransitionPtr addActivity (String state, String event, CFSMAction * action1, CFSMAction * action2, ... ) void addEntryAction (String state, CFSMObjectPtr owner, FSMvoidFunction action, CFSMObjectPtr owner2, ... ) void AddError (String errmsg) HRESULT addEvent (CFSMEventPtr fsmEvent) void addExitAction (String state, CFSMObjectPtr owner, FSMvoidFunction action, CFSMObjectPtr owner2, ... ) void addFSM (CFiniteStateMachinePtr fsm) HRESULT addState (CFSMStatePtr fsmState) void addStateChange (String state, String event, String next) void addStateChangeObserver (IFSMStateChangeObserver * observer) CFSMTransitionPtr addTransition (String state, String event, String next, CFSMAction * action1, CFSMAction * action2, ... ) CFSMTransitionPtr addTransition (String state, String event, String next, CFSMObjectPtr owner, FSMObjectFunction action, CFSMObjectPtr owner2, ...) boolean canHandleEvent (String stateName, String event) boolean canHandleEvent (String event) String ErrorMessage (HRESULT error) CFSMEventPtr findEvent (CFiniteStateMachinePtr fsm, String event) CFSMStatePtr findState (CFiniteStateMachinePtr fsm, String state) HRESULT forceCurrentState (String state) CFSMEventPtr getCurrentEvent () CFSMStatePtr getCurrentState () String getCurrentStateName () String getEdges () String GetError () CFSMEventPtr getEvent (String event) String getEvents () CFSMStatePtr getFirstState () String getFSMEdges () CFSMPolicyPtr getFSMPolicy () CFSMStatePtr getState (String state) String getStates () CFiniteStateMachinePtr getTopLevelFSM () String getType () HRESULT HandleError (HRESULT hr) DWORD handleEvent (CFSMEvent * fsmevent, int operationalType) DWORD handleEvent (CFSMEvent event, int operationalType) boolean handleEvents (String events[]) boolean isAlive () boolean isDone () boolean isFirstTime () boolean jamEvent (CFSMEvent event) HRESULT postprocessUpdateAction () HRESULT preprocessUpdateAction () HRESULT processEvent (CFSMEvent * event) HRESULT processEvent (CFSMEvent event) void releaseFSM () void ResetError () HRESULT resetFSM () void resumeThread () void setCurrentEvent (CFSMEventPtr next) void setCurrentState (CFSMStatePtr next) HRESULT SetError (String str) CFSMStatePtr setFirstState (CFSMStatePtr state) void setFirstState (String state) void setFSMPolicy (CFSMPolicyPtr policy) void setupFSM () String setupToString () void sleep (long millis, int nanos) HRESULT startThread () void stopThread () void suspendThread () String timingToHTML () String toDebugString () String toHTML (int highlightlatesttransition) HRESULT ToString (BSTR * str) String toTableFormat (int highlightlatesttransition) String toText () HRESULT updateFSM () HRESULT updateFSMPolicy () void yield ()
|
Methods in class CFSMState |
CFSMState (String name) CFSMState () ~CFSMState () void addEntryAction (CFSMActionPtr action) void addExitAction (CFSMActionPtr action) CFSMTriggerPtr addPostTrigger (CFSMTriggerPtr trigger) CFSMTriggerPtr addPreTrigger (CFSMTriggerPtr trigger) CFSMTransitionPtr addTransition (CFSMEventPtr event, CFSMStatePtr next, CFSMActionPtr action, CFSMActionPtr action2, ...) boolean eventValid (CFSMEventPtr event) String getEdges () String getTransitions () String getType () HRESULT handleTransition (CFSMTransitionPtr transition, CFSMEventPtr event, CFSMStatePtr &nextState) CFSMTransitionPtr lookupTransition (CFSMStatePtr state) HRESULT lookupTransition (CFSMEventPtr event, CFSMTransitionPtr & validtransition) CFSMEventPtr lookupTransitionEvent (CFSMStatePtr nextState) void releaseState () CFSMActionPtr setActivityHook (CFSMActionPtr activityHook) CFSMActionPtr setEntryActionHook (CFSMActionPtr entryActionHook) CFSMActionPtr setExitActionHook (CFSMActionPtr exitActionHook) void setPostUpdateAction (CFSMActionPtr action) void setPreUpdateAction (CFSMActionPtr action) boolean stateValid (CFSMStatePtr state) String toDebugString () HRESULT updateState (CFSMEventPtr event, CFSMStatePtr &nextState, CFSMTransitionPtr &transition) HRESULT updateState (CFSMStatePtr state, CFSMStatePtr &nextState, CFSMTransitionPtr &transition)
|
Methods in class CFSMObject |
String diagnostics () String getName () String getType () void setName (String aname)
|
Methods in class RefCount |
RefCount (void) ~RefCount () static String classInfo () void DecRef () void flagDelete (int i) String getType () size_t howMany () int IncRef ()
|
Method Detail |
CCalculator(String expr=L"")
~CCalculator()
String calculate(String expression)
bool checkSignedNumber()
HRESULT fail(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT failedSignedNumber(CFiniteStateMachine * fsm,
CFSMEvent * event)
CToken getNextToken()
HRESULT noOperation(CFiniteStateMachine * fsm,
CFSMEvent * event)
static int opEVAL(OPTYPE op,
std::mystack &operands)
HRESULT resetFSM()
void setupFSM()
HRESULT stackLeftParen(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT stackNumber(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT stackOperator(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT stacksignednumber(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT stackunaryoperator(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT terminate(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT unstackAllOperators(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT unstackGEOperator(CFiniteStateMachine * fsm,
CFSMEvent * event)
HRESULT unstackIfLeftParen(CFiniteStateMachine * fsm,
CFSMEvent * event)