字句解析や構文解析プログラムは、手書きで作ることもできますが、世の中にはこれらの処理を自動的に作ってくれる ソフトがあります。 僕はインターネットのサイトを閲覧したり、エイホのバイブルを読んだりして、その存在を知ってはいました。 しかしこういったソフトを扱うことは、とても難しいという印象を持っていたため、 使ってみたいとはあまり思っていませんでした。 「正規表現」や「ＢＮＦ」などの見知らぬ表記法にも抵抗がありましたし、 UNIX系のツールですので、必要なライブラリなんかも僕の開発環境（ＶＣ＋＋）とは異なっているかもしれません。 手書きで作った方が、早くて確実だと思っていたのです。
ところが、そんな認識を一変させられるような本を、たまたま書店で立ち読みしていて発見したのです。
| タイトル | ｙａｃｃ／ｌｅｘ プログラムジェネレータ ｏｎ ＵＮＩＸ |
|---|---|
| 著者 | 五月女健治 |
| 発行元 | 株式会社テクノプレス |
| お値段 | ３５０２円（本体３４００円） |
この本ではyaccとlexという２種類のソフトの使い方と、これらのソフトを 使って言語処理系を開発する方法が解説されています。
例題として関数電卓や簡易インタープリタ、簡易コマンドラインといったプログラムの ソースコードが掲載されているのですが、 どれも短く簡潔で、しかも構造が明確なので、とても読み易いコードばかりでした。
簡易インタープリタは、そのソースコードは６００行足らずなのですが、 Ｃ言語風の簡易言語で書かれたテキストファイルを翻訳し、そのまま実行する機能を有しています。 さすがに関数定義や配列などの機能はありませんが、変数が使用できますし、画面やキーボードからの入出力を 行う組み込みの関数を有しています。
この本を買う前日までは、構文解析器の作成が思うように進まず、それ以降に必要となってくる、 記号表や構文木の生成、型チェックといった処理や、これらの処理を構文解析に結び付ける方法については、 ほとんど見通しが立っていない状態でした。 暗中模索の様相を呈していたインタープリタの作成が、この本のサンプルコードでは 「そんなの有りですか？」と思うくらい、あっさりと記述されていたのです。
字句解析器を生成する「ｌｅｘ」と、構文解析器を生成する「ｙａｃｃ」は、 一般に「コンパイラコンパイラ」と呼ばれています。 lexは「正規表現」、 yaccは「ＢＮＦ」と呼ばれている表記法に基づいて作られた一種のプログラミング言語を使って、 字句解析器や構文解析器の動作を記述します。 これらのソフトに、それぞれの表記法に従って書かれたテキストファイルを渡すと、 字句解析プログラムや構文解析プログラムを、Ｃ言語で書かれたソースコードの形で生成してくれます。
Ｃ言語ですので、他の処理をするプログラムと簡単に結びつけられますし、 生成されるファイルの拡張子を「cpp」にするだけで、Ｃ＋＋のソースコードとして扱うことだってできます。
もちろんyaccで作った構文解析器と、lexで作った字句解析器を連携されることもできます。
デフォルトでlexが生成する字句解析器は、「yylex()」という名前の関数として生成されます。 yylex()はテキストファイルなどの入力ソースから文字列を読み込んで行って、 任意のパターンにマッチしていることを確認すると、「トークン」を 関数の戻り値として返します。（実際にはトークンの種類ごとに割当てられた整数値として返されます。）
一方、yaccがデフォルトで生成する構文解析器は「yyparse()」という名前の関数です。 yyparse()は「yylex()」という名前の関数を繰り返し呼び出して、トークンを得ながら構文解析処理を進めて行くのです。 その結果、構文解析器と字句解析器が連携する形となってくるわけです。
lex用のプログラムを具体的に書いてみますと、次のようなものになります。
%%
\n return (RETURN);
[0-9]+ {yylval = atoi(yytext); return (NUMBER);}
. printf("ERROR!!\n");
%%
「%%」と「%%」で囲まれた範囲に、字句解析処理のルールを書いて行きます。
このテキストファイルをlexに渡して生成された字句解析器は、
文字列を読みこみながら、次のような動作を行います。| 読みこんだ文字列が、改行コード（\n）だった場合は、トークンとして“RETURN”を返す。 |
| 読みこんだ文字列が、０から９までの数字が１文字以上連続しているものだった場合は、 その文字列を数値データに変換して、広域変数のyylvalに代入する。そしてトークンとして“NUMBER”を返す。 |
| 改行コード以外の文字が読みこまれた場合は、「ERROR!!」という文字を表示する。 |
要するに、左側にマッチングする文字列のパターン、右側にパターンにマッチした場合に、 実行される動作を書いて行くわけです。パターンは正規表現という表記法で書きますし、 動作についてはＣ言語の文を書きます。なお「yylval」という変数は、構文解析器に対して、 トークンの種類だけでは表せない、付加的な情報を渡すために定義されている広域変数です。
以上の規則に従った場合、画面に「ERROR!!」の文字を表示させないで済む文字列は、例えば次の ような形になります。
123456
789
0
この文字列には０から９までの数字と改行しか含まれていません。それ以外の文字が１文字混じる度に、 「ERROR!!」という文字が表示されてしまいます。
今度はyacc用のプログラムを書いてみます。
%{
#include <stdio.h>
int sum = 0;
%}
%token RETURN
%token NUMBER
%%
number_list : /* empty */
| number_list number RETURN
;
number : NUMBER {
sum += $1;
printf("sum=%d",sum);
}
;
%%
“%{”と、“%}”で囲まれた区間は、Ｃ言語の文をそのまま書くことができます。このプログラムでは、
「sum」という変数を宣言しています。「%token」というキーワードは、yylex()から返されるトークンを宣言するものです。この宣言 をすることによって、字句解析器は“NUMBER”や“RETURN”という名前を使って、 トークンを返すことができるようになります。 （実際に生成されるＣ言語のソースコードでは#defineに置き換えられます。）
「%%」からは、「生成規則」という指示を書き連ねて行きます。 生成規則は簡単にいうと、ある記号の組み合わせを、一つの記号に置き換えるルールを規定したものです。
yaccが生成する構文解析器は、 「状態スタック」という記憶領域に「記号」をどんどん貯めこんで行きます。 そして貯めこんだ記号の一部が生成規則の右辺（「：」より右側のことです）に合致しているものであった場合、 それを生成規則の左辺の記号に置き換えるという処理を繰り返しながら、構文解析を進めて行くのです。 「ポイッ、ポイッ、ポイッ、ポイッ、ドカーン！」といった感じです。
なお、１種類の記号が複数の生成規則によって生成される場合は、「｜」で区切って、一つにまとめて 書くことができます。
生成規則の右辺の中で“｛”と“｝”で囲まれた部分はアクションといって、 Ｃ言語の文を書くことが出来ます。 生成規則が適用された時、そのアクション（Ｃ言語の文）も一緒に実行されます。 Ｃ言語の文中で“$$”とか“$1”とか見慣れない 文字が登場しますが、これは生成規則の右辺にある 一つ一つの記号を関数に見たてた場合の戻り値みたいなものです。 「$1」は生成規則の右辺で、最初に登場する記号の戻り値を表しています。また「$$」は その生成規則自体の値を返すために「$$＝式；」という代入文の形で使います。
説明が前後しますが、構文解析器にとって、字句解析器から得られるトークンは最も基本的な記号です。 どの生成規則からも生成されることはありません。この記号のことを「終端記号」と呼びます。 逆にどれかの生成規則によって生成される記号のことを「非終端記号」と呼びます。 それと後述しますが「開始記号」という記号もあります。 これらをまとめて「記号」と呼ぶのです。
上記のyacc用プログラムは字句解析器を呼びながら次のような動作を行います。
| ルール１ | 状態スタックが空の場合（まだ何も読みこんでない時）は、記号number_listを置く。 |
|---|---|
| ルール２ | 状態スタックに、number_list、number、RETURNの順に記号が 並んでいる場合は、これをnumber_listに置きかえる。 |
| ルール３ | 状態スタックにNUMBERがある場合、これをnumberに置きかえる。その際に、変数sumに NUMBERに付随するデータ（字句解析器がトークンを返す際、yylvalに設定した値）を加算し、 画面にsumの値を表示する。 |
ここで先ほどのlex用のプログラムと連携させて、次のような入力があった場合の動きを考えてみます。
234
432
この文字列はまず字句解析器によって処理されますから、 構文解析器には次のようなトークンの並びが入力されます。
| 順番 | トークンの種類 | 属性値（yylval） |
|---|---|---|
| １ | NUMBER | 234 |
| ２ | RETURN | 未設定 |
| ３ | NUMBER | 432 |
| ４ | RETURN | 未設定 |
構文解析器が字句解析器を呼び出す前は、状態スタックは空です。この時ルール１により、number_listが 状態スタックに積まれます。
字句解析器からNUMBERを得ると、ルール３によって、NUMBERはnumber に置きかえられます。その際、変数sumにNUMBERの属性値である234が加算され、その値が画面に表示されます。
字句解析器からRETURNを得ると、状態スタックには「number_list number RETURN」という 順番で記号が並ぶことになりますので、ルール２により、これらをnumber_listに置き換えます。
字句解析器からNUMBERを得ると、ルール３によって、NUMBERはnumber に置きかえられます。その際、変数sumにNUMBERの属性値である432が加算され、その値が画面に表示されます。
字句解析器からRETURNを得ると、状態スタックには「number_list number RETURN」という 順番で記号が並ぶことになりますので、ルール２により、これらをnumber_listに置き換えます。
これで文字列は最後まで読み込まれましたから、構文解析は終了します。最後に状態スタックにはnumber_list が残ることになります。実は文法的に正しい入力を受け付けた場合、必ず最後にnumber_listが１つだけ 状態スタックに残ります。これはこのプログラムに限ったことではなくて、yaccで作られる構文解析器では 必ず最後に１つだけ残る非終端記号が１種類あります。この記号は「開始記号」と呼ばれています。 生成規則は「〜〜〜は●である」という規則を表していますので、最後に一つだけ 残る開始記号というのは、言語の文法そのものを表しているといえます。 「色々と紆余曲折はあったけど、結局は開始記号ということなんだよねー」というわけ（？）です。
なおyaccのプログラムでは、最初に書かれた生成規則の左辺の記号が開始記号となります。
これで、入力された数値を累計するプログラムを作ることができました。これだけの 例では十分に説明はできていませんが、yaccを使ったプログラミングは 非常に強力です。字句解析器を手書きしたとしても、関数や変数が使える関数電卓をわずか１５０行程度で 書くことができます。
yaccを使うことで分り易くなったのは、単にコーディングの面だけではありませんでした。
実はエイホのバイブルでは、大抵はyacc用プログラムの記述に使われているＢＮＦか、類似の表記を使って、 文法やそれに係わる意味規則の説明がなされているのです。 yaccを使わずにそれらの規則を処理しようと思った場合、規則に対応した構文解析器を 完全に手書きで作らなければなりませんでした。バイブルを読んでいると、「分るけど、分らないよ！」 という説明にしばしば対面しましたが、その多くはこうした表記のレベルの高さに由来していました。
例えばエラー処理なんかで、「よくある記述ミスに対応した、誤り用生成規則を作っておくとよい」 などと書いてあっても、「…そうですか、頑張ってくださいね」としか思えなかったものです。
ところがyaccを使い始めてからは、バイブルで説明されている内容から、すぐ具体的な記述方法を連想する ことができるようになり、「僕でもやればできるんだ！！」と思えるようになったのです。
ところで気になるyaccのお値段ですが、なんと今なら 多機能電卓のサンプルコードをお付けして、
たった の10,000円！！
10,000 円です!!!
…というのはもちろん大ウソです。（爆）
バージョンによってはお金を取るものもあるのかもしれませんが、大抵は無料でインターネット上に公開されています。 特に「bison」というyaccの上位互換ソフトはＦＳＦ（Free Software Foundation) という所が出していて、その使用に当たって対価を要求されることはありません。
僕が知っている入手先は、
ftp.cs.titech.ac.jp/pub/gnu
mirror.nucba.ac.jp/mirror/GNU/
などですが、「bison|入手」なんかで検索をかければ幾らでも見つかるんじゃないかと思います。
ただ、これらのソフトはUNIXベースのソフトで、ファイルの解凍や コンパイルなどに手間がかかると思いますので、Windows用の実行ファイルを用意しました。 ファイルの解凍と、コンパイルエラーに対する対症療法的な修正を行っております。 当然フリーでダウンロードして頂けます。
bisonflex.lzh
（LZH形式で圧縮を行っていますので、解凍ソフトを使う必要があります。）
ソース及びドキュメントに関しては上記のサイトからダウンロードして下さい。Bisonのバージョンは1.27、 Flex（lexの上位互換ソフト）は2.5.4の ものをコンパイルしました。
なお、ダウンロードや実行は全てご自身の責任で行って下さい。大切なデータが壊れたり、（そんなことはない と思いますが…）ダウンロードしたらお金を取られた、といった場合を含むいかなる結果についても 私が責を負うことありません。
BisonやFlexで作られるソースコードは、メモリ管理や入出力に標準Ｃライブラリ（※） を使用していますので、ＶＣ＋＋（や他のＣ言語の開発環境）でも適切なヘッダファイルを インクルードすることで簡単に使うことができます。 Flexのソースコードの入力はデフォルトでは標準入力を使いますが、これもYY_INPUTというマクロを 再定義して自前の関数を指定することができますので、どんな入力ソースでもＯＫです。 いや「野菜のオーラ」とかはだめだけど…。
※Visual C++でbisonおよび、flexを使うにはというＴＩＰを用意しました。VC++を使っている方は参考にして下さい。(2001/06/18)
注- 標準Ｃライブラリ
- Ｃ言語の開発環境に標準で添付することになっている関数セット。 基本的なファイル入出力や、メモリ管理、数値計算、文字列操作などを行う関数が用意されています。 国際的な標準規格として定められています。
言語処理系の制作に戻る