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:
="1.0"
<parser-descriptor namespace="CommandParser">
<class-descriptor classname="Parser">
<states varname="_state" initstate="NOTHING" >
<state name="NOTHING">
<input val="sS" newstate="S" />
</state>
-->
<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>
-->
<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>
-->
<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:
="1.0" ="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>
-->
<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>
-->
<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
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Rant 
Admin