FSMGenerator
Finite State Machine generating software
Copyright © 2002-2003 Pavel Bekkerman
by Pavel Bekkerman (chpavel@tx.technion.ac.il)
Abstract
Similarly to the Finite Automata model in Computer Science, Finite State Machine model finds its widest use in Software Engineering. As a software development design pattern, FSM occurs in many software solutions, but unlike most of its pattern counterparts, FSM requires substantial time for manual implementation. But the really devastating part of manual implementation is usually in its increasing cost of change and maintenance. All of the above considerations eventually converge to a necessity of automatic, fault-free FSM generation.
This document is a final report on a project, which set as its goal to develop a software tool that would be able to:
1) Produce FSM implementation automatically from generic human-readable configuration file
2) Produce FSM implementation in number of existing programming languages and provide a framework for adding more programming languages
3) Produce FSM that could be easily coupled with developers software
4) Produce FSM that would be totally transparent to the developer, but still, fault-free and complete.
The final product can be used for
its primary purpose – generating FSM from arbitrary configuration, as well as,
for building powerful tools for software design, implementation, testing,
verification, etc. Some examples of such applications are: graphical automata
modeling, model creation for model-based verification, model-based code synthesis
and so on.
Contents
1. Introduction
2. Product Specifications
2.1. Product Background
2.1.1. Programming model
2.1.2. FSM model
2.1.3. FSM software pattern vs. Automata mathematical model
2.2. Product Definition
2.2.1. Software tool
2.2.2. FSM human-readable configuration file
2.2.3. FSM machine-readable definition file
2.2.4. Fault handling
2.2.5. Interface between user’s software and FSM
2.2.6. Interface between FSM and user’s software
2.2.7. User Presentation
3. Product Development
3.1. Solutions and Constrains
3.2. Design
3.2.1. Configuration File Format
3.2.2. API
3.2.3. Modules
3.2.3.1. Scanner
3.2.3.2. Parser
3.2.3.3. FSM Database
3.2.3.4. FSM Database manager
3.2.3.5. Generator
3.2.3.6. Main, Common and Global
3.3. Implementation
3.4. Integration
3.5. Testing
4. Product Usage
4.1. Demo
4.2. Usage Guidelines
4.3. Extensions
5. Summary
6. TODO
Appendix
A.
List of Terms and Abbreviations
Appendix
B.
List of Figures
Appendix
C.
List of References
Appendix
D.
Product Distribution
1. Introduction
Similarly to the Finite Automata model in Computer Science, Finite State Machine model finds its widest use in Software Engineering. As a software development design pattern, FSM occurs in many software solutions, but unlike most of its pattern counterparts, FSM requires substantial time for manual implementation. But the really devastating part of manual implementation is usually in its increasing cost of change and maintenance. All of the above considerations eventually converge to a necessity of automatic, fault-free FSM generation.
This document is a final report on a project, which set as its goal to develop a software tool that would be able to:
5) Produce FSM implementation automatically from generic human-readable configuration file
6) Produce FSM implementation in number of existing programming languages and provide a framework for adding more programming languages
7) Produce FSM that could be easily coupled with developers software
8) Produce FSM that would be totally transparent to the developer, but still, fault-free and complete.
The final product can be used for its primary purpose – generating FSM from arbitrary configuration, as well as, for building powerful tools for software design, implementation, testing, verification, etc. Some examples of such applications are: graphical automata modeling, model creation for model-based verification, model-based code synthesis and so on.
Further in the document we present a full report on the product development process stage-by-stage.
2. Product Specifications
2.1. Product Background
2.1.1. Programming model
A typical 3rd generation programming language provides programmer with various tools to accomplish his algorithmic tasks:
- Type and variable definition and referencing
- Statements and expressions
- Conditional statements
- Iteration statements
- Function definition and invocation
By definition the state of the program at every execution step is an overall value situated in the memory allocated to the process. The programming language utilizes this state definition through abstraction of variable names with addition of their visibility. This way the program state transition is always partial and, therefore, hard to model for verification and vise versa - hard to synthesize from model.
However, this is not an obstacle for the human programmer, for whom such a programming model is well suitable to his way of (algorithmic) thinking.
As a software model, FSM (Finite State Machine) [1], is defined as follows:
M = { Σ, Q, δ, s, F }
Σ – the set of events
All the possible events the machine can handle and produce.
Ex: Mouse Click, Temperature Raised, Mood Changed, etc…
Q – the set of states
During the machine lifetime it resides in one of these states.
Ex:
δ – transition function
For every (state, event) pair, δ defines the next state.
I.e.: If the machine was in the state and the event would have been occurred, the machine would move into the next state.
s – start state
An exclusive state, one of the states in Q, from which the machine starts its running.
F – the set of final states
The subset of states in Q, one of which the machine takes as final.
I.e.: arriving to one of these states might result in machine stopping.
2.1.3. FSM software pattern vs. Automata mathematical model
The FSM model is nothing but the mathematical Finite Deterministic Automata.
However, for the software purposes, it is extended to provide developer with powerful programming tools:
- Independent machine running
- Event automatic, as well as, programmer introduced handling
- State automatic, as well as, programmer introduced handling
- Transition automatic, as well as, programmer introduced handling
- Machine fault detection and automatic, as well as, programmer introduced handling
Further in this document whenever FSM abbreviation occurs it stands for
2.2. Product Definition
The product is a software tool, which is able to build a software component implementing a user-defined FSM that could be used in other software development.
2.2.1. Software tool
As an input, the tool receives a human-readable “configuration file”, written in the “configuration language”. According to its input it produces:
- Source code files, implementing the FSM, that can be further compiled with user’s project
- Machine-readable FSM definition file, that can be further used in run-time with user’s project
The source code files, produced by the tool, SHOULD NOT be backward engineered to produce the FSM original definition. On the opposite, the tool CAN use the Machine-readable definition FSM files, for that purpose.
2.2.2. FSM human-readable configuration file
The configuration file should be written by a human and well understood by human.
This file MUST include:
- The definition of the FSM (as stated in the “Product Background” section)
Σ: Events MUST be defined by alphanumeric names.
Q: States MUST be defined by alphanumeric names.
δ: Transitions MUST be defined by alphanumeric names.
In transition definition the states and event appearing in the (State, Event) pair and resulting State, MUST be defined previously.
s: Start state MUST be one of the previously defined states, referred by its name.
F: Final states MUST be among the previously defined states, referred by their names.
The names are unique independent of the entry type they refer.
- The definition of the callbacks
Callbacks must be defined by alphanumeric names.
This file must contain FSM definition in a machine-understandable format.
The API must be provided apart from the tool, giving a similar functionality to the user.
The API must provide functionality for execution of FSM defined in the FSM machine-readable definition file in the run-time.
2.2.4. Fault handling
The produced FSM should handle ALL possible faults. These faults origin may be the FSM itself, the software coupled with it or the platform on which the software and the FSM are running.
2.2.5. Interface between user’s software and FSM
The user’s software will interface the produced FSM through a predefined API. This way the execution of the event processing by the FSM can be seen as a complete and encapsulated task resulting in FSM state change and execution of appropriate callbacks into the user’s software, defined in the below.
2.2.6. Interface between FSM and user’s software
The callback name must refer some sort of “plugs” within the user’s software, which provide the interface between the created FSM and the user’s software.
Those MAY be functions, classes, objects or variables (i.e.: flags). The choice is programming language and user dependent.
Each event can have 2 callbacks – on event incoming and on event outgoing.
(This requirement was narrowed, during the analysis, to only incoming event callback.)
Each state can have 2 callbacks – on state entry and on state exit.
Each transition can have 1 callback – on transition execution.
2.2.7. User Presentation
The tool must be easy to learn and use. If an error appears during the tool execution, it should be presented to the user with appropriate information on its origins and fixing. The produced FSM should be situated at the user-defined destination.
3. Product Development
3.1. Solutions and Constrains
Before going deeper into product development stages and reporting on their execution, we would like to enlist some of the items that came up during the requirements analysis, which predefined final product design and implementation.
The product’s purpose is to produce FSM from configuration file.
ð The configuration file format is a subject of consideration.
After the configuration file format is determined, the FSM production is a task similar to code generation by compilers [3].
ð Product design can be similar to compiler design:
· First, the configuration file is scanned;
· Then, it’s parsed and internal database holding alternative FSM definition is created;
· Then, from this database the concrete FSM implementation is generated.
Given that the product performs similar tasks to source code compilation, it’s eminent to:
ð Decide on the database format to hold the FSM definition before its generation and
ð The form of the generated FSM is a subject to consideration.
It can be considered two possible forms of generated FSM:
1. An internal database “snapshot”
ð In this case, the FSM execution through the API would require either onetime uploading of the database to the process memory, or constant queries to the database on every event processing by the FSM, or combination of two.
ð On the other hand, the FSM definition would be external to the user’s software and
ð FSM replacement would be possible at the runtime.
2. Source code produced from the internal code
ð In this case, the FSM itself is a piece of source code.
ð It can be compiled apart from the user’s software and linked with it either statically or dynamically.
ð On the other hand, this way, the code of FSM makes a substantial part of the resulting binary code although
ð The execution of the event processing by FSM is fastest possible and
ð Errors in user’s software and FSM integration are caught already at the compile time.
From the last two, it emerged that the second solution is as powerful as the first one and will even perform better during the runtime. Not to mention that it’s much easier to implement and elegant in that it produces the FSM in programming language of the user’s software – readable and understandable by the programmer.
As Fig.1 shows, the product consists of 5 principal modules residing in two layers: Scanner, Parser, Generator, Database and Database Manager. Logically, to make the generation process possible, the only thing required from the user of the product is to provide a configuration file and the appropriate FSM implementation is generated “automatically”. As Fig.1 shows there’re 2 layers for the software – Scanner/Parser/Generator and Database/Database Manager.
First, we explain on the design of API given to the user through which its software can utilize any FSM produced by the product.
Then, we explain on the design of every software module within the product.
Finally, we explain the design consideration on the module integration and the product use as a single software piece.
3.2.1. Configuration File Format
[name]
FSMIsEven /* the machine tests if a binary number is
even. */
[states]
s0;
s1;
[events]
input0;
input1;
[transitions]
t00: s0,input0->s0;
t01: s0,input1->s1;
t10: s1,input0->s0;
t11: s1,input1->s1;
[start]
s0;
[final]
s0;
[callbacks]
call0: Func0;
call1: Func1;
call2: Func2;
call3: Func3;
[hooks]
s0: call0, call2;
s1: call1;
input0: call3;
t11: call2;
Fig.2 Configuration File example
We describe the configuration file format by the example, present on Fig.2 the configuration file contains sections: name, states, events, etc. Within each section statements are separated with semicolons and, according to the section, have different formats. For example, transition definition “ t01: s0,input1->s1 ” states as follows: there’s a transition called t01, which takes the FSM from state s0 to s1, provided the event input1 occurred. Of course, s0, s1 and input1 are defined beforehand.
3.2.2. API
The API is an integral part of the software distribution. The purpose of the API is to provide the user with uniform way to invoke any FSM generated by our product.
We, thereby, explain the API design on the example of its implementation in Java [7].
The API resides in a single package we called simply “FSM”. The package contains 3 public classes, of which 2 are needed to provide interface between user’s software and generated FSM, and the last one provides the framework for user-defined FSM generation.
The first two are:
public class FSM
{
// interface
public FSM( AbstractFSM fsm );
public boolean IsFinal();
public void Initialize() throws FSMException;
public void Process( int idEvent ) throws
FSMException;
public void Attach( FSM fsm ) throws
FSMException;
public void Finalize() throws FSMException;
}
Fig.3 API (Java) – class FSM
public class FSMException
extends Exception
{
public FSMException( String strMessage );
}
Fig.4 API (Java) – class FSMException
And the second two are:
public interface AbstractFSM
{
public int
_getStartState() throws FSMException;
public
IDPair _getNextIncarnation( int idState, int idEvent )
throws FSMException;
public
boolean _isFinalState ( int idState )
throws FSMException;
public void _processStateEnter ( int isState ) throws FSMException;
public void
_processStateExit ( int isState )
throws FSMException;
public void
_processEvent ( int idEvent )
throws FSMException;
public void
_processCallback ( int idCallback )
throws FSMException;
public void
_processTransition ( int idTransition )
throws FSMException;
}
Fig.5 API (Java) – interface AbstractFSM
public class IDPair
{
public
IDPair()
{
}
public int
idFirst;
public int
idSecond;
}
Fig.6 API (Java) – class IDPair (“non-public” class)
The FSM generated by the product is a source files containing source code implementing user-defined FSM functionality. Our design solution was to predefine abstract FSM functionality in terms of its interface, which the concrete FSM would implement. This is done through the interface Abstract FSM. When a new FSM is generated it implements the AbstractFSM interface by providing concrete implementation to its methods, i.e.: _processEvent, _processTransition.
Then, the generated FSM, identified by unique class name, which is one of the user-defined parameters, is passed to an instance of class FSM, during its construction. Class FSM has standard methods for concrete FSM manipulation, which totally encapsulate its presence, once passed to the class FSM instance. Only by using Process method of the class FSM, the user’s software can initiate event processing generated FSM. The processing can then results in callbacks to user’s software, and by definition, to the FSM state change.
Here’s an example of an API use:
public
static void main(String[] args)
{
FSM fsm
= new FSM( new FSMPresentation() );
try
{
fsm.Initialize();
fsm.Process( IDEvents.EVENT_nickel );
fsm.Process( IDEvents.EVENT_dime );
fsm.Process( IDEvents.EVENT_quarter );
fsm.Process( IDEvents.EVENT_select_soda );
if(
fsm.IsFinal() )
{
System.out.println( "Final" );
}
else
{
System.out.println( "NonFinal" );
}
fsm.Finalize();
}
catch(
FSMException e )
{
System.out.println( e );
}
}
Fig.7 API (Java) – using the generated FSM through API’s class FSM instance
In addition, as Fig.7 shows, if a fault occurs during the generated FSM execution, FSMException can be caught to handle it.
This concludes the API design description.
3.2.3. Modules
Once again, as Fig.1 shows, the product consists of 5 principal modules residing in two layers: Scanner, Parser, Generator, Database and Database Manager. We will now go deeper into design of each one of these modules.
3.2.3.1. Scanner
The scanner is a back-end of the FSM generating tool. The input to the scanner is the configuration file. “Something” external opens a file stream for the configuration file, from which the scanner pulls characters one-by-one. The output of the scanner is a series of tokens, which the scanner was able to realize from the stream reading, while meaningless characters are omitted (this functionality is also called screening).
To build scanner for FSM configuration file we used the FLEX – character stream scanner generation tool [4]. FLEX receives a configuration file containing definition of the tokens, the scanner should retrieve from the stream in a form of regular expressions and generates a C code for this scanner. The scanner then is able to interact with user’s software in the next way: the user’s software opens the stream and delivers its handler to the scanner. Then by continuously invoking yylex() function of the scanner, the user’s software makes it scan the stream and return each time either new token, the end-of-the-file mark or an error message.
This is the configuration file for the scanner:
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "scanner.h"
void prepare_token( int nID );
int g_nLine = 1;
%}
SQUARE_BRACET_LEFT "["
SQUARE_BRACET_RIGHT "]"
COLLON ":"
SEMICOLLON ";"
COMMA ","
DOT "."
QUOTATION "\""
ARROW "-"">"
DIGIT
[0-9]
SYMBOL
[a-zA-Z_$@]
INTEGER {DIGIT}*
FLOAT {DIGIT}*{DOT}{DIGIT}+
NAME {SYMBOL}({SYMBOL}|{DIGIT})*
STRING {QUOTATION}({SYMBOL}|{DIGIT})*{QUOTATION}
COMMENT "/""*""*""/"|"/""*"([^"*"]|"*"[^"/"])*"*""/"
SECTION {SQUARE_BRACET_LEFT}{NAME}{SQUARE_BRACET_RIGHT}
%%
{DOT} {
prepare_token( TOKEN_DOT ); return( ERROR_SUCCESS ); }
{SEMICOLLON} { prepare_token( TOKEN_SEMICOLLON ); return( ERROR_SUCCESS ); }
{COLLON} {
prepare_token( TOKEN_COLLON ); return( ERROR_SUCCESS ); }
{COMMA} {
prepare_token( TOKEN_COMMA ); return( ERROR_SUCCESS ); }
{ARROW} {
prepare_token( TOKEN_ARROW ); return( ERROR_SUCCESS ); }
{SECTION} {
prepare_token( TOKEN_SECTION ); return( ERROR_SUCCESS ); }
{STRING} {
prepare_token( TOKEN_STRING ); return( ERROR_SUCCESS ); }
{NAME} {
prepare_token( TOKEN_NAME ); return( ERROR_SUCCESS ); }
{COMMENT} {
prepare_token( TOKEN_COMMENT ); return( ERROR_SUCCESS ); }
[\t\f\ ]+ {}
"\n" { g_nLine++; }
. {
fprintf( stderr,"unexpected char '%c'!\n", yytext[0]); exit(-1); }
%%
int yywrap()
{
return 1;
}
void prepare_token( int nID )
{
yylval.id
= nID;
yylval.text
= (char*) malloc( strlen(yytext) + 1 );
yylval.line
= g_nLine;
strcpy( yylval.text, yytext );
}