Entry

プログラミングメモ - 簡易有限状態機械で CGI クエリを解析してみる

2007年01月26日

あまり難しいことはやってないし小ネタなんですけど,まぁ,メモなので。

以前このサイトでウェブベースの XSLT プロセッサを C で作ったんですけれど(参照:「qune: CGI ベースの XSLT プログラムを作ってみた」),この時は自前で CGI クエリを解析するルーチンを実装したのでした。まぁ,自前といっても大したモノじゃないことは,ソースを読んでもらえれば分かると思います。URL エンコーディングもデコードしないし……。

で,この時はというと,CGI クエリをこんな感じで解析していたんですね。

  1. 準備段階として,クエリ文字列をヒープにコピーする(strdup(3))。
  2. コピーした文字列を1文字(1バイト)ずつ走査して,'&' を '\0' に置き換える(これで "key=val" な文字列を抜き出せる)。
  3. "key=val" の文字列をまた走査して,'=' を '\0' で置き換える(これで "key" と ”val” がバラバラになる)。
  4. 適当な構造体に収める(普通のリストだったと思う)。

最初にヒープにコピーしたのは,引数を const にしたかっただけなので,趣味の話です。ただ,文章で読んでもらえば分かると思うけれども,これってかなり無駄がありますよね。同じ文字列を2回も走査してますから……。実のところ,strdup(3) は malloc(3) + strlen(3) なので,実際は3回(以上)走査していることになります。スクリプト的というか,なんというか。

考えてもみたら,CGI クエリなんてのは '&' と '=' しか特別な文字はないわけで,URL エンコーディングを入れても '%' と '+' が加わるだけです。また,文字列の意味も「キー」と「値」しかありません。これくらいだったら,1回走査するだけでチャチャッとパースしたいものです。

というわけで,一回走査するだけで,「キー」と「値」を振り分ける関数を作ってみます。できたのがこちら。

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

#define BUFSIZE 1024

#define STATE_KEY 1
#define STATE_VAL 2

int
main(int argc, char *argv[])
{
    char bufKey[BUFSIZE];
    char bufVal[BUFSIZE];
    char *pKey  = bufKey;
    char *pVal  = bufVal;
    char *query = NULL;
    char *cur   = NULL;
    int state   = STATE_KEY; 

    if (argc != 2) {
        fprintf(stderr, "%s <query>", argv[0]);
        exit(0);
    } else {
        query = argv[1];
    }

    bzero(bufKey, BUFSIZE);
    bzero(bufVal, BUFSIZE);
    for (cur = query; *cur != '\0'; cur++) {
        switch (*cur) {
        case '=' :
            state = STATE_VAL;
            break;
        case '&' :
            *pKey = '\0';
            *pVal = '\0';
            printf("key = %s\n", bufKey);
            printf("val = %s\n", bufVal);
            state = STATE_KEY;
            pKey = bufKey;
            pVal = bufVal;
            break;
        default  :
            switch (state) {
            case STATE_KEY :
                *pKey = *cur;
                *pKey++;
                break;
            case STATE_VAL :
                *pVal = *cur;
                *pVal++;
                break;
            default :
                /* never comes here */
                break;
            }
            break;
        }
    }
    *pKey = '\0';
    *pVal = '\0';
    printf("key = %s\n", bufKey);
    printf("val = %s\n", bufVal);
 
    return 0;
}

ソースが汚ないのは許してください。15分で作った出来立てですから……小まめに関数に分ければ,ちょっとはマシになると思います。おそらくバグもあるので,そのつもりで見てください。ともあれ,実行すると,こんな感じで振り分けてくれます。これは,Google へのクエリ引数。

aian:~ % ./query 'hl=ja&q=hoge+foo+bar&btnG=Google+%E6%A4%9C%E7%B4%A2&lr='
key = hl
val = ja
key = q
val = hoge+foo+bar
key = btnG
val = Google+%E6%A4%9C%E7%B4%A2
key = lr
val =

for ループが文字列を1回走査するだけだってのがミソです。こういうの,状態によって振舞いを変えるときの常套句で,有限状態機械(有限オートマトン)なんて呼ばれることもあるんですよね。オートマトンはもっと複雑な解析をするときに使われる概念なので,これしきのプログラムに有限状態機械なんて言葉を当てるのもおこがましいんですが。

ここでは,STATE_KEY な状態と STATE_VAL な状態を持っていて,スタートは STATE_KEY(「キー」)の状態から始まります。'=' が見つかったら,その次は「値」が来るはずですから,状態を STATE_VAL にします。'&' か '\0' が来たら,そこで "key=val" の組み合せが終わります(状態を STATE_KEY に戻す)。これら以外の文字が来た場合は,状態によって決められたバッファに収めていきます。つまり,状態が STATE_KEY のときはキーのバッファ(bufKey)にコピーして,反対に状態が STATE_VAL のときは値のバッファ(bufVal)にコピーするといった具合。ここでは,'&' か '\0' を見付けた時点で,一旦バッファの中身をはき出してリセットしています。

今回はバッファを固定長にしたけれども,先日紹介した,ファイルから1行読み取る関数を使うなりすれば,可変長の引数にも対応できそうです(GET メソッドの場合は長さが分かるから気にする必要はないけれど(素直に strlen(3) を使えばいい))。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN