gperf超入門

概要

ある特定のキーワードとマッチするかどうかを判定するようなプログラムを書く場合，力任せにマッチさせてもういのだが，効率よくマッチさせるにはハッシュ法を用いれば良い．しかし，C言語を用いるとき，自分でハッシュを実装するのはちょっと．．．という時に用いるのがgperf．今回は，自作字句解析を実装するためにちょっと試したのでそれをまとめる．

gperfの基本

gperfを利用するには，以下の手順を踏む．

1. キーワードファイルを用意する
2. キーワードファイルから，マッチするか否かを判定するプログラムを自動生成する
3. 任意のプログラム(e.g., main)から，自動生成されたプログラムを利用する．

以下，この手順に従ってgperfを使ってみる．

基礎編

キーワードファイルの準備

3つのキーワードを一行ごとに書いたid1.keyを用意する

id1.key

%{
#include <string.h> //これが何なのかは後述するid2.keyを参照
%}
%%
ABC
DEF
XYZ

マッチプログラムの生成

以下のコマンドでプログラムを自動生成する．

>gperf id1.key > id1.c

作成したキーワードファイルをもとにプログラムを自動生成し，リダイレクトしてid1.cというファイルに保存する．

マッチプログラムの利用

自動生成したプログラムは，以下の関数を提供している．

const char* in_word_set(char*, unsigned int);

この関数は，第一引数に文字列，第二引数に文字列の長さを受け取り，作成したキーワードファイルにマッチする場合にはマッチした文字列へのポインタを返す．マッチしない場合にはNULLが返ってくる．これを踏まえて以下のプログラムを作成して実験してみる．

main1.c

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

extern const char* in_word_set(char*, unsigned int); // (1) 関数のインポート

int main(int argc, char *argv[]) {
    const char *p = NULL;
    if (argc == 1) {
        return 0;
    }

    p = in_word_set(argv[1], strlen(argv[1]));  // (2) // 関数の利用
    if (p == NULL) {
        printf("no match\n");
    } else {
        printf("hit [%s]\n", p);                 // (3) // マッチしたキーワードの出力
    }
    return 0;
}

(1)
id.cに関数in_word_setが定義されているので，externでインポートする

(2)
引数でマッチさせたいキーワードを受け取り，関数を呼び出す．マッチした場合にはpにマッチしたキーワードへのポインタが返る．

(3)
マッチしたキーワードを出力する．

このプログラムは以下のようにしてid1.cと共にコンパイルし，実行する．

>gcc -o main1 main1.c id1.c
>./main1 ABC
hit[ABC]
>./main1 XXX
no match

実践編

基礎編では，単にマッチしたかどうかと，マッチした場合には文字列へのポインタを返していたが，gperfではマッチした時に任意の構造体へのポインタを返すことができる．
この機能を利用するには，

1. 構造体の定義
2. 構造体で使う型の定義
3. キーワードとそれに付随する属性の定義(構造体1つに対応する情報)

をする必要がある．その後，基本編と同様，マッチプログラムを生成し，利用する．
上記のプロセスをベースに，構造体を定義してgperfを使ってみる．

構造体の定義

gperfで自動生成するプログラムで構造体を利用するため，構造体の定義と，そこで利用する型(手順1,2)を定義するヘッダを用意する．

id2.h

#ifndef _ID2_H_
#define _ID2_H_

#define ID 10
#define DYN 11
#define F_DIR 12
#define APPX 13

typedef enum state {
    BEGIN,
    MIDDLE,
    END,    
} LSTATE;

struct OPE {
    char *name;
    int type;
    int type2;
    LSTATE state;
};

#endif

構造体としてOPE，その中で使うenum型のLSTATEを定義する．また，後述するキーワードファイルで利用する値も#defineで定義する．

キーワードファイルの定義

以下のキーワードファイルを作成する

id2.key

%{
#include "id2.h"      // (1) ヘッダのインクルード
#include <string.h>
%}

struct OPE {          // (2)構造体の定義
    char *name;
    int type;
    int type2;      
    LSTATE state;
};

%%                    // (3)ここから，構造体の型に対応したキーワードと属性の定義
id, ID, ID, BEGIN
dyn, DYN, DYN, MIDDLE
f_dir, F_DIR, F_DIR, MIDDLE
appx, APPX, APPX, END

キーワードファイルは3つの部分に分かれている．
(1)
まずは，%{と%}に囲まれた部分．ここに書かれた文字列は，そのまま自動生成プログラムに反映される．そのため，ここで前述したヘッダファイルをインクルードする．

(2)
ここに，先ほどヘッダファイルで定義した構造体を再び定義する．先ほどの定義と重複するが，ここに定義しないと自動生成の時に失敗する．

(3)
ここから，マッチさせたいキーワードなど，具体的な値を定義していく．定義した構造体は4つのメンバーを持ち，最初が文字列，続く2つがintの値，最後がenum型のLSTATEなので，1行にカンマ区切りで具体的な値を定義する．

これを踏まえた上で，以下のmain関数を実装する．

マッチプログラムの利用

main2.c

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

extern struct OPE *in_word_set(char*, unsigned int);

int main(int argc, char* argv[]) {
    struct OPE *p;          // (1)in_word_setの返り値を受け取るポインタ
    if (argc == 1) {
        return 1;
    }

    p = in_word_set(argv[1], strlen(argv[1]));
    if (p == NULL) {
        printf("no match!\n");
    } else {
        printf("match!\n");
        printf("name  = %s\n", p->name);
        printf("type  = %d\n", p->type);
        printf("state = %d\n", p->state);               
    }

    return 0;
}

このプログラムでは，struct OPE *pとしてin_word_setの返り値を受け取っている．基本編ではマッチした文字列へのポインタを受け取っていた．こうするためには後述するようにプログラムの自動生成時にオプションを指定する．

gperf -tT id2.key > id2.c
gcc -o main2 main2.c id2.c

-tはin_word_setの返り値を構造体へのポインタにするために指定する．
-Tは，構造体の定義がid2.keyとid2.hに重複するので，自動生成するid2.cに構造体を定義しないようにするために指定する．

こうした上で，以下のように実行してみる

>./main2 xxx
no match!
>./main2 dyn
match!
name  = dyn
type  = 11
state = 1

マッチした場合に構造体へのポインタが返り，中身を指定できていることがわかる．

最後に，ここで実行したプログラムをコンパイルするためのMakefileを書いておく．

all: main1.c id1.key main2.c id2.key
        gperf id1.key > id1.c
        gcc -o main1 main1.c id1.c
        gperf -tT id2.key > id2.c
        gcc -o main2 main2.c id2.c

test: all
        ./main1 ABC
        ./main2 xxx
        ./main2 dyn

clean:
        rm -rf main1 main2 *~