作成したものはプログラム実験部屋のその５−JBCompilerにおいてあります。
1. はじめに
コンパイラ作ってみるかも編−その１で始めたコンパイラ作成ですが、VBで軽く字句解析・構文解析の基礎を学んでみました。
そこで、ようやくここから実際のコンパイラを作成しようと思います。
まず、今回作成するコンパイラの大まかな仕様を決めておきます。
|
今回はx86のコードは生成せず、Javaのクラスコードを生成します。
この利点として、メモリ管理をJavaVMに丸投げできることや、多少変なコードでもPCの動作に影響を与えず実行できるという利点があります。
.exeを吐くコンパイラを作ると、まともに動くまで何度もおかしな動作しそうでちょっと怖いし(^^;
flex(Wikipedia)とbison(Wikipedia)は、それぞれ字句解析・構文解析を行うコードを生成してくれるプログラムです。
今回は、まずflexを使って字句解析用のコードを作成してみます。
ただ、flexとbisonは連携して使えるようになっており、逆に今回の例では、bisonのコードも準備しないとコンパイルできません。
2. 環境設定
ということで、まずはflex・bisonを入手します。
色々なバージョンがありますが、今回はUnix系の動作に近いものということで、cygwin版を利用します。
cygwinって何？という人はとりあえず検索してインストールしてみてください。
多分デフォルト設定ではflexとbisonはインストールされないため、パッケージ一覧で明示的にflex・bisonがInstallされるようにしてください。
こんな感じ。KeepかInstallになっていればokです。
なお、数年以上古いcygwinを使っている人は、flexのバージョンが2.5未満の可能性があります。
flexは2.5でC++対応など大きく変更されているので、2.5以上のバージョンにしておいてください。
cygwinのインストールが済んだら、環境変数Pathにcygwin\binディレクトリを追加しておき、コマンドプロンプトから実行できるようにしてください。
コマンドプロンプトで↓のように実行できるとokです。
C:\sample>flex -V flex version 2.5.4 |
さて、次にVisualC++ 2005からflexを利用する方法です。
flexは一般的に拡張子.lのテキストファイルを処理して、C言語の字句解析器を生成します。
そこで、まず拡張子.lのテキストファイルをプロジェクトに登録し、次にカスタムビルド設定をします。
ソリューションエクスプローラで.lファイルを右クリックして"プロパティ"を選択、"構成プロパティ"の"全般"にある"ツール"の欄を"カスタム ビルド ツール"にします。
そして"カスタム ビルド ステップ"の"全般"を開き、"コマンドライン"の欄にflexのコマンドラインを記述します。
ついでに"説明"や"出力ファイル"の項目も埋めておきます。
たとえばこんな感じ。
flexコマンドでは-oの後に空白をつけずに出力ファイル名を書き、最後に入力ファイル名を書きます。
この例ではjbc.lを入力としてjbclexer.cppを生成しています。
この状態でjbc.lにflexが解釈できる適切なデータを持たせておくと、さしあたり１回ビルドさせるとjbclexer.cppが出来ます。
その後生成されたファイルをプロジェクトに追加すると良いでしょう。
3. flexの定義ファイルを書こう
さて、準備が整ったところでflexに処理させるデータを作成します。
この節では、flexの定義ファイルの一般的な書き方を示します。
コンパイラ作成固有の話は次の章以降に行うので、すでにflexを使ったことがある人はこの節は飛ばして大丈夫です。
Flex 字句スキャナ生成プログラムやLex and YACC primer/HOWTOにFlexの日本語マニュアルがあるので、こちらも参考にすると良いでしょう。
今回はJBCompilerで使用したファイルをサンプルに説明していきます。
サンプルファイル(別ウインドウ)
flexは、定義ファイルを処理させることでC/C++でコンパイル可能なソースを生成します。
この定義ファイルの大まかな構成は以下のとおりです。
%{
Cのコード
}%
定義
%%
ルール
%%
Cのコード
|
２箇所あるCのコード部は、flexにより生成されるソースの先頭・末尾にそのままコピーされます。
生成後のファイルで必要な#includeや変数・関数宣言を入れておきます。
上記のサンプルファイルでは、STL関連のヘッダインクルードや、マクロ定義・関数宣言などをしています。
末尾のCコードは空にしてあります。
続く定義部には、基本的に正規表現に名前を与える処理を行います。
ルール部では、同じ正規表現を何度も使用することがあるため、ここで名前を与えておくと繰り返しがなくなって便利です。
なお、この定義はなくてもかまいません。
サンプルファイルの定義例を以下に挙げます。
ID [a-zA-Z][_a-zA-Z0-9]*
digit [0-9]
exponent [eE][+-]?{digit}+
i {digit}+
float_constant ({i}\.{i}?|{i}?\.{i}){exponent}?
左側が名前、右側が正規表現です。正規表現名 ID は、１文字目はアルファベット、２文字目以降はアルファベット・数字・アンダースコアを任意の数繰り返せることを示します。
大抵のプログラム言語の変数名や関数名はこのような正規表現で表現できます。
他にも、数値を表す digit や小数を表す float_constant などを定義しています。
float_constant では、直前の定義 i や exponent を利用しています。
他の正規表現を利用する場合は、 float_constant の例のように、前後を大括弧 { } で囲います。
他にも、定義部には、flexに与えるオプションを指示する %option や、後述のスタート状態を示す %x %s があります。
%option では、flexに対する指示をコマンドラインオプションで与える代わりに、同等の指示を定義ファイルから行えます。
これは上記のマニュアルを参照してください。
そして、残るはルール部です。
ここには、正規表現と、その正規表現にマッチした場合の処理を記述します。
基本的には、正規表現に対応して番号を振り、それをreturnすればokです。
このとき、bisonを利用する場合は、yylvalという変数に追加情報を格納できます。
今回のサンプルファイルでは、たとえば以下のような処理を記述しています。
sub { yylval.lineno=lineno(); return(T_SUB); }
function { yylval.lineno=lineno(); return(T_FUNCTION); }
dim { yylval.lineno=lineno(); return(T_DIM); }
左側は正規表現を記述しますが、この例では正規表現はアルファベットだけなので実質この文字列自体が来るかどうかを判定しています。たとえば入力に sub や function や dim という文字列が来たとき、yylvalに値を代入して、return文で色々返しています。
つまり、flexは sub や function や dim という文字列を見つけるたび、呼び出し元に対応する整数T_SUB、T_FUNCTION、T_DIMを返します。
yylvalには、後のデバッグのためここでは元の入力の行番号を代入しておくことにします。
lineno()はflexの定義する関数で、読み込みの行番号を返します。
4. コンパイラ向けのflex定義ファイル
上では、一般的なFlexの定義ファイルを書いてきました。
ここでは、もう少し実践的に、コンパイラ向けの定義ファイルを書いていきます。
まず、字句解析結果の情報を格納するyylvalの型を決めます。
yylvalはbisonが管理する情報であり、flexではそれをちょっと利用するだけになります。
なので、yylvalの型はbison側で定義するのですが、先にここで載せておきます。
struct{
int lineno;
union{
int type;
Varlist* vl;
Expression* expr;
Statement* stmt;
ExprVec* exprvec;
StmtVec* stmtvec;
};
};
|
exprの型であるExpressionは式を表す構造体で、自前で作成したものです。
字句解析の結果、数値や文字列が出てきた場合、その値を格納するのに使います。
詳細は今後。
さて、字句解析のルールを書いていきます。
まず、予約語の類は上と同様の処理で構いません。
sub { yylval.lineno=lineno(); return(T_SUB); }
function { yylval.lineno=lineno(); return(T_FUNCTION); }
dim { yylval.lineno=lineno(); return(T_DIM); }
他にも、ifとかforとかcallとか色々作っています。次に、演算子を処理していきます。
基本的には上と同じですが、順番には若干注意が必要です。
判定は上から順に行うため、 ++ や += の判定はより短い + より先に行う必要があります。
+ を上にすると、 ++ や += と書いてあっても先に + のルールで処理されてしまいます。
演算子 or のところには何もルールが書いてありませんが、この場合次のルールと同じ処理を行います。
つまり、 or と || は全く同じ処理を行います。
"++" { yylval.lineno=lineno();return(T_INC);}
"--" { yylval.lineno=lineno();return(T_DEC);}
"+=" { yylval.lineno=lineno();return(T_EQADD);}
"+" { yylval.lineno=lineno();return(T_PLUS); }
"or"
"||" { yylval.lineno=lineno();return(T_BOOLOR); }
次に、定義部で作成した正規表現を使う例です。
正規表現を利用する場合は、中括弧で囲います。
{ID} 予約語以外の文字列ということで、変数名や関数名が該当します。
ただ、これが変数か関数かは構文解析をしないとわかりません。
なお、yylvalを使ってこの文字列を保持することが出来ます。
yytextには正規表現にマッチした文字列が入るため、この例ではこの文字列を一旦リストに格納し、そのインデックスをyylvalに持たせています。
(「yylval.expr->index=GetIndexfromIDList(&IDlist,yytext);」の部分。
{int_constant} は10進数で記述された整数を示す正規表現であるため、整数を示すT_INTをreturnしています。
ここでは、yytextからsscanfを利用して数値を読み取り、yylval.expr->ivalに格納しています。
サンプルファイル中では16進数や浮動小数点の数値も処理しています。
なお、これらの数値処置はよくある処理なので、flexのマニュアル中にも数字の処理として記載されています。
{ID} { yylval.expr=new Expression;
yylval.expr->lineno=lineno();
yylval.expr->exprtype=T_ID;
yylval.expr->index=GetIndexfromIDList(&IDlist,yytext); return(T_ID); }
{int_constant} { yylval.expr=new Expression;
sscanf(yytext,"%ld",&yylval.expr->ival);
yylval.expr->lineno=lineno();
yylval.expr->type=T_INT;
yylval.expr->exprtype=T_CONST;
return(T_INT);}
同様に複雑なものとして、「"」で囲まれた文字列の処理があります。これは長いので、flexのマニュアルにある文字列リテラルの処理を参照ください。
次に、空白・改行文字の処理をしておきます。
{ws} はスペースまたはタブです。
まず最後の２行、 {ws} と . はルールが記述されていません。
これは何もしないことを示します。すなわち、字句解析中に空白文字や任意文字が来た場合は無視します。
. は最後のルールとして書くべきでしょう。そうしないと、どんな文字もここにマッチしてしまいます。
"_"{ws}*\n {nowline=lineno()+1;}
^{ws}*\n {nowline=lineno()+1;}
\n {nowline=lineno()+1;yylval.lineno=lineno();return '\n';}
{ws}
.
上３つは改行に関わる処理です。今回作るコンパイラは、VBのように１行で一区切りとしています。ただ、行末に"_"が来たときだけは次の行と連結します。
このため、途中で改行記号 \n が出てきたら、そのまま数値'\n'を返します。
bisonではこれを行区切りとして処理します。
ただ、１つ目のルールでは、"_"のあとに空白がきて、その後改行が来た場合、'\n'を返しません。
すなわち、bisonには行の存在が認識されない＝改行を無視して次の行と連結して処理されます。
２つ目は、行の先頭から空白文字と改行文字しかない、すなわち空行ですね。この場合も何も返しません。
ただ、この３つの処理ではnowlineという変数を更新しています。
これはあとで構文解析でエラーが発生したときに、発生箇所を特定するのに使います。
最後にコメントの処理をします。
これもflexのマニュアルのコメントの処理の欄にあるものに少し手を入れています。
ここでは、定義部で定義したスタート状態 %x が使われています。
先頭の２行だけはルール部ではなく定義部にあると思ってください。
%x comment_line
%x comment_block
"'" { BEGIN(comment_line);}
"//" { BEGIN(comment_line);}
"/*" { BEGIN(comment_block);}
<comment_line>[^\n]+ {nowline=lineno()+1;}
<comment_line>[\n] { BEGIN(INITIAL);}
<comment_block>"*/" { BEGIN(INITIAL);}
<comment_block>[*/]
<comment_block>[^*/\n]+ {nowline=lineno()+1;}
<comment_block>[\n] {nowline=lineno()+1;}
ルールの最初の３つは、コメント処理の開始を示します。これらの文字列を受けると、BEGIN文により指定したスタート状態 comment_line や comment_block に入ります。
これらのスタート状態に入ると、以後先頭に <comment_line> や <comment_block> が付いた行だけが処理対象のルールに入ります。
たとえば、 ' や // により comment_line 状態に入った場合を考えます。
以後、改行以外の文字が来たときは変数nowlineを更新するだけで、改行が来るとBEGIN文により初期スタート状態 INITIAL に戻ります。
これにより、改行までをコメント化することが出来ます。
comment_block も同様で、コメントの終端 */ が来るまではnowlineの更新以外の処理を行いません。
5. まとめ
今回は早くもこれで終わりです。
実際プログラムを動かすには、bison側の設定も必要なので…
flexの役割は、正規表現にマッチする文字列を見つけたら対応する整数値をreturnすること。
その際追加情報があればyylvalに格納すること。
ここさえ覚えておけば、あとは正規表現やスタート状態を適切に設定するだけで字句解析が出来ます。
コンパイラを作る場合、どんな言語でもflexは似たような記述になると思います。
（演算子が「:-)」で、予約語が「B-)」みたいな変な言語を考えない限りは(^^;）
次回、bisonでは構文解析を行いますが、このあたりから作ろうとする言語の特徴が出てきますのでお楽しみに。
参考文献
