Ragel

http://www.cs.queensu.ca/~thurston/ragel/

Ragel は、ステートマシンコンパイラの一種で、パーサジェネレータとして使われることが多い。その実例として、Mongrel や Hpricot がある。

パーサジェネレータとして Ragel を使う利点は、以下の通り。

• プロトコルやデータフォーマットを正確にパーズできる
• その結果、セキュアなソフトウェアが作れる
• 外部ライブラリに依存しないコードができる
• ものすごく速い

特に HTTP server など、速度が求められるサーバを書くときに便利なことがわかる。

参考: http://www.zedshaw.com/tips/ragel_state_charts.html

ここでは、簡単な例としてドメイン名のパーザを作ってみよう。ホスト言語は C で。

まずは、Ragel 6.0 をインストールする。
OSX の場合、MacPorts でインストールできるものは少し古いので、Ragel のページ の下のほうから ragel-6.0.tar.gz を入手し、インストールする。

$ ./configure
$ make
$ sudo make install

ステートマシンの定義は、こんな感じに書ける。

alnumhyphen = alnum | "-";
label = alnum (alnumhyphen* alnum)?;
domain = label ("." label)*;
main := domain;

BNF っぽくてわかりやすい。
これをコンパイルすると、

こんなステートマシンができあがるわけだ。(Graphviz で画像化できる)

この定義を yacc のように C のソースに埋め込んで、domain.rl というファイル名で保存する。

#include <stdio.h>
#include <string.h>

%%{
  machine domain_parser;
  
  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;
  
  write data;
}%%

#define BUFSIZE 1024

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;
  const char* begin = NULL;
  char buf[BUFSIZE];
  
  printf("*** %s\n", data);
  
  %% write init;
  %% write exec;
}

int main(int argc, char** argv)
{
  parse("www.example.org");
  parse("www-host.example.org");
  parse("-www.example.org");
  parse("ww-.example.org");
  return 0;
}

とりあえず、実行してみよう。

$ ragel -C domain.rl
$ gcc -o domain domain.c
$ ./domain
*** www.example.org
www
example
org
*** www-host.example.org
www-host
example
org
*** -www.example.org
! parse error
*** ww-.example.org
! parse error

それぞれのドメイン名をパーズして、要素に分解できていることがわかる。(ラベルの最初か最後にハイフンがあるものはエラー)
それでは、具体的に Ragel の定義を見ていこう。

%%{
  machine domain_parser;
  
  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;
  
  write data;
}%%

Ragel の定義は、%%{ から }%% までの間に書いていく。

  machine domain_parser;

まず、ステートマシン名を宣言する。(必須)

  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }
  action error { puts("! parse error"); }

ここでは、アクションを定義している。
Ragel には、任意の状態遷移の前後にアクション (任意のコード) を実行できるという特徴がある。アクションの中では、fpc で現在のポインタ位置を参照できるので、それを利用して必要なところをキャプチャしていくわけだ。

  alnumhyphen = alnum | "-";
  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;
  domain = label ("." label)*;
  main := domain @!error;

ステートマシンの定義は、Ragel 言語という正規言語 (regular language) で書く。alnum は組み込みのステートマシンで、[0-9a-zA-Z] に相当する。

label の定義には、アクションが使われている。

  label = (alnum (alnumhyphen* alnum)?) >begin_label %end_label;

こう書くと、label にマッチする直前に begin_label が、直後に end_label が呼び出される。
ここで、もう一度アクションの定義を確認してみると、

  action begin_label { begin = fpc; }
  action end_label {
    strncpy(buf, begin, fpc-begin);
    buf[fpc-begin] = 0;
    puts(buf);
  }

begin_label が呼ばれたときに begin にその時点の fpc を保存しておき、end_label では begin から fpc までの文字列を切り出して表示していることがわかる。これで、正規表現のキャプチャと同じことができる。

さらに、main の定義を見てみる。

  main := domain @!error;

こう定義しておくと、状態遷移にエラーが起きたときに error アクションを呼び出してくれる。
最後に、

  write data;

で、ここにステートマシンの定義コードを出力する。
ホストプログラムの本体を見ていこう。

#define BUFSIZE 1024

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;
  const char* begin = NULL;
  char buf[BUFSIZE];
  
  printf("*** %s\n", data);
  
  %% write init;
  %% write exec;
}

int main(int argc, char** argv)
{
  parse("www.example.org");
  parse("www-host.example.org");
  parse("-www.example.org");
  parse("ww-.example.org");
  return 0;
}

パーザ部分は、parse 関数であることがわかる。

void parse(const char* data)
{
  const char* p = data;
  const char* pe = data + strlen(data);
  const char* eof = pe;
  int cs;

Ragel では、用途ごとに変数名が決められているので、ステートマシンを実行するスコープに、以下の変数をあらかじめ定義しておく必要がある。

data	入力データ
p	データの最初。通常は data をセットしておく。
pe	データの最後。通常は data + strlen(data) をセットしておく。
eof	入力の最後を示す。通常は pe と同じでよい。
cs	現在の状態

そして、

  %% write init;
  %% write exec;

で、ステートマシンの初期化コードと実行コードを出力する。

$ ragel -C domain.rl

コンパイルしてできる domain.c の中を見てみると、

write data;
write init;
write exec;

の部分が、ステートマシンのコードに置き換えられている様子がわかる。

IRC プロトコルパーザを含むサンプルを置いておきます。
http://limechat.net/sample/ragel_samples.zip