株式会社エス・スリー・フォー

XMLを用いた状態遷移

• 状態遷移表
• 状態遷移表のXMLによる表現
• 状態遷移表を駆動する
• イベント駆動型XMLパーサ

状態遷移表(SMCより抜粋)

FSM(Finite State Machine:有限状態機械)は、
アプリケーションの分析･設計において重要なパートのひとつです。非常に多くのアプリケーションが、その動作をFSMによって記述することができます。

FSMは”State Map:状態表”あるいは”State Transition
Table:状態遷移表”と呼ばれる表の形で表現されます。

“(門番のいる)ゲート”を例に、FSMを作ってみましょう。以下のようなState Mapを用意しました。

このState
Mapはゲートの制御モデルを表現しています。ゲートは2つの状態Locked(閉じている)とUnlocked(開いている)をもち、2つのイベントCoinとPassを受け付けます。

Coinイベント

門番が入場料を受け取った

Passイベント

誰かがゲートを通過した

また、ゲートには4つのアクションが定義されています。

Unlock

ゲートを開ける

Lock

ゲートを閉じる

Alarm

警報を鳴らす

ThankYou

余分なお金をもらったことに礼を言う

このState Mapの読み方は以下のとおりです:

• ゲートがLocked状態のとき:
  • Coinイベントが発生したら、Unlocked状態に遷移してUnlockアクションを起こす。
  • Passイベントが発生したら、閉じているゲートを無理矢理誰かが通過したことに対しAlarmアクションを起こす
• ゲートがUnlocked状態のとき:
  • Passイベントが発生したら、Locked状態に戻してLockアクションを起こす
  • Coinイベントが発生したら、余分なお金を頂いた事に礼を言う(ThankYouアクションを起こす)。

状態遷移表のXMLによる表現

この状態遷移表をXMLで記述してみました。

文法

まず、状態遷移表をXMLで表現するための文法をDTD(Document Type
Definition)で定義します。
これは今後いかなる状態遷移表をXMLで記述する場合でも再利用できます。

fsm.dtd : 状態遷移表の文法

<!-- Document Type Definition for 'Finite State Machine' -->

  <!ELEMENT FSM   (#PCDATA | State)* >
  <!ATTLIST FSM   name     NMTOKEN #REQUIRED>
  <!ATTLIST FSM   initial  NMTOKEN #REQUIRED>
  <!ATTLIST FSM   terminal NMTOKEN "none">

  <!ELEMENT State (#PCDATA | Event)* >
  <!ATTLIST State name  NMTOKEN  #REQUIRED>

  <!ELEMENT Event (#PCDATA)>
  <!ATTLIST Event name       NMTOKEN  #REQUIRED>
  <!ATTLIST Event transition NMTOKEN  "none">
  <!ATTLIST Event action     NMTOKEN  "none">
  

• <!ELEMENT FSM   (#PCDATA | State)* >

  <FSM>タグはその要素として任意の文字列(#PCDATA)または<State>タグを0個以上含みます。

• <!ATTLIST FSM   name     NMTOKEN #REQUIRED>
  <!ATTLIST FSM   initial  NMTOKEN #REQUIRED>
  <!ATTLIST FSM   terminal NMTOKEN "none">
        

  <FSM>タグはname(名前),initial(初期状態),terminal(停止状態)を属性に持ちます。
  name,initialは必須属性、terminalは省略時には”none”>です。

• <!ELEMENT State (#PCDATA | Event)* >
      

  <State>タグはその要素として任意の文字列(#PCDATA)または<Event>タグを0個以上含みます。

• <!ATTLIST State name  NMTOKEN  #REQUIRED>
        

  <State>タグはname(名前)を属性に持ちます。
  nameは必須属性です。

•       <!ELEMENT Event (#PCDATA)>
      

  <Event>タグはその要素として任意の文字列(#PCDATA)を0個以上含みます。

• <!ATTLIST Event name       NMTOKEN  #REQUIRED>
  <!ATTLIST Event transition NMTOKEN  "none">
  <!ATTLIST Event action     NMTOKEN  "none">
  

  <EventM>タグはname(名前),transition(次の状態),action(アクション)を属性に持ちます。
  nameは必須属性、transition,actionは省略時には”none”>です。

文法に基づいた状態遷移表

では、この文法に基づいてゲートの状態遷移表をXMLで記述します。

gate.xml : ゲートの状態遷移表

<?xml version="1.0" encoding="Shift_JIS"?>

<!DOCTYPE FSM SYSTEM "fsm.dtd">

<FSM name="Gate" initial="Locked">

  <State name="Locked">
    <Event name="Coin" action="Unlock" transition="Unlocked"/>
    <Event name="Pass" action="Alarm"/>
  </State>

  <State name="Unlocked">
    <Event name="Coin" action="ThankYou"/>
    <Event name="Pass" action="Lock" transition="Locked"/>
  </State>

</FSM>

いかがでしょう、冒頭の表がそのままXMLで表現されているのが見て取れます。

状態遷移表を駆動する

XMLで記述された状態遷移表は適当なXMLパーサで解析することで状態遷移表に定義されている状態、そしてそれぞれの状態におけるイベントとアクション、次の状態を読み出すことができます。

以下に挙げる例では、ユーザからの文字列入力をイベントとし、XMLで書かれた状態遷移表をXMLパーサでダイナミックに解析しながら状態遷移表をドライブします。

実行結果 (Bold表記はユーザ入力)

FSM : Gate
state : Locked
enter an event (Coin,Pass,exit) ? Coin
action : Unlock
state : Unlocked
enter an event (Coin,Pass,exit) ? Pass  
action : Lock
state : Locked
enter an event (Coin,Pass,exit) ? Coin
action : Unlock
state : Unlocked
enter an event (Coin,Pass,exit) ? Coin
action : ThankYou
state : Unlocked
enter an event (Coin,Pass,exit) ? Pass
action : Lock
state : Locked
enter an event (Coin,Pass,exit) ? Pass
action : Alarm
state : Locked
enter an event (Coin,Pass,exit) ? exit

以下の3つのサンプルコードはそれぞれ次のXMLパーサを利用したものです。

• MSXML (Microsoft) :
  Microsoft XML Parser 2.0

  Internet Explorer
  5.0(IE5)をインストールすると、システムディレクトリにmsxml.dllが置かれます。
  msxml.dllはIE5がXMLの解析に用いるCOMサーバで、Visual
  BasicなどのCOMクライアントをサポートする言語から利用できます。サンプルコードはVisual C++
  6.0のCOMサポート機能を用いています。

• XML4C (IBM) : XML Parser
  for C++ 3.1.0

  IBM
  alphaWorksよりダウンロードできます。
  MSXMLは実質上Windows-onlyなので、UNIX系にはXML4Cをお勧めします。
  また、Java版 XML4J も同じくalphaWorksから入手可能です。

• JAXP (Sun Microsystem) :
  Java API for XML Parsing 1.0

  Java Technology
  & XMLよりダウンロードできます。
  SunによるJava版XMLパーサです。

MSXML版

/*
 * Finite State Machine using MSXML (Microsoft XML Parser 2.0)
 */

#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <string>

#import "msxml.dll"

using namespace std;
using namespace MSXML;

/*
 * elementからattribute_nameなるアトリビュート値を取り出す
 */
inline string get_attribute(IXMLDOMElementPtr element, const char* attribute_name) {
  return (const char*)_bstr_t(element->getAttribute(attribute_name));
}

/*
 * parentの子nodeの中からattribute_nameなるアトリビュート値がkeyに一致するものを見つける
 */
IXMLDOMElementPtr find_element(IXMLDOMNodePtr parent, const char* attribute_name, const string& key) {
  IXMLDOMElementPtr element;
  for ( IXMLDOMNodePtr node = parent->firstChild; node != 0; node = node->nextSibling ) {
    if ( node->nodeType == NODE_ELEMENT ) {
      element = node;
      if ( get_attribute(element,attribute_name) == key )
        return element;
    }
  }
  return 0;
}

/*
 * ----- main -----
 */
int main(int argc, char* argv[]) {

  if ( argc != 2 ) {
    cerr << "fsm <URL for FSM>" << endl;
    return 1;
  }

  if ( FAILED(CoInitialize(0)) ) {
    cerr << "Can't initialize COM" << endl;
    return 1;
  }

  try {

    /*
     * XML Parser の生成と初期化
     */
    IXMLDOMDocumentPtr document("MSXML.DOMDocument");
    document->validateOnParse = VARIANT_TRUE; // 検証を行う
    document->async = VARIANT_FALSE;          // Parse完了までloadメソッドをブロック

    /*
     * 引数に与えられたURLで示されたXMLをロードする
     */
    document->load(argv[1]);

    /*
     * Parseエラーがあれば出力
     */
    IXMLDOMParseErrorPtr error = document->parseError;
    if ( error->errorCode != 0 ) {
      if ( error->line ) {
        cerr << "line     : " << error->line << endl;
        cerr << "position : " << error->linepos << endl;
        cerr << "source   : " << (const char*)error->srcText << endl;
      }
      cerr << "URL        : " << (const char*)error->url       << endl;
      cerr << "code       : " << error->errorCode << endl;
      cerr << "reason     : " << (const char*)error->reason    << endl;
      return 1;
    }

    /*
     * ルートエレメントを取得する
     */
    IXMLDOMElementPtr root = document->documentElement;

    /*
     * 全イベントを取り出す
     */
    set<string> event_set;
    IXMLDOMNodeListPtr events = root->getElementsByTagName("Event");
    for ( int i = 0; i < events->length; ++i ) {
      IXMLDOMElementPtr node = events->item[i];
      event_set.insert(get_attribute(node,"name"));
    }

    /*
     * 初期状態 / 終了状態 を取得する
     */
    string state_name     = get_attribute(root,"initial");
    string terminal_name  = get_attribute(root,"terminal");

    string fsm_name       = get_attribute(root,"name");
    cout << "FSM : " << fsm_name << endl;

    /*
     * 状態遷移表を駆動する
     */
    while ( state_name != terminal_name ) {

      /*
       * state_name で示される State を見つける
       */
      IXMLDOMElementPtr state  = find_element(root,"name",state_name);
      if ( state == 0 ) {
        cerr << "can't find state : " << state_name << endl;
        break;
      }

      /*
       * 現在の状態とイベント一覧を出力する
       */
      cout << "state : " << state_name << endl;
      cout << "enter an event (";
      copy(event_set.begin(), event_set.end(), ostream_iterator<string>(cout,","));
      cout << "exit) ? " << flush;

      /*
       * ユーザからのイベント入力
       */
      string event_name;
      cin >> event_name;
      if ( event_name == "exit" )
        break;
      if ( event_set.find(event_name) == event_set.end() ) {
        cerr << event_name << " is not valid." << endl;
        continue;
      }

      /*
       * event_name で示される Event を見つける
       */
      IXMLDOMElementPtr event = find_element(state,"name",event_name);
      if ( event == 0 ) {
        cerr << "can't find event : " << event_name << endl;
        break;
      }

      /*
       * アクションを実行する
       */
      string action_name = get_attribute(event,"action");
      if ( action_name != "none" )
        cout << "action : " << action_name << endl;

      /*
       * 次の状態へ遷移する
       */
      string transition_name = get_attribute(event,"transition");
      if ( transition_name != "none" )
        state_name = transition_name;
    }

  } catch ( _com_error& ex ) {
    cerr << "COM error occurred : " << ex.ErrorMessage() << endl;
  }

  CoUninitialize();
  return 0;
}

XML4C版

/*
 * Finite State Machine using XML4C (IBM XML Parser for C++ 3.0.1)
 */

#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <string>

#include <util/PlatformUtils.hpp>
#include <dom/DOM.hpp>
#include <parsers/DOMParser.hpp>
#include <sax/ErrorHandler.hpp>
#include <sax/SAXParseException.hpp>

using namespace std;

inline string transcode(const DOMString& domstr) {
  return domstr.transcode();
}

/*
 * Parse中に発生したエラーを出力する
 */
class ErrorReporter : public ErrorHandler {
  bool ok_;
public:
  ErrorReporter() : ok_(true) {}
  ~ErrorReporter() {}

  void warning(const SAXParseException& toCatch) {}
  void error(const SAXParseException& toCatch) {
    ok_ = false;
    std::cerr << "Error at file \"" << transcode(toCatch.getSystemId())
              << "\", line " << toCatch.getLineNumber()
              << ", column " << toCatch.getColumnNumber()
              << "\n   Message: " << transcode(toCatch.getMessage())
              << "\n\n";
  }

  void fatalError(const SAXParseException& toCatch) {
    ok_ = false;
    std::cerr << "Fatal Error at file \"" << transcode(toCatch.getSystemId())
              << "\", line " << toCatch.getLineNumber()
              << ", column " << toCatch.getColumnNumber()
              << "\n   Message: " << transcode(toCatch.getMessage())
              << "\n\n";
  }

  void resetErrors() {}

  bool ok() const { return ok_; }
};

/*
 * elementからattribute_nameなるアトリビュート値を取り出す
 */
inline string get_attribute(DOM_Element element, const char* attribute_name) {
  return transcode(element.getAttribute(attribute_name));
}

/*
 * parentの子nodeの中からattribute_nameなるアトリビュート値がkeyに一致するものを見つける
 */
DOM_Element find_element(DOM_Node parent, const char* attribute_name, const string& key) {
  DOM_Element element;
  for ( DOM_Node node = parent.getFirstChild(); node != 0; node = node.getNextSibling() ) {
    if ( node.getNodeType() == DOM_Node::ELEMENT_NODE ) {
      element = (DOM_Element&)node;
      if ( get_attribute(element,attribute_name) == key )
        return element;
    }
  }
  return element;
}

/*
 * ----- main -----
 */
int main(int argc, char* argv[]) {

  if ( argc != 2 ) {
    cerr << "fsm <URL for FSM>" << endl;
    return 1;
  }

  /*
   * XML Parser の生成と初期化
   */
  try {
    XMLPlatformUtils::Initialize();
  } catch ( XMLException& ex ) {
    cerr << transcode(ex.getMessage()) << endl;
    return 1;
  }
  DOMParser parser;
  ErrorReporter error;
  parser.setDoValidation(true);  // 検証を行う
  parser.setErrorHandler(&error); // エラーハンドラを設定

  /*
   * 引数に与えられたURLで示されたXMLをロードする
   */
  try {
    parser.parse(argv[1]);
    if ( !error.ok() ) {
      return 1;
    }
  } catch ( XMLException& ex ) {
    cerr << transcode(ex.getMessage()) << endl;
    return 1;
  }

  /*
   * ドキュメントを取得する
   */
  DOM_Document document = parser.getDocument();

  /*
   * ルートエレメントを取得する
   */
  DOM_Element root = document.getDocumentElement();

  /*
   * 全イベントを取り出す
   */
  set<string> event_set;
  DOM_NodeList events = root.getElementsByTagName(DOMString("Event"));
  for ( int i = 0; i < events.getLength(); ++i ) {
    DOM_Element node = (DOM_Element&)events.item(i);
    event_set.insert(get_attribute(node,"name"));
  }

  /*
   * 初期状態 / 終了状態 を取得する
   */
  string state_name     = get_attribute(root,"initial");
  string terminal_name  = get_attribute(root,"terminal");

  string fsm_name       = get_attribute(root,"name");
  cout << "FSM : " << fsm_name << endl;

  /*
   * 状態遷移表を駆動する
   */
  while ( state_name != terminal_name ) {

    /*
     * state_name で示される State を見つける
     */
    DOM_Element state  = find_element(root,"name",state_name);
    if ( state == 0 ) {
      cerr << "can't find state : " << state_name << endl;
      break;
    }

    /*
     * 現在の状態とイベント一覧を出力する
     */
    cout << "state : " << state_name << endl;
    cout << "enter an event (";
    copy(event_set.begin(), event_set.end(), ostream_iterator<string>(cout,","));
    cout << "exit) ? " << flush;

    /*
     * ユーザからのイベント入力
     */
    string event_name;
    cin >> event_name;
    if ( event_name == "exit" )
      break;
    if ( event_set.find(event_name) == event_set.end() ) {
      cerr << event_name << " is not valid." << endl;
      continue;
    }

    /*
     * event_name で示される Event を見つける
     */
    DOM_Element event = find_element(state,"name",event_name);
    if ( event == 0 ) {
      cerr << "can't find event : " << event_name << endl;
      break;
    }

   /*
    * アクションを実行する
    */
    string action_name = get_attribute(event,"action");
    if ( action_name != "none" )
      cout << "action : " << action_name << endl;

   /*
    * 次の状態へ遷移する
    */
    string transition_name = get_attribute(event,"transition");
    if ( transition_name != "none" )
      state_name = transition_name;
  }

  return 0;
}

JAXP版

/*
 * Finite State Machine using JAXP (Sun Java API for XML Parsing 1.0)
 */

import java.io.*;
import java.util.*;

import org.w3c.dom.*;
import javax.xml.parsers.*;
import org.xml.sax.*;

public class fsm {

 /*
  * elementからattribute_nameなるアトリビュート値を取り出す
  */
  private static String get_attribute(Element element, String attribute_name) {
    return element.getAttribute(attribute_name);
  }

 /*
  * parentの子nodeの中からattribute_nameなるアトリビュート値がkeyに一致するものを見つける
  */
  private static Element find_element(Node parent, String attribute_name, String key) {
    Element element = null;
    for ( Node node = parent.getFirstChild(); node != null; node = node.getNextSibling() ) {
      if ( node.getNodeType() == Node.ELEMENT_NODE ) {
        element = (Element)node;
        if ( get_attribute(element,attribute_name).equals(key) )
          return element;
      }
    }
    return element;
  }

 /*
  * ----- main -----
  */
  public static void main(String argv []) {

    if (argv.length != 1) {
      System.err.println("fsm <filename>");
      System.exit(1);
    }

    Document document;

    try {

      DocumentBuilderFactory docBuilderFactory = DocumentBuilderFactory.newInstance();
      DocumentBuilder        docBuilder        = docBuilderFactory.newDocumentBuilder();

      docBuilderFactory.setValidating(true); // 検証を行なう

     /*
      * ドキュメントを取得する
      */
      document = docBuilder.parse(new File(argv[0]));

     /*
      * ルートエレメントを取得する
      */
      Element root = document.getDocumentElement();

     /*
      * 全イベントを取り出す
      */

      TreeSet event_set = new TreeSet();
      NodeList events = root.getElementsByTagName("Event");
      for ( int i = 0; i < events.getLength(); ++i ) {
        Element node = (Element)events.item(i);
        event_set.add(get_attribute(node,"name"));
      }

     /*
      * 初期状態 / 終了状態 を取得する
      */
      String state_name     = get_attribute(root,"initial");
      String terminal_name  = get_attribute(root,"terminal");

      String fsm_name       = get_attribute(root,"name");
      System.out.println("FSM : " + fsm_name);

     /*
      * 状態遷移表を駆動する
      */
      while ( !state_name.equals(terminal_name) ) {

       /*
        * state_name で示される State を見つける
        */
        Element state  = find_element(root,"name",state_name);
        if ( state == null ) {
           System.err.println("can't find state : " + state_name);
           break;
        }

       /*
        * 現在の状態とイベント一覧を出力する
        */
        System.out.println("state : " + state_name);
        System.out.print("enter an event (");
        Iterator it = event_set.iterator();
        while ( it.hasNext() ) {
          System.out.print(it.next() + ",");
        }
        System.out.print("exit) ? ");

       /*
        * ユーザからのイベント入力
        */
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String event_name = input.readLine();
        if ( event_name.equals("exit") )
          break;
        if ( !event_set.contains(event_name) ) {
          System.err.println(event_name + " is not valid.");
          continue;
        }

       /*
        * event_name で示される Event を見つける
        */
        Element event = find_element(state,"name",event_name);
        if ( event == null ) {
          System.err.println("can't find event : " + event_name);
          break;
       }

      /*
       * アクションを実行する
       */
       String action_name = get_attribute(event,"action");
       if ( !action_name.equals("none") )
         System.out.println("action : " + action_name);

      /*
       * 次の状態へ遷移する
       */
       String transition_name = get_attribute(event,"transition");
       if ( !transition_name.equals("none") )
         state_name = transition_name;

     }

    } catch ( SAXParseException err ) {
      System.out.println("** Parsing error"
                         + ", line " + err.getLineNumber()
                         + ", uri " + err.getSystemId());
      System.out.println("   " + err.getMessage());
    } catch ( SAXException e ) {
      Exception x = e.getException();
      ((x == null) ? e : x).printStackTrace ();
    } catch (Throwable t) {
      t.printStackTrace ();
    }
  }

}

イベント駆動型XMLパーサ

XML4C(およびJAXP)は、SAXと呼ばれるイベント駆動型パーサをサポートしています。SAXパーサにはユーザが定義したイベントハンドラを食わせておきます。イベントハンドラにはあらかじめ、ドキュメント/エレメントの開始/終了など、様々なイベントが発生したときに呼び出されるメソッドを用意しておきます。

以下に示すコードは、XMLで書かれた状態遷移表をSAXパーサで解析し、FSM/State/Eventがネストした構造体を構築します。

XML4C SAX版

/*
 * Finite State Machine using XML4C/SAXParser (IBM XML Parser for C++ 3.0.1)
 */

#include <iostream>
#include <set>
#include <string>

using namespace std;

#include <util/PlatformUtils.hpp>    // PlatformUtils
#include <parsers/SAXParser.hpp>     // SAXParser
#include <sax/HandlerBase.hpp>       // HandlerBase
#include <sax/SaxParseException.hpp> // SaxParseException

/*
 * UNICODEからstringへの変換
 */
inline string transcode(const XMLCh* xmlch) {
  return XMLString::transcode(xmlch);
}

/*
 * Event
 */
struct Event {
  string name;
  string action;
  string transition;
  Event(const string& n) : name(n) {}
  Event(const string& n, const string& a, const string& t)
    : name(n), action(a), transition(t) {}
};

inline bool operator<(const Event& x, const Event& y) {
  return x.name < y.name;
}

typedef set<Event> Events;
typedef set<string> EventNames;

/*
 * State
 */
struct State {
  string name;
  Events events;
  State() {}
  State(const string& n) : name(n) {}
};

inline bool operator<(const State& x, const State& y) {
  return x.name < y.name;
}

typedef set<State> States;

/*
 * FSM
 */
struct FSM {
  string name;
  string initial;
  string terminal;
  States states;
  EventNames event_names;
};

/*
 * XMLからFSMを構築するためのハンドラ
 */
class Handler : public HandlerBase {
  State current_state;
  FSM&  fsm;
public:

  Handler(FSM& f) : fsm(f) {}

  // DocumentHandler

  // エレメント(タグ)の開始
  virtual void startElement(const XMLCh* const tag_name, AttributeList& attrs) {
    string tag = transcode(tag_name);
    if ( tag == "FSM" ) {
      fsm.name     = transcode(attrs.getValue(L"name"));
      fsm.initial  = transcode(attrs.getValue(L"initial"));
      fsm.terminal = transcode(attrs.getValue(L"terminal"));
    } else
    if ( tag == "State" ) {
      current_state.name = transcode(attrs.getValue(L"name"));
      current_state.events.clear();
    } else
    if ( tag == "Event" ) {
      current_state.events.insert(Event(transcode(attrs.getValue(L"name")),
                                        transcode(attrs.getValue(L"action")),
                                        transcode(attrs.getValue(L"transition"))));
      fsm.event_names.insert(transcode(attrs.getValue(L"name")));
    }
  }

  // エレメント(タグ)の終了
  virtual void endElement(const XMLCh* const tag_name) {
    string tag = transcode(tag_name);
    if ( tag == "State" ) {
      fsm.states.insert(current_state);
    }
  }

  // ErrorHandler

  virtual void warning(const SAXParseException& exception) {
    cout << "Err::warning";
    cout << transcode(exception.getMessage()) << endl;
  }

  virtual void error(const SAXParseException& exception) {
    cout << "Err::error:";
    cout << transcode(exception.getMessage()) << endl;
  }

  virtual void fatalError(const SAXParseException& exception) {
    cout << "Err::fatalError:";
    cout << transcode(exception.getMessage()) << endl;
  }

};

/*
 * ----- main -----
 */
int main(int argc, char* argv[]) {

  FSM fsm;

  /*
   * 初期化とFSMの構築
   */
  try {
    XMLPlatformUtils::Initialize();
    SAXParser parser;
    Handler   handler(fsm);

    parser.setDoValidation(true);
    parser.setDocumentHandler(&handler);
    parser.setErrorHandler(&handler);

    parser.parse(argv[1]);

  } catch ( const XMLException& er ) {
    cout << er.getMessage() << endl;
  }

  /*
   * 初期状態 / 終了状態 を取得する
   */
  string state_name     = fsm.initial;
  string terminal_name  = fsm.terminal;

  string fsm_name       = fsm.name;
  cout << "FSM : " << fsm_name << endl;

  /*
   * 状態遷移表を駆動する
   */
  while ( state_name != terminal_name ) {

   /*
    * state_name で示される State を見つける
    */
    States::const_iterator sit = fsm.states.find(State(state_name));
    if ( sit == fsm.states.end() ) {
      cerr << "invalid state : " << state_name << endl;
      break;
    }

    /*
     * 現在の状態とイベント一覧を出力する
     */
    cout << "state : " << state_name << endl;
    cout << "enter an event (";
    copy(fsm.event_names.begin(), fsm.event_names.end(), ostream_iterator<string>(cout,","));
    cout << "exit) ? " << flush;

    /*
     * ユーザからのイベント入力
     */
    string event_name;
    cin >> event_name;
    if ( event_name == "exit" )
      break;
    if ( fsm.event_names.find(event_name) == fsm.event_names.end() ) {
      cerr << event_name << " is not valid." << endl;
      continue;
    }

   /*
    * event_name で示される Event を見つける
    */

    Events::const_iterator eit = sit->events.find(Event(event_name));
    if ( eit == sit->events.end() ) {
      cerr << "invalid event : " << event_name << endl;
      break;
    }

   /*
    * アクションを実行する
    */
    string action = eit->action;
    if ( action != "none" )
      cout << "action : " << action << endl;

   /*
    * 次の状態へ遷移する
    */
    string transition = eit->transition;
    if ( transition != "none" )
      state_name = transition;

  }

  return 0;
}