SourceForge.net Logo | Home | Download | Contact Us | SourceForge.net Logo

 

 

 

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.

 

2.1.2.      FSM model

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: Start State, Pretty Good State, OK State, Very Good State, End State, etc…

 

δ – 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

 

With these extended capabilities, the FSM is referred in the software developers’ community as

Finite State Machine Design (Behavioral) Pattern [2].

 

Further in this document whenever FSM abbreviation occurs it stands for Finite State Machine Design (Behavioral) Pattern.

 

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.

 

2.2.3.      FSM machine-readable definition file

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.

3.2.            Design

Fig.1 FSM Generation Process – software modules

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 );

}

 

Fig.8 Scanner configuration file for the FLEX

FLEX generates scanner in a form of Deterministic Automata for regular expression exception.

This shows an interesting tradeoff: we used specialized FSM to generate software, which is able to generate generic FSM.

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


 

Appendix D.         Product Distribution