第十ニ報：bison を使ってみる

　何年か前に単純な興味からコンパイラ（Ａ．Ｖ．エイホ、Ｒ．セシィ、Ｊ．Ｄ．ウルマン著、原田賢一訳。麻宮騎亜の漫画の方ではない）という本を読んだことがあるのですが、途中から yacc, lex といった解析プログラム作成プログラムの話になって「プログラム持っとらんけん実践できんやないの」とやるせなくなったことがあります。

　で、Cygwin に yacc, lex の上位バージョンである bison, flex が入ってることが分かったので、その bison を使ってみることにしました。折角タダで用意してくれているので、info bison を読んでやってみることにしました。

　今回のプログラマの友はその覚書のようなものです。bison を使おうと思ってるけど尻込みしている人の参考資料にでもなれば幸いです。

（註：用語には無頓着なので不正確なことがあります）

1. bison とは？
2. 構文解析の基本知識
   1. トークン解析
   2. 構文解析
   3. 優先順位と結合規則
   4. BNF
3. bison インプットの概略
   1. C の宣言文
   2. bison の宣言文
   3. 文法規則
   4. C の追加コード
4. 具体例
   1. 後置式計算機
   2. 普通の計算機
   3. エラー訂正
   4. トークン所在地の利用

１．bison とは？

　bison はパーサ（parser）生成プログラムです。パーサというのは、構文解析を行うもののことです。bison はそのパーサを C のコードとして出力します。

　パーサ生成プログラムとして有名な yacc の上位互換プログラムにあたります。

２．構文解析の基本知識

　コンパイラやインタプリタ、スクリプトエンジンなどを作る場合、プログラムのソースを解析する必要があります。この解析は大まかに２種類からなり、１つはトークン解析、もう１つは構文解析です。

２−１．トークン解析

　トークンとは、プログラムを構成する単位のことです。これ以上分けられない、最小単位のトークンを終端トークンと呼びます。

　トークン解析は、この終端トークンを切り出す作業のことです。

　終端トークンはこれ以上分けられないものの、意味的な値（付加情報）を持つことが出来ます。例えば「数」という終端トークンを考えた場合、45 も 892 もどちらも「数」ですが異なるものです。その違いを意味的な値という形で表現します。

　トークン解析を行うプログラムをスキャナ（レキシカルアナライザ）と呼びます。スキャナ生成プログラムには lex や flex があります。

２−２．構文解析

　構文解析とは、非終端トークンの解析作業のことです。

　非終端トークンは終端トークンや非終端トークンの０個、１個または複数個によって定義されるトークンです。トークンの組み合わせにその組み合わせ方に応じた意味を持たせたもの、ということもできます。非終端トークンの定義のことを、その言語の文法と呼びます。

　例えば、終端トークンとして「数」と「加算記号」と「乗算記号」を考えた時、「式」という非終端トークンは「「数」または「式」「加算記号」「式」または「式」「乗算記号」「式」」と定義できます。「「数」「乗算記号」「数」「加算記号」「数」」というものがあれば、

「「数」「乗算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「乗算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「乗算記号」「式」「加算記号」「数」」
　　「式」「乗算記号」「式」→「式」
「「式」「加算記号」「式」」
　　「式」→「式」
「「式」「加算記号」「式」」
　　「式」「加算記号」「式」→「式」
「「式」」

という具合に解析することにより、全体として１つの「式」になっていることが分かります。

　構文解析を行うプログラムをパーサと呼びます。パーサ生成プログラムには yacc や bison があります。

２−３．優先順位と結合規則

　よく考えてみると、上の解析は

「「数」「乗算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「乗算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「乗算記号」「式」「加算記号」「数」」
　　「数」→「式」
「「式」「乗算記号」「式」「加算記号」「式」」
　　「式」「加算記号」「式」→「式」
「「式」「乗算記号」「式」」
　　「式」「乗算記号」「式」→「式」
「「式」」

という順番で行うことも出来ます。即ち、真ん中の「式」を先に左と右のどちらにくっつけて評価するか、ということです。

　しかし、四則演算の規則に従うならば、乗算は常に加算よりも先に行わなければなりません。したがって、真ん中の「式」は「乗算記号」のある側にくっつけて評価する必要があるのです。

　このように、くっつける（結合する）順番が演算子の種類によって決まるとき、その順番を演算子の優先順位と呼びます。

　では、優先順位が同じ演算子同士ではどうでしょうか。

　例えば、終端トークンとして「数」と「加算記号」と「減算記号」を考え、非終端トークン「式」を「「数」または「式」「加算記号」「式」または「式」「減算記号」「式」」と定義した場合、「「数」「減算記号」「数」「加算記号」「数」」は

「「数」「減算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「減算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「減算記号」「式」「加算記号」「数」」
　　「式」「減算記号」「式」→「式」
「「式」「加算記号」「式」」
　　「式」→「式」
「「式」「加算記号」「式」」
　　「式」「加算記号」「式」→「式」
「「式」」

と

「「数」「減算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「減算記号」「数」「加算記号」「数」」
　　「数」→「式」
「「式」「減算記号」「式」「加算記号」「数」」
　　「数」→「式」
「「式」「減算記号」「式」「加算記号」「式」」
　　「式」「加算記号」「式」→「式」
「「式」「減算記号」「式」」
　　「式」「減算記号」「式」→「式」
「「式」」

の２通りの解析順が考えられます。

　しかし、3 - 1 + 2 (= 4) は (3 - 1) + 2 (= 4) であって 3 - (1 + 2) (= 0) ではないので、真ん中の「式」は左に結合して評価しなければなりません。

　このように、同じ優先順位の演算子にはさまれている場合は、その演算子の種類に応じて決められた方向に結合することになります。このどちらに結合するかという規則のことを、演算子の結合規則と呼びます。

　単純に非終端トークンの定義を与えただけでは解析順が２通り考えられる場合がありますが、優先順位と結合規則によってこの曖昧さを除くことが出来るわけです。

２−４．BNF

　上で書いたような文法を記述する表現法（これ自身も文法を持っているわけですが）として、bison では BNF（Backus-Naur Form）をベースとした亜種を採用しています。

　BNF では、非終端トークンの定義は ::= を挟んで指定します。定義が複数ある場合はバーテクス ( | ) で区切ります。

　例えば、終端トークンとして「数」と「加算記号」を考える時、非終端トークン「式」は

<式> ::= <数> | <式> <加算記号> <式>

と表現されます。トークンの名前はメタ変数と呼ばれ、< > で囲みます。

　これに対し、bison ではメタ変数を < > で囲むことはなく、さらに ::= の代わりにコロン（ : ）を使います。

３．bison インプットの概略

　bison のインプットは次のように構成されています。

%{
C の宣言文
%}

bison の宣言文

%%

文法規則

%%

C の追加コード

　bison の入力ファイルには識別子 .y をつけます。bison を実行すると、識別子の部分が .tab.c に変わった C のソースファイルが出力されます。

　また、/* ... */ の形でコメント（インプットと無関係な文字列）を書くことが出来ます。

３−１．C の宣言文

　出力ファイルの先頭に出力される C コードです。%{ と %} と書かれた行で囲みます。

　通常、#include, #define 文や関数のプロトタイプ宣言などを書いておきます。

３−２．bison の宣言文

　bison 用の宣言文を書きます。

　宣言は % で始まる命令を使って行います。

　%{ 〜 %} も実のところは命令の１種で、３−１と３−２の順番は特に関係ないようです。%% は３−１，２、３−３、３−４を分ける「区切り」のようで、３−４がない場合は最後の %% は省略できるようです。

%union {
　型 型識別子;
　[型 型識別子; ...]
}

　意味的な値の型とその識別子を宣言します。

%token [<型識別子>] 識別子 [エイリアス文字列] [識別子 ...]

　指定した識別子が終端トークンの名前であることを宣言します。文字列（ダブルクオーテーションで囲まれたもの）を使って別名をつけることができます。

　%union で宣言した型に結びつけることもできます。また、型識別子として演算子を表す operator を使うことができます。

%type <型識別子> 識別子 [識別子 ...]

　指定した識別子が非終端トークンの名前であり、指定した型を持つことを宣言します。

　型識別子は %union で宣言したものか、operator です。

%left 識別子 [識別子 ...]

　指定した識別子の結合規則が左結合であることを宣言します。

%right 識別子 [識別子 ...]

　指定した識別子の結合規則が右結合であることを宣言します。

%nonassoc 識別子 [識別子 ...]

　指定した識別子の結合規則が必要になるとエラーになることを宣言します。

　識別子の優先順位は、%left, %right, %nonassoc 宣言の順番によって指定します。インプットの下の方に書かれたものの方が優先順位が高くなります。同じ %left, %right, %nonassoc 宣言内にある識別子同士の優先順位は同じです。

３−３．文法規則

　BNF に付加情報を付けた形で文法を記述します。

非終端トークン識別子: 文法規則 [%prec 識別子] [{ アクション }] [| 文法規則 ...] ;

　%prec は、指定した識別子と同じ優先順位、結合規則をその文法規則に適用させるものです。

　アクションは、対応する文法規則が適用された時に実行される C コードです。

　詳しくは４．具体例のところで話します。

３−４．C の追加コード

　出力ファイルの一番最後に出力される C コードです。main 関数など、必要な処理をここに書くことが出来ます。つまり、簡単なプログラムなら bison の出力ファイルをそのままコンパイルするだけで済むことがあります。

　主にはトークン解析コードを書くことになります。

４．具体例

　いくつかの具体例を使って、bison の使い方を見ていきます。

４−１．後置式計算機

　後置式（逆ポーランド記法）を使った計算機を作ります。

　後置式では、演算子を被演算要素を並べた後に置きます。例えば、2 + 3 は後置式では 2 3 + になります。

　後置式は優先順位や結合規則を必要としないのが特徴です。つまり、%left, %right, %nonaccoc を使わなくても作れるのです。

・ C の宣言文

%{

#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define YYSTYPE double

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

%}

　インクルード文は C の追加コードのために行っています。関数のプロトタイプ宣言もです。

　問題は YYSTYPE の宣言です。これは、意味的な値の型が１種類しかない場合に適用される型を表します。省略すると int になります。今回は普通の小数演算を行いたいので、double にしておきます。

　typedef でないのは、YYSTYPE が定義されてるかどうかで #ifndef を使った分岐（省略された場合の処理）を行うからです。const char* など、typedef でないと困りそうなもの（複数の終端トークンからなる）は、一旦 typedef してから #define するといいでしょう。

・ bison の宣言文

%token NUM

　NUM が終端トークンの識別子であることを指定します。この NUM は「数」を表す終端トークンとします。その意味付けはトークン解析を行う時に行うので、文法規則だけでは意味付けされません。

　出力ファイルでは NUM というマクロが定義されます。マクロはある値に置き換えられ、それが終端トークンの種類を表す番号になります。

　このように定義されるトークンのほかに、文字も終端トークンとして扱われます（文字列ではなく文字です）。また、0 は解析終了を、1, 256 はエラーを表します。そのため、ここで定義されるマクロは 257 以降の値で定義されます。

　そして、このように定義された終端トークンに文字列を使って別名を付けることもできます。

%token NUM "num"

　こうすると、"num" は NUM の別名になります。この機能は "->" のような２文字以上の演算子を扱う時に便利です。

・ 文法規則

　各非終端トークンに次のような意味を持たせたいと思います。

・ 非終端トークン「input」

　入力データを表します。「文が０個以上あるもの」と定義します。

・ 非終端トークン「line」

　文を表します。「改行で終わり、改行があるまでに式が０個か１個あるもの」と定義します。

　文を処理すると、「式がある場合はその式の結果を表示し、ない場合は何もしない」という動作を行いたいと思います。

・ 非終端トークン「expr」

　式を表します。「数値、四則演算、累乗演算、またはネゲーション（符号反転演算）」と定義します。

　これを bison のインプットでは次のように書きます。

input   : /* empty */
        | input line
;

line    : '\n'
        | expr '\n'
                { printf("\t%.10g\n", $1); }
;

expr    : NUM
        | expr expr '+'
                { $$ = $1 + $2;            }
        | expr expr '-'
                { $$ = $1 - $2;            }
        | expr expr '*'
                { $$ = $1 * $2;            }
        | expr expr '/'
                { $$ = $1 / $2;            }
        | expr expr '^'
                { $$ = pow($1, $2);        }
        | expr 'n'
                { $$ = -$1;                }
;

・ 非終端トークン「input」

　「」（何もない場合）または「input line」と定義します。全体で、「トークン「line」が０個以上あるもの」を表します。

・ 非終端トークン「line」

　「'\n'」（改行のみ）または「expr '\n'」と定義します。全体で、「改行で終わり、改行があるまでにトークン「expr」が０個か１個あるもの」を表します。

　そして、「expr '\n'」の方にはアクションが設定してあります。アクションは、非終端トークンがこの形で解析を終えた時に実行される C のコードです。

　この場合は $1 を printf を使って表示するようにしています。この $x というのは、文法中に現れる x 番目のトークンの意味的な値を表します。ここではトークン「expr」の意味的な値を表します。つまり、「expr」の意味的な値を表示することになります。

・ 非終端トークン「expr」

　数を表す終端トークン「NUM」または「expr 単項演算子」または「expr expr 二項演算子」と定義します。３−２ でやったように、「NUM NUM NUM 二項演算子 二項演算子」や「NUM NUM 二項演算子 NUM 二項演算子」というのを定義しなくても、再帰的に評価することによってあらゆる可能性を網羅することができます。

　「NUM」以外の文法にはアクションが設定してあります。ここには「line」の時と違って $$ というものが出てきます。この $$ はその非終端トークン自身の意味的な値を表します。

・ C の追加コード

　ここには、トークン解析関数 yylex、エラー表示関数 yyerror、そして main 関数などを書きます。

/* トークン解析関数 */
int yylex(void)
{
  int c;

  /* 空白、タブは飛ばす */
  while((c = getchar()) == ' ' || c == '\t')
    ;
  /* 数値を切り出す */
  if(c == '.' || isdigit(c))
  {
    ungetc(c, stdin);
    scanf("%lf", &yylval);
    return NUM;
  }
  /* EOF を返す */
  if(c == EOF)
    return 0;
  /* 文字を返す */
  return c;
}

/* エラー表示関数 */
void yyerror(const char* s)
{
  fprintf(stderr, "error: %s\n", s);
}

int main(void)
{
  /* 構文解析関数 yyparse */
  return yyparse();
}

・ トークン解析関数 yylex

　標準入力から、空白、タブは無視して、数値か、文字かを切り出しています。切り出したあと、その終端トークンの種類を表す値を返します。文字の場合は文字コードをそのまま返せます。それ以外のときは bison の宣言で定義したマクロを使います。そして、解析を終える時は 0 を返します。

　数値の場合には yylval という値にその値を入れていますが、これが意味的な値になります。意味的な値は yylval に入れるのです。

・ エラー表示関数 yyerror

　エラーが起きたときに yyerror 関数が呼ばれます。引数にはエラーの内容を表す文字列が渡されます。

　ここではその文字列を標準エラー出力に出力しています。

・ main 関数

　トークン解析関数 yyparse を呼んでいます。ただそれだけです。

・ まとめ

　以上のインプットをまとめると、次のようになります。

%{

#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define YYSTYPE double

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

%}

%token NUM

%%

input   : /* empty */
        | input line
;

line    : '\n'
        | expr '\n'
                { printf("\t%.10g\n", $1); }
;

expr    : NUM
        | expr expr '+'
                { $$ = $1 + $2;            }
        | expr expr '-'
                { $$ = $1 - $2;            }
        | expr expr '*'
                { $$ = $1 * $2;            }
        | expr expr '/'
                { $$ = $1 / $2;            }
        | expr expr '^'
                { $$ = pow($1, $2);        }
        | expr 'n'
                { $$ = -$1;                }
;

%%

/* トークン解析関数 */
int yylex(void)
{
  int c;

  /* 空白、タブは飛ばす */
  while((c = getchar()) == ' ' || c == '\t')
    ;
  /* 数値を切り出す */
  if(c == '.' || isdigit(c))
  {
    ungetc(c, stdin);
    scanf("%lf", &yylval);
    return NUM;
  }
  /* EOF を返す */
  if(c == EOF)
    return 0;
  /* 文字を返す */
  return c;
}

/* エラー表示関数 */
void yyerror(const char* s)
{
  fprintf(stderr, "error: %s\n", s);
}

int main(void)
{
  /* 構文解析関数 yyparse */
  return yyparse();
}

　これを rpn.y というファイルに保存します。これを bison に通します。

bison rpn.y

　すると、rpn.tab.c という C のファイルが出力されます。これをコンパイルしてやれば、後置式計算機の完成です。

gcc -O -o rpn rpn.tab.c

　以下に実行例を示します。

1 2 +
        3
1 2 3 4 5 + + + +
        15
1 2 3 * +
        7
1 2 * 3 +
        5
3 1 - 2 +
        4
3 1 2 + -
        0
2 1 n -
        3
9 3 / 3 /
        1

　普通の式（中置記法）では優先順位や結合規則が必要になりますが、後置式の場合は 3 1 - 2 + (→ (3 - 1) + 2) や 3 1 2 + - (→ 3 - (1 + 2)) のように不要です。

４−２．普通の計算機

　今度は普通（中置記法）の計算式を読んで計算を行う計算機を作ります。

・ C の宣言文と追加コード

　４−１と同じで問題ありません。

・ bison の宣言文

%token NUM
%left '+' '-'
%left '*' '/'
%left NEG
%right '^'

　%token NUM の他に、演算子の結合規則が書いてあります。

　'+', '-', '*', '/' は上で見たように左結合です。累乗演算子 '^' は右結合にしておきます。4 ^ 3 ^ 2 は 4 ^ (3 ^ 2) と同じになります（つまり 4³² です）。

　NEG というのはネゲーション（符号反転演算）を表し、ここで定義される終端トークン識別子ですが、実際には NEG という終端トークンはそのまま使いません。優先順位を表す記号としての識別子です。その意味は後で分かると思います。

　優先順位は下に行くほど高くなります。従って、加減算が一番優先順位が低く、乗除算、ネゲーション、そして累乗演算の順に優先順位が高くなっていきます。

・ 文法規則

input   : /* empty */
        | input line
;

line    : '\n'
        | expr '\n'
                { printf("\t%.10g\n", $1); }
;

expr    : NUM
        | expr '+' expr
                { $$ = $1 + $3;         }
        | expr '-' expr
                { $$ = $1 - $3;         }
        | expr '*' expr
                { $$ = $1 * $3;         }
        | expr '/' expr
                { $$ = $1 / $3;         }
        | expr '^' expr
                { $$ = pow($1, $3);     }
        | '-' expr
                %prec NEG
                { $$ = -$2;             }
        | '(' expr ')'
                { $$ = $2;              }
;

　「input」と「line」は前と同じです。

　「expr」もカッコ式が増えたこと以外は殆ど同じですが、ネゲーションの部分がちょっと違います。

　ネゲーションの部分には %prec NEG というのが付いています。これは、優先順位や結合規則を NEG と同じにするという指定です。

　ネゲーションを表す演算子は '-' で減算と同じですが、優先順位は減算の時とは異なります。なので、NEG という形式的な識別子を定義して、それと同じにする、というように指定するわけです。

４−３．エラー訂正

　４−２に少し手を加えて、エラーが起こったときの処理を行います。手を加えるのは「line」の定義で、

line    : '\n'
        | expr '\n'
                { printf("\t%.10g\n", $1); }
        | error '\n'
                { yyerrok;                 }
;

　とします。「error」というのは構文エラーを表す非終端トークンです。構文解析に失敗するとトークン「error」であると解釈されます。

　「error '\n'」は「構文解析に失敗してから改行が現れるまで」を表します。従って、構文解析に失敗した行、ということになります。

　yyerrok というのはエラーから復帰するためのものです。どうやらエラーが起こっていることを表すフラグをクリアするもののようです。

　こうすると、構文エラーが起こっても構文解析を続けることが出来ます。

４−４．トークン所在地の利用

　４−３に少し手を加えて、ゼロ除算の場合にエラーを出すようにします。その際、どの位置でエラーが発生したかも表示します。

・ C の宣言文

%{

#include <stdio.h>
#include <ctype.h>
#include <math.h>

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

%}

　諸般の事情により意味的な値の型は int にしておきます。デフォルトで int なので、YYSTYPE の定義を消せばいいだけです。

・ 文法規則

　x 番目のトークンの所在地は @x で取得できます。これは構造体になっていて、first_line, first_column, last_line, last_column というメンバはそれぞれ始点の行番号、始点の列番号、終点の行番号、終点の列番号を表します。また、@$ でその非終端トークン自身の所在地を取得できます。

line:     '\n'
        | expr '\n'
                { printf("\t%d\n", $1); }
        | error '\n'
                { yyerrok;              }
;

expr    : NUM
        | expr '/' expr
                {
                  if($3 != 0)
                    $$ = $1 / $3;
                  else
                  {
                    $$ = 1;
                    fprintf(stderr,
                      "%d.%d-%d.%d: division by zero",
                      @3.first_line, @3.first_column,
                      @3.last_line,  @3.last_column);
                  }
                }
    :
    :
    :
;

　エラー復帰の方法として、意味的な値には 1 を入れておきます。本来なら答えは未定義な筈のに答えが出てきますが、仕方がないとしておきます。

　また、整数を扱うようにしたので、printf のフォーマットを %.10g から %d に変えておきます。

・ C の追加コード

　しかし、文法規則に @x を追加しただけでは所在地を取得することは出来ません。トークン解析の部分で解析位置を逐一知らせてやる必要があるのです。

/* トークン解析関数 */
int yylex(void)
{
  int c;

  /* 空白、タブは飛ばす */
  while((c = getchar()) == ' ' || c == '\t')
    yylloc.last_column++;

  /* 先頭の位置を保存 */
  yylloc.first_line   = yylloc.last_line;
  yylloc.first_column = yylloc.last_column;

  /* 数値を切り出す */
  if(isdigit(c))
  {
    yylval = c - '0';
    yylloc.last_column++;
    while(isdigit(c = getchar()))
    {
      yylloc.last_column++;
      yylval = yylval * 10 + c - '0';
    }
    ungetc(c, stdin);
    return NUM;
  }

  /* EOF を返す */
  if(c == EOF)
    return 0;

  /* 文字を返す */
  if(c == '\n')
  {
    yylloc.last_line++;
    yylloc.last_column = 0;
  }
  else
    yylloc.last_column++;
  return c;
}

int main(void)
{
  /* 所在地の初期化 */
  yylloc.first_line   = yylloc.last_line   = 1;
  yylloc.first_column = yylloc.last_column = 0;

  return yyparse();
}

　yylloc がトークンの位置を表す構造体変数です。トークン解析を行いながら、yylloc の値をしかるべき値に設定します。

　数値の解析に scanf を使うと yylloc の値を決められないので、手動で解析してやります。実は、このとき小数だと面倒になるので、意味的な値の型を整数にしたのでした。

　以上、bison を使って簡単な計算機を作ってみたわけですが、やっぱり自分で作るよりはるかに楽だなー、と思いました。でも、トークン解析の部分がまだ面倒なので flex も使えるようにしたいですね。

　もっと複雑な計算機を作ってみるテストは flex を使えるようになったあとにやってみようと思います。%union や %type の使い方も実はもう分かっているのですが、トークン解析が面倒なので保留です。

　他に簡単にできるものとして、普通の式を後置式に変換して表示するプログラムなんかも考えられます。いろいろいじってみると面白いと思いますね。

目次に戻る

トップページに戻る

Last update was done on 2002.8.19