gperf超入門

### 概要
ある特定のキーワードとマッチするかどうかを判定するようなプログラムを書く場合，力任せにマッチさせてもういのだが，効率よくマッチさせるにはハッシュ法を用いれば良い．しかし，C言語を用いるとき，自分でハッシュを実装するのはちょっと．．．という時に用いるのが[gperf](https://www.gnu.org/software/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というファイルに保存する．

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

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

```c: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`と共にコンパイルし，実行する．

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

### 実践編
基礎編では，単にマッチしたかどうかと，マッチした場合には文字列へのポインタを返していたが，gperfではマッチした時に任意の構造体へのポインタを返すことができる．
この機能を利用するには，
1. 構造体の定義
2. 構造体で使う型の定義
3. キーワードとそれに付随する属性の定義(構造体1つに対応する情報)

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

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

```c: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関数を実装する．

#### マッチプログラムの利用

```c: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`の返り値を受け取っている．基本編ではマッチした文字列へのポインタを受け取っていた．こうするためには後述するようにプログラムの自動生成時にオプションを指定する．

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

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

```shell:
>./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 *~
```