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 );
}
3.2.3.2. Parser
The input to the parser is the output of the scanner. The parser should realize statements, which define the FSM, according to the FSM configuration file grammar rules.
To automatically generate parser, just like we did with the scanner, we might use a YACC-like tool, BISON [5], for example. But, to simplify our task we decided to implement the parser by ourselves, using, of course… a Finite State Machine approach! So, once again we had that tradeoff.
The parser module contains a single method that receives a file to-be-parsed.
FSMDB* parse( const char
*strConfigurationFileName );
Fig.9 Parser’s main method
This method opens the file stream for this file and passes its handler to the scanner. By invoking scanner’s method yylex(), it then gets token one-by-one, until the EOF is reached.
Without getting deeper into the parsers infrastructure, like we said it’s implemented as Finite State Machine, we will just say that: once parser realizes that the tokens form, for example, transition definition, it updates the FSM Database with this definition. This way, by the end of parsing, if no scanning or parsing error occurred, the FSM Database contains an internal representation of the FSM configuration file.
The next step, however, will be to check this Database integrity in respect to FSM model and to, finally, generate the FSM. These steps are in a responsibility of the Generator module.
3.2.3.3. FSM Database
We’d like to state only a few words about the FSM Database module design.
Unlike the Scanner or the Parser module, the Database module is design entirely in Object-Oriented paradigm. The final module design contains 6 different classes. These can be grouped as follows:
- Data classes: Event, State, Transition and Callback
- Database itself: FSMDB
- Interface classes: FSMDBException
struct FSMDB
{
FSMDB(const
string& name = STRNULL);
~FSMDB();
string
m_strName; // the FSM name.
const
string& Name ()const;
// Data
holders (can be read directly by the file generators).
vector<State> m_dvStates;
vector<Event> m_dvEvents;
vector<Transition> m_dvTransitions;
vector<Callback> m_dvCallbacks;
vector<ID> m_dvFinalID;
index m_indStart;
};
Fig.10 FSMDB class
Already at the design stage, we decided on an extensive use of STL [6] in the FSMDB implementation.
Finally, to simplify access for a high-level parser to a low-level database we designed a FSM Database Manager.
3.2.3.4. FSM Database Manager
class FSMDBManager class FSMDBManager
{
public:
FSMDBManager(FSMDB&);
~FSMDBManager();
const
string& Name ()const;
//
Insertion Interface.
void
NameSet (const string&);
void
StateInsert (const string& name);
void
EventInsert (const string& name);
void
TransInsert (const string& name,
const string&
from,
const
string& event,
const string&
to);
void
StartSet (const string& name);
void
FinalInsert (const string& name);
void
CallbackInsert (const string&
callName,
const string&
funcName);
void
HookSet (const string& name,
const string&
call1,
const string&
all2=STRNULL);
};
Fig.11 FSMDBManager class’s public interface
The names of the FSMDBManager class’s methods speak for themselves.
As it can be seen, the identification of the states, events, transitions, callbacks and hooks is name-based. So names must be unique, and if not, an FSMDBException is thrown.
3.2.3.5. Generator
The Generator module was also designed using OO-paradigm. Moreover, the purpose of Generator module is not only to provide FSM generators for required destination programming languages (C, CPP and Java), but also provide a framework for tool extension by adding generators for additional programming languages.
class FSMFileGenerator
{
protected:
const FSMDB&
m_fsmDb;
string m_strDestinationPath;
virtual bool
_stateFileGenerator()const = 0;
virtual bool
_eventFileGenerator()const = 0;
virtual bool
_transFileGenerator()const = 0;
virtual bool
_callsFileGenerator()const = 0;
virtual bool
_mainFileGenerator ()const = 0;
int _directoryCreate();
public:
FSMFileGenerator(const
FSMDB&, const string& strPath);
virtual
~FSMFileGenerator();
bool
GenerateFiles ();
};
Fig.11 Class FSMFileGenerator of the Generator module
FSMFileGenerator defines concrete generation pattern – generator receives Database and path where to put the generated files. It also defines abstract methods for each of the generated item.
The concrete implantation of the generation for particular programming language is, then, a task of a class that inherits from the FSMFileGenerator. We provide all ready: FSMCPPGenerator and FSMJavaGenerator.
The details of the FSM generation for particular programming language are out of the scope of this document. We, hereby, address the reader to the actual code of the generators. Also, reviewing a code of the generated FSM in a familiar programming language would add considerably to understanding of the product functionality (see Appendix D.).
3.2.3.6. Main, Common and Global
Main, Common and Global are support modules. These modules always present in every software design and their responsibility is as follows:
- Common and/or Global
These two have the same responsibility of defining error message codes, constants and any other features common to all of the modules within the software.
- Main
This module creates, initializes, invokes and, at the end, cleanups the rest of the modules within the software.
3.3. Implementation
We’ve already noted some of the aspects of modules implementation. Scanner and Parser, Main, Common and Global were implemented in C language. FSM Database, Database Manager and Generators were implemented in C++, using C/C++ Standard Programming Library (ANSI) and STL.
From the above, the portability of the source code to various platforms is straightforward. We successfully compiled the code on Unix (Linux RedHat 7.2) and Windows (2000).
3.4. Integration
Implementation of different modules was done separately and, after passing unit and component testing, the modules were integrated into one piece.
All the modules integration passed unexpectedly easy. Probably, thanks to the nature of the product and its “serial” 2-layers only design. (By “serial” we refer to the fact that the modules are invoked sequentially and only one time each. One finishes its job and then the other one starts its.)
3.5. Testing
As noted before, we performed unit testing on every class of every module. Then, component testing on the principle modules was done. Then, we tested the whole software as one piece.
Thanks to large share of time invested into requirements analysis and design, we had few, if any, problems with module separate testing, integration and combined testing. The only significant class of bugs was, of course, memory leaks, emerging from the use of C/C++ that have no memory management effective mechanism, like Java does, for example. We were capable to track and eliminate most of the bugs, and the share of time spent on testing was rather significant.
4. Product Usage
The product can be extensively used for its primary goal – FSM generation from arbitrary configuration file. This can be done in one of the next 3 ways.
4.1. Demo
We provide a GUI application to demonstrate the product capabilities.
To use demo, simply run FSMBuilder.exe, chose a configuration file, pick-up your favorite programming language(s) and click on “Generate Codes” button to generate the FSM.
Remember, of course, that there’s a format to configuration file. So, in case of either lexical, grammar or logical error, the tool will be able to pinpoint its origin, and even advise you on how to fix it… but, the GUI Demo does not include an output window for that. To, get more powerful control over FSM generation, one should use another application we provide, described below.
4.2. Tool
This is a command-line application, which receives configuration file and the path for destination files and generates the code of the FSM. The output from execution is highly informative. In case of an error, you’re given the line, the character number and the reason for the error occurrence. The tool, then, doesn’t stop, but tries to recover and continue scanning, parsing or generating the FSM.
To use tool, simply run FSMGen.exe from command line, provide it with configuration file and the path for destination files and the desired FSM is being automatically generated.
4.3. Extension
Another great benefit of the product is its open architecture.
One of the possible scenarios for product extension is creation of additional generators. To do that, the extender should be familiar with FSMDB format and learn, on example of C++ or Java generators that we provide, how to generate code from the FSM definition stored in FSMDB in a programming language of his choice.
Another case of extension is building applications that would utilize our tool, by providing it with FSM configuration file as an input and using the generated FSM directly. In other words, making our product integral part of their application. One can do so by running the tool as a separate application or, even greater then that, by incorporating our source code into user’s software. Examples for such applications might be: graphical automata modeling, model creation for model-based verification, model-based code synthesis, etc.
5. Summary
This document summarizes our work on the product, which is “The Configurable FSM generating tool”, and in short - “Configurable FSM”.
Working on the project added, particularly, to our knowledge of extensive use of Finite State Machine in different applications in Computer Science and Software Engineering.
We predict an extensive use of such tool in software design, implementation, testing, verification, and also countless more areas beyond the Computer Science and Software Engineering. Only few examples of such applications are: graphical automata modeling, model creation for model-based verification, model-based code synthesis and so on.
6. TODO
1) There can be additional generators added
for various programming languages to the distribution
2) Add switch to FSMGen for choosing
between destination programming languages, like it’s done in FSMBuilder.
3) Add output window to FSMBuilder for
informative and error messages display, like it’s done in FSMGen.
4) Extend FSMBuilder demo to a complete application.
Beyond the items listed above, the extension of our
product is, virtually, unlimited (see 4.3.Extension).
Appendix
A.
List of Terms and Abbreviations
API - Application Programming Interface
BISON - see YACC
DB - Database
DFA - Deterministic Finite Automata
FA - Finite Automata
FLEX - see LEX
FSM - Finite State Machine
GUI - Graphical User Interface
LEX - Lexical Analyzer Generator
NDFA - Non-Deterministic Finite Automata
YACC - Yet-Another-Compiler-Compiler
Appendix
B.
List of Figures
|
Figure 1 |
FSM Generation Process – software modules. |
|
Figure 2 |
Configuration File example |
|
Figure 3 |
API (Java) – class FSM. |
|
Figure 4 |
API (Java) – class FSMException. |
|
Figure 5 |
API (Java) – interface AbstractFSM |
|
Figure 6 |
API (Java) – class IDPair (“non-public” class). |
|
Figure 7 |
API (Java) – using the generated FSM through API’s class FSM instance. |
|
Figure 8 |
Scanner configuration file for the FLEX. |
|
Figure 9 |
Parser’s main method |
|
Figure 10 |
FSMDB class |
|
Figure 11 |
FSMDBManager class’s public interface. |
|
Figure 12 |
Class FSMFileGenerator of the Generator module. |
Appendix
C.
List of References
[1] “Switching and finite automata theory”, Zvi Kohavi, McGraw-Hill, 1978, 2nd Ed.
[2] “Design Patterns”, Erich Gamma, Addison-Wesley, 1997
[3] “Compiler design”, R. Wilhelm, Addison-Wesley, 1995
[4] “FLEX – GNU Project”, http://www.gnu.org/software/flex/, Free Software Foundation, 1999
[5] “BISON – GNU Project”, http://www.gnu.org/software/bison/, Free Software Foundation, 1998
[6] “Standard Template Library”, http://www.sgi.com/tech/stl/, Hewlett-Packard Company, 1994
[7] “The Source for Java(TM) Technology”, http://java.sun.com/, Sun Microsystems Inc., 1995-2002