Bisonとは

Bisonは、文脈自由文法を入力として自動でパーサを作ってくれるソフトウェアである。
それぞれの規則を処理した後に実行する処理を指定することができる。

Bisonのインストール

Windows

Bison for Windows
から、Complete package, except sourcesのインストーラをダウンロードしてインストールする。
インストーラを使いたくない場合は、BinariesとDependenciesをダウンロードし、適当な同じフォルダに解凍(中身のフォルダを統合)してもよい。

Linux

Bison - GNU Project - Free Software Foundation
のDownloading Bisonの所のリンクからソースコードをダウンロードして解凍し、解凍したディレクトリ(configureなどがある)で

$ ./configure
$ make
$ make install

というコマンドを実行する。ただし、$はプロンプトを表し、コマンドには含まれない。
./configureにおいては、必要に応じてプレフィックスなどのオプションを指定するとよい。

簡単なサンプル(動作確認)

test.y

%{
/* ここにC言語の「ヘッダ」を書く */

# include <stdio.h>

int yylex(void);
void yyerror(const char *);

%}

%%
/* ここに文法を書く */

lang
    : /* 空 */
    | 'a' lang 'b'
    ;

%%
/* ここにC言語の「フッタ」を書く */

/* 次の「文字」をストリームから読み取って返す */
int yylex(void) {
    int input;
    do {
        input = getchar();
    } while (input == '\n'); /* 改行は無視する */
    if (input == EOF) return 0; /* 終了を表す */
    return input;
}

/* エラーメッセージを出力する */
void yyerror(const char *m) {
    fprintf(stderr, "%s\n", m);
}

int main(void) {
    if (yyparse() == 0) {
        puts("YES");
    } else {
        puts("NO");
    }
    return 0;
}

これをbison -d -v test.yというコマンドでBisonで処理すると、以下のファイルができる。

test.tab.c : 生成されたパーサのソースコード
test.tab.h : 生成されたパーサのソースコード
test.output : 生成されたパーサの動作が記述されたファイル(参考)

このtest.tab.cをgccなどでコンパイルし、実行すると、パーサが動作する。
このプログラムは、入力から改行を取り除いた文字列が「aが0個以上続いた後、bがちょうど同じ数続く」という文字列になっているかを判定し、
なっているならYES、なっていないならNOと出力する。

文法の書き方

Bisonで用いる文法は、非終端記号名: 記号列 [{アクション}] [| 記号列 [{アクション}] ...] ; のような形で書く。
記号列は、非終端記号や文字(終端記号)の0個以上の列である。
アクションは、その記号列を読み込み、その非終端記号として解釈するときに実行するプログラムである。
具体的には、

hoge
    : hoge fuga
    | 'a'
    ;

fuga
    : 'b'
      { puts("fuga b"); }
    | 'c'
    ;

のような感じになる。この文法は、

hogeは、hogeの後にfugaをつなげたものか、文字'a'
fugaは、文字'b'か、文字'c'

という意味である。また、fugaの'b'に対してアクションが設定されており、これにより文字'b'が読み込まれ、fugaとして解釈されるときにfuga bが出力される。(putsがマクロ定義などの影響を受けず、C言語の標準ライブラリ関数として解釈される場合)

入力全体を表す非終端記号はBisonの%startを用いて指定することができ、指定しない場合は最初に書かれている非終端記号となる。

また、アクション中において、この非終端記号の「意味」は$$と表され、この非終端記号で表される記号列の各要素の「意味」は前から順に$1, $2, ...と表わされるので、アクションを用いて各要素の「意味」からこの非終端記号の「意味」を求めるプログラムを書くことができる。

Brainf*ckコンパイラ

以下にBisonを用いたBrainf*ckコンパイラのソースコードを示す。
このプログラムは、各コマンドを表す文字に対し単純に変換結果を対応させ、コンパイルの結果は入力プログラム全体の変換結果を連結したものの前後に初期化、終了、入出力のプログラムを連結したものとなる。
ターゲットは32ビットのx86 Linuxであるが、各コマンドに対応する変換結果や前後につけるプログラムを変えることで他のターゲットにも対応できるはずである。

コマンドラインから引数を1個指定すると、それをファイル名として解釈し、そのファイルから入力を読み込もうとする。
引数が無い場合は、標準入力から入力を読み込む。
コンパイル結果は標準出力に出力される。

bf.y

%{

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

int yylex(void);
void yyerror(const char *s);

# define YYSTYPE char*

/* 分岐に使用するラベルの通し番号 */
int label_id;
/* 文字列を渡すと、それをmallocで格納した場所にコピーして返す */
char *allocate_string(const char *str);
/* 2個の文字列を連結した文字列を返し、元の文字列は開放する */
char *concat_and_free(char *s1, char *s2);

%}

/* syntax errorだけでなく、より詳しいエラーメッセージを吐かせる */
/* bison 3用 */
/* %define parse.error verbose */
/* bison 2.4.1用 */
%error-verbose

/* 構文解析中の場所の追跡を有効にする */
%locations

/* 構文解析前に実行する処理を記述する */
%initial-action {
    /* ラベル番号を初期化する */
    label_id = 0;
    /* 解析中の位置を初期化する */
    yylloc.last_line = yylloc.first_line = 1;
    /* 文字を読み込んだ時にインクリメントするので、列番号は0に初期化する */
    yylloc.last_column = yylloc.first_column = 0;
}

/* 解析を開始する非終端記号を指定する */
%start program

%%

/* プログラム全体 */
program
    : command_list
        {
            /* コマンド列の前に出力するデータ */
            char *prorogue = allocate_string(
                "\t.text\n"
                "\t.globl main\n"
                "main:\n"
                "\txorl %esi, %esi\n"
            );
            /* コマンド列の後ろに出力するデータ */
            char *epilogue = allocate_string(
                "\tmovl $1, %eax\n"
                "\tmovl $0, %ebx\n"
                "\tint $0x80\n"
                "\tret\n"
                "\n"
                "read_byte:\n"
                "\tpushl $0\n"
                "\tmovl $3, %eax\n"
                "\tmovl $0, %ebx\n"
                "\tmovl %esp, %ecx\n"
                "\tmovl $1, %edx\n"
                "\tint $0x80\n"
                "\tpop %eax\n"
                "\tmovb %al, memory(%esi)\n"
                "\tret\n"
                "\n"
                "write_byte:\n"
                "\tmovb memory(%esi), %al\n"
                "\tpushl %eax\n"
                "\tmovl $4, %eax\n"
                "\tmovl $1, %ebx\n"
                "\tmovl %esp, %ecx\n"
                "\tmovl $1, %edx\n"
                "\tint $0x80\n"
                "\tpop %eax\n"
                "\tret\n"
                "\n"
                "\t.lcomm memory, 65536\n"
            );
            char *result = concat_and_free(prorogue, concat_and_free($1, epilogue));
            /* コンパイル結果を出力する */
            fputs(result, stdout);
            free(result);
            $$ = NULL;
        }
    ;

/* コマンドが0個以上繋がったもの */
command_list
    : /* 空 */
        {
            $$ = allocate_string("");
        }
    | command_list command
        {
            $$ = concat_and_free($1, $2);
        }
    ;

/* 各コマンド */
command
    : '+'
        {
            $$ = allocate_string("\tincb memory(%esi)\n");
        }
    | '-'
        {
            $$ = allocate_string("\tdecb memory(%esi)\n");
        }
    | '>'
        {
            $$ = allocate_string("\tincw %si\n");
        }
    | '<'
        {
            $$ = allocate_string("\tdecw %si\n");
        }
    | ','
        {
            $$ = allocate_string("\tcall read_byte\n");
        }
    | '.'
        {
            $$ = allocate_string("\tcall write_byte\n");
        }
    | '[' command_list ']'
        {
            char buffer[256], *prorogue, *epilogue;
            int start_label = label_id++;
            int end_label = label_id++;
            sprintf(buffer,
                "\tcmpb $0, memory(%%esi)\n"
                "\tjnz L%d\n"
                "\tjmp L%d\n"
                "L%d:\n", start_label, end_label, start_label);
            prorogue = allocate_string(buffer);
            sprintf(buffer,
                "\tcmpb $0, memory(%%esi)\n"
                "\tjz L%d\n"
                "\tjmp L%d\n"
                "L%d:\n", end_label, start_label, end_label);
            epilogue = allocate_string(buffer);
            $$ = concat_and_free(concat_and_free(prorogue, $2), epilogue);
        }
    ;

%%

FILE *infp;

int yylex(void) {
    static char commands[] = "+-><[],.";
    for(;;) {
        /* 文字の読み込み */
        int input = getc(infp);
        if (input == EOF) {
            /* 入力終了時には0を返す */
            return 0;
        }
        /* 位置の更新 */
        if (input == '\n') {
            /* 次の行に行く */
            yylloc.last_line = ++yylloc.first_line;
            yylloc.last_column = yylloc.first_column = 0;
        } else {
            /* 次の文字に行く */
            yylloc.last_column = ++yylloc.first_column;
        }
        /* コマンドかどうかを判定 */
        if (strchr(commands, input) != NULL) {
            /* 有効なコマンドなら構文解析器に渡す */
            yylval = NULL;
            return input;
        } else {
            /* その他の文字(コメント)は捨てる */
        }
    }
}

void yyerror(const char *s) {
    fprintf(stderr, "%s at line %d, column %d\n", s, yylloc.first_line, yylloc.first_column);
}

/* バッファを確保し、そこに引数で与えられた文字列をコピーして返す */
char *allocate_string(const char *str) {
    char *buffer = malloc(sizeof(char) * (strlen(str) + 1));
    if (buffer == NULL) {
        yyerror("malloc failed");
        exit(1);
    }
    strcpy(buffer, str);
    return buffer;
}

/* バッファを確保し、str1とstr2を連結した文字列をそこにコピーして返す。
 * str1とstr2が指す領域は開放される。 */
char *concat_and_free(char *str1, char *str2) {
    size_t len1 = strlen(str1);
    size_t len2 = strlen(str2);
    char *buffer = malloc(sizeof(char) * (len1 + len2 + 1));
    if (buffer == NULL) {
        yyerror("malloc failed");
        exit(1);
    }
    strcpy(buffer, str1);
    strcpy(buffer + len1, str2);
    free(str1);
    free(str2);
    return buffer;
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        infp = stdin;
    } else {
        infp = fopen(argv[1], "r");
        if (infp == NULL) {
            fputs("input file open failed\n", stderr);
            return 1;
        }
    }
    yyparse();
    if (argc >= 2) fclose(infp);
    return 0;
}

Brainf*ck派生言語のコンパイラを作る

このプログラムを利用して、各コマンドを単純に別の文字列で置き換えたBrainf*ck派生言語のコンパイラを作ることを考える。
単純に考えると、yylex()関数で入力されたコマンドをそのまま構文解析器に渡しているが、
ここをコマンドとして用いる文字列を読み込んだらそのコマンドを構文解析器に渡すプログラムにするとよい。

他の部分は共通なので、yylex()関数および複数文字からなるコマンドに対応したyyerror()関数のみを載せる。

bf2.y

int yylex(void) {
    static char commands[] = "+-><[],.";
    static const char *command_str[8] = {
        "阿澄佳奈",
        "水橋かおり",
        "喜多村英梨",
        "井口裕香",
        "田村ゆかり",
        "堀江由衣",
        "佐藤利奈",
        "花澤香菜"
    };
    int command_pos[8];
    int i, j;
    int loc_log[64][2];
    int loc_log_head = 0;
    int loc_log_max = sizeof(loc_log) / sizeof(loc_log[0]);
    for (i = 0; i < 8; i++) command_pos[i] = 0;
    for(;;) {
        /* 文字の読み込み */
        int input = getc(infp);
        if (input == EOF) {
            /* 入力終了時には0を返す */
            return 0;
        }
        /* 位置の更新 */
        if (input == '\n') {
            /* 次の行に行く */
            yylloc.last_line++;
            yylloc.last_column = 0;
        } else {
            /* 次の文字に行く */
            yylloc.last_column++;
        }
        loc_log[loc_log_head][0] = yylloc.last_line;
        loc_log[loc_log_head][1] = yylloc.last_column;
        loc_log_head = (loc_log_head + 1) % loc_log_max;
        /* コマンドかどうかを判定 */
        for (i = 0; i < 8; i++) {
            if ((unsigned char)command_str[i][command_pos[i]] == input) {
                command_pos[i]++;
                if (command_str[i][command_pos[i]] == '\0') {
                    int loc_index;
                    /* 有効なコマンドを読み込んだ */
                    /* トークンの開始位置を設定する */
                    loc_index = loc_log_head - command_pos[i];
                    while (loc_index < 0) loc_index += loc_log_max;
                    yylloc.first_line = loc_log[loc_index][0];
                    yylloc.first_column = loc_log[loc_index][1];
                    /* 各コマンドの判定状態をリセットする */
                    for (j = 0; j < 8; j++) command_pos[j] = 0;
                    /* 構文解析器に渡す */
                    yylval = NULL;
                    return commands[i];
                }
            } else if (command_pos[i] > 0) {
                /* このコマンドは実はj文字後から始まっていたかもしれない */
                for (j = 1; j <= command_pos[i]; j++) {
                    /* まず読み込んだ文字が矛盾しないかを判定する */
                    if ((unsigned char)command_str[i][command_pos[i] - j]  == input) {
                        int ok = 1;
                        int k;
                        /* 今の状態から読み込んできた文字がわかるので、矛盾しないかを判定する */
                        for (k = 1; command_pos[i] - j - k >= 0; k++) {
                            if (command_str[i][command_pos[i] - j - k] != command_str[i][command_pos[i] - k]) {
                                ok = 0;
                                break;
                            }
                        }
                        if (ok) break;
                    }
                }
                command_pos[i] = command_pos[i] - j + 1;
            }
        }
    }
}

void yyerror(const char *s) {
    fprintf(stderr, "%s at %d:%d-%d:%d\n", s,
        yylloc.first_line, yylloc.first_column,
        yylloc.last_line, yylloc.last_column);
}

各コマンドをcommand_posに格納しておくことで、ここを変えるだけで様々なコマンドに対応できるようにしている。
そして、入力された文字列がそれぞれのコマンドになったかどうかを平行で判定している。
ここで、「一致しなかったら単純に各コマンドの先頭に戻る」というアルゴリズムにしてしまうと、
例えばabを探したい時にaabという入力が来ると、2個目のaでリセットされ、次のbと探したい文字列の先頭のaを比較してしまい、abがあるのに見逃してしまう。
そこで、そのコマンドが始まったかもしれないと考える位置を必要最低限だけずらすことで、このような見逃しが起こらないようにしている。

ただし、このプログラムでは、コマンドの集合が語頭符号になっていない、すなわち例えばbaとbaaが両方コマンドの集合に含まれている場合は、短い方のコマンド(この場合ba)が読み込まれた時点ですぐに構文解析器に渡してしまうので、うまく処理できない可能性がある。

Brainf*ck派生言語のコンパイラを改良する

先ほどのプログラムでBrainf*ck派生言語を作ることができたが、非常に処理が重くなってしまった。
これは、コマンドが一致しなかった時にわざわざループを回して開始位置の候補をどれだけ進めるべきかを調べているためであると考えられる。
よく考えると、この部分でどれだけ進めるかは、今コマンドのどこと比較しているかと入力された文字だけから決まるはずである。
そこで、事前に調べてテーブルに格納することで、処理を高速化することができた。

変更した関数のみを載せる。

bf3.y

void initialize_table(const char *command_str, int command_next[][256]) {
    int command_pos, input;
    for (command_pos = 0; command_str[command_pos] != '\0'; command_pos++) {
        for (input = 0; input < 256; input++) {
            if ((unsigned char)command_str[command_pos] == input) {
                /* 一致 */
                command_next[command_pos][input] = command_pos + 1;
            } else if (command_pos == 0) {
                /* かすってすらいない */
                command_next[command_pos][input] = 0;
            } else {
                int i;
                /* このコマンドは実はi文字後から始まっていたかもしれない */
                for (i = 1; i <= command_pos; i++) {
                    /* まず読み込んだ文字が矛盾しないかを判定する */
                    if ((unsigned char)command_str[command_pos - i]  == input) {
                        int ok = 1;
                        int j;
                        /* 今の状態から読み込んできた文字がわかるので、矛盾しないかを判定する */
                        for (j = 1; command_pos - i - j >= 0; j++) {
                            if (command_str[command_pos - i - j] != command_str[command_pos - j]) {
                                ok = 0;
                                break;
                            }
                        }
                        if (ok) break;
                    }
                }
                command_next[command_pos][input] = command_pos - i + 1;
            }
        }
    }
}

int yylex(void) {
    static char commands[] = "+-><[],.";
    static const char *command_str[8] = {
        "阿澄佳奈",
        "水橋かおり",
        "喜多村英梨",
        "井口裕香",
        "田村ゆかり",
        "堀江由衣",
        "佐藤利奈",
        "花澤香菜"
    };
    static int command_next[8][64][256]; /* 2番めの値が文字列の最大長 */
    static int command_initialized;
    int command_pos[8];
    int i, j;
    int loc_log[64][2];
    int loc_log_head = 0;
    int loc_log_max = sizeof(loc_log) / sizeof(loc_log[0]);
    if (!command_initialized) {
        for (i = 0; i < 8; i++) initialize_table(command_str[i], command_next[i]);
        command_initialized = 1;
    }
    for (i = 0; i < 8; i++) command_pos[i] = 0;
    for(;;) {
        /* 文字の読み込み */
        int input = getc(infp);
        if (input == EOF) {
            /* 入力終了時には0を返す */
            return 0;
        }
        /* 位置の更新 */
        if (input == '\n') {
            /* 次の行に行く */
            yylloc.last_line++;
            yylloc.last_column = 0;
        } else {
            /* 次の文字に行く */
            yylloc.last_column++;
        }
        loc_log[loc_log_head][0] = yylloc.last_line;
        loc_log[loc_log_head][1] = yylloc.last_column;
        loc_log_head = (loc_log_head + 1) % loc_log_max;
        /* コマンドかどうかを判定 */
        for (i = 0; i < 8; i++) {
            command_pos[i] = command_next[i][command_pos[i]][input];
            if (command_str[i][command_pos[i]] == '\0') {
                int loc_index;
                /* 有効なコマンドを読み込んだ */
                /* トークンの開始位置を設定する */
                loc_index = loc_log_head - command_pos[i];
                while (loc_index < 0) loc_index += loc_log_max;
                yylloc.first_line = loc_log[loc_index][0];
                yylloc.first_column = loc_log[loc_index][1];
                /* 各コマンドの判定状態をリセットする */
                for (j = 0; j < 8; j++) command_pos[j] = 0;
                /* 構文解析器に渡す */
                yylval = NULL;
                return commands[i];
            }
        }
    }
}