December 23, 2004

mallocしない正規表現

H8のようなマイコンで動く、mallocしない、つまり思わぬところからメモリを確保することのない正規表現ライブラリをこしらえてみました。動機はH8でもネットワークと直結できる今のご時世、HTTPのヘッダ解析すらマイコンでしなければならないわけですが、それをだらだらと書くのは鬱というものだろうということでがんばってみました。

特徴は、はじめにメモリをスタックから確保し、それ以上のメモリが必要になった場合はエラーをはいてとまるようにしてあります。つまり事前に試行実験をしておいてあらかじめメモリがどの程度必要か見極めさえすればそれ以上のメモリは要求されないので、マイコンなどのメモリが極端に少ないアプリケーションにはうってつけでないかと思います(逆にそこまでして正規表現使いたいかといわないでください…)。

ダウンロード・機能・使い方などは以下をどうぞ。

使える正規表現の記法ですが、Rubyの記法を採用していますが、機能は完全ではありません。今後機能を拡張する予定ですが、現在できることは

• 文字クラス、[a-z]のように表現、否定も^で可能
• 特殊文字

  ¥s

  空白文字、[¥n¥t¥r¥f]

  ¥S

  空白文字以外

  ¥d

  数字、[0-9]

  ¥D

  数字以外

  ¥h

  16進文字、[0-9A-Fa-f]

  ¥H

  16進文字以外

  ¥w

  半角の通常文字、[0-9A-Za-z_]に相当

  ¥W

  半角の通常文字以外

• 繰り返し指定

  *

  0回以上

  ?

  0回または1回

  +

  1回以上

  {m}

  m回

  {m,}

  m回以上

  {m,n}

  m回以上、n回以下

• 回数指定における非欲張りモード、*?とか{m,n}?のように回数指定のうしろに?で表現
• OR、|で表現
• グルーピング、(hoge)のように表現
• バックリファレンス、¥1のように表記
• バックリファレンスを想定しないグルーピング、(?hoge)のように表記
• 微妙な2byte文字への対応(ソースをみていただければ意味がわかると思います、もちろん文字コード変換などはしていません…)

といったことが可能です。

使い方はアーカイブ内のtest.cやコメントを参照してください。要約すると

な感じです。NODE_MAXは遷移表のノードの最大数、SUBMATCH_MAXはバックリファレンスの最大個数、STACK_SIZEはマッチ時の使用メモリの大きさを決めています。

実装ですが、NFAな遷移表を作ってゴリゴリスタックでマッチさせています。

ちなみにこの正規表現ライブラリを使用・転載については今のところCreative Commonsのライセンスにおける『帰属 - 非営利 - 同一条件許諾』とします。条件にあるとおり改変は自由にやっていただいてけっこうですが、その成果なども教えていただけるとうれしい限りです。
ダウンロードはこちらから。

とりあえず、これを使ってマイコンで動くXMLのSAXパーサでもこしらえるか、スクリプト言語でも実装するかを考えています。