Click here to Skip to main content
Click here to Skip to main content

Autogenerate Source Code for a Finite State Automaton Applying XML/XSLT

, 31 Aug 2005
Rate this:
Please Sign up or sign in to vote.
Shows how to generate source code for a finite state automaton described by XML applying XSLT

Introduction

Finite state automaton is useful in a couple of situations, for example: parsing protocols, tracing user input, etc. But it has a big drawback: automaton's source code is very big. It contains a lot of lines and it is hard to create and support it. This article is about how you can relieve describing automaton using XML and generate its source code applying XSLT. I used C# but you can use any other .NET language. As an example, I'm going to create a simple parser for only two text commands: "show message" and "show error".

Describe Automaton

Finite state automaton is a set of states and transitions between states. So I described this in this XML file:

<?xml version="1.0" ?>
<parser-descriptor namespace="CommandParser">
  <class-descriptor classname="Parser">
    <states varname="_state" initstate="NOTHING" >
      <state name="NOTHING">
        <input val="sS" newstate="S" />
      </state>
            
      <!-- show error or message -->
      <state name="S">
        <input val="hH" newstate="SH" />
      </state>
      <state name="SH">
        <input val="oO" newstate="SHO" />
      </state>
      <state name="SHO">
        <input val="wW" newstate="SHOW" />
      </state>
      <state name="SHOW">
        <input val=" " newstate="SHOW_space" />
      </state>
            
      <state name="SHOW_space">
        <input val="eE" newstate="SHOW_E" />
        <input val="mM" newstate="SHOW_M" />
      </state>
            
      <!-- show error -->
      <state name="SHOW_E">
        <input val="rR" newstate="SHOW_ER" />
      </state>
      <state name="SHOW_ER">
        <input val="rR" newstate="SHOW_ERR" />
      </state>
      <state name="SHOW_ERR">
        <input val="oO" newstate="SHOW_ERRO" />
      </state>
      <state name="SHOW_ERRO">
        <input val="rR" newstate="SHOW_ERROR" />
      </state>
      <state name="SHOW_ERROR">
      </state>
            
      <!-- show message -->
      <state name="SHOW_M">
        <input val="eE" newstate="SHOW_ME" />
      </state>
      <state name="SHOW_ME">
        <input val="sS" newstate="SHOW_MES" />
      </state>
      <state name="SHOW_MES">
        <input val="sS" newstate="SHOW_MESS" />
      </state>
      <state name="SHOW_MESS">
        <input val="aA" newstate="SHOW_MESSA" />
      </state>
      <state name="SHOW_MESSA">
        <input val="gG" newstate="SHOW_MESSAG" />
      </state>
      <state name="SHOW_MESSAG">
        <input val="eE" newstate="SHOW_MESSAGE" />
      </state>
      <state name="SHOW_MESSAGE">
      </state>
            
    </states>
  </class-descriptor>
</parser-descriptor>

Where:

  • <parser-descriptor> is a description for .NET namespace
  • <class-descriptor> is a description for class
  • <states> is a description for a class field for storing automaton's state
  • <state> is a description for a state
  • <input> is a description for a transition (input message and new state)

Generate Source Code

I created this simple XSLT stylesheet to convert an XML file into C# source code:

<?xml version="1.0" encoding="UTF-8" ?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="html"/>
  <!--  -->
<xsl:template match="/parser-descriptor">
<html>
<body>
<pre>
namespace <xsl:value-of select="@namespace"/>
{
<xsl:apply-templates select="class-descriptor"/>
}
</pre>
</body>
</html>
</xsl:template>

<!-- create class -->
<xsl:template match="class-descriptor">
  public class <xsl:value-of select="@classname" />
  {
    public enum States
    {
<xsl:for-each select=".//states//state" >
      <xsl:value-of select="@name" />,
</xsl:for-each>
    }
    States <xsl:value-of select=".//states//@varname" /> = 
	States.<xsl:value-of select=".//states//@initstate" />;
    
    public void Reset()
    {
      <xsl:value-of select=".//states//@varname" /> = 
	States.<xsl:value-of select=".//states//@initstate" />;
    }
    
    public States State
    {
      get
      {
        return <xsl:value-of select=".//states//@varname" />;
      }
    }

    public void InputChar(char c)
    {
      switch(<xsl:value-of select=".//states//@varname" />)
      {
<xsl:for-each select=".//states//state" >
      case States.<xsl:value-of select="@name" />:
<xsl:apply-templates select="input"/>
        throw new Exception("Invalid input character");
</xsl:for-each>
      default:
        throw new Exception("Invalid state value");
      }
    }
  }
</xsl:template>

<!-- processing of input character -->
<xsl:template match="input" >
       if (-1 != ("<xsl:value-of select="@val" />").IndexOf(c))
       {
         <xsl:value-of select="..//..//@varname" /> = 
		States.<xsl:value-of select="@newstate" />;
         return;
       }       
</xsl:template>

</xsl:stylesheet>

I created a simple C# program to use this XSLT stylesheet:

using(Stream xsltData = new FileStream(_xsltFileName, FileMode.Open))
{
  XslTransform tr = new XslTransform();
  tr.Load(new XmlTextReader(xsltData));

  tr.Transform(_xmlFileName, _resultFileName);
}

After transformation, I got a source code for my automaton:

namespace CommandParser
{
  public class Parser
  {
    public enum States
    {
      NOTHING,
      S,
      SH,
      ... and so on
    }
    States _state = States.NOTHING;
    
    public void Reset()
    {
      _state = States.NOTHING;
    }
    
    public States State
    {
      get
      {
        return _state;
      }
    }

    public void InputChar(char c)
    {
      switch(_state)
      {

        case States.NOTHING:

          if (-1 != ("sS").IndexOf(c))
          {
            _state = States.S;
            return;
          }       

          throw new Exception("Invalid input character");

        case States.S:

          if (-1 != ("hH").IndexOf(c))
          {
            _state = States.SH;
            return;
          }       

          throw new Exception("Invalid input character");

... and so on.

And at last, this is a code to check my automaton workability:

private void _textBoxCommands_TextChanged(object sender, System.EventArgs e)
{      
  Parser parser = new Parser();
  string msg = _textBoxCommands.Text;
  int length = msg.Length;

  for (int i = 0; i < length; ++i)
  {
    char c = msg[i];
    try
    {
      parser.InputChar(c);
    }
    catch(Exception ex)
    {
      return;
    }
  }
  switch(parser.State)
  {
    case Parser.States.SHOW_ERROR:
      MessageBox.Show("Error Message");
      break;
    case Parser.States.SHOW_MESSAGE:
      MessageBox.Show("Info Message");
      break;
  }
}

Conclusion

Now I can change a set of commands parsed by this automaton in a simple manner. The source code will be generated automatically. I've used this approach during the creation of a finite state automaton for tracing of user input in one of my GUI controls.

Good luck.

History

  • 1st September, 2005: Initial post

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Maxim Alekseykin
Team Leader
Russian Federation Russian Federation
MCAD
 
Now is looking for remote job.
 
- C++/C#, VB/VBA, SQL Server/Access databases.
- automatic testing, code review
- performance tuning
max.uk2005@gmail.com
-

Comments and Discussions

 
GeneralDo it for C++, ... in C++, PinmemberWREY1-Sep-05 12:18 
GeneralInteresting approach PinmemberJörgen Sigvardsson1-Sep-05 10:04 
I will make note of this article for future use. Brilliant!
 
--
An eye for an eye will only make the world blind.
GeneralSource link broken Pinmemberleppie1-Sep-05 2:02 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 1 Sep 2005
Article Copyright 2005 by Maxim Alekseykin
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid