第十三報：flex を使ってみる
前回 bison を使ったので、今回は flex を使ってみます。
flex は info がなくて man しかないというやるせない状況ですが、タダなので文句は言いません。
（註：相変わらず用語には無頓着なので不正確なことがあります）
flex はスキャナ（scanner）生成プログラムです。スキャナというのは、トークン解析を行うもののことです。flex はそのスキャナを C のコードとして出力します。
スキャナ生成プログラムとして有名な lex の上位互換プログラムにあたります。
（前回のコピペですんません）
flex でトークン解析を行う場合、各トークンの特徴を正規表現を使って指定します。なので、flex を使うためには先ずこの正規表現を知らないといけません。先ずはそこから話したいと思います。
正規表現というのは UNIX/GNU で伝統的に使われている文字列マッチングのための言語（のようなもの）です。それぞれは微妙に違うものの grep/egrep, sed, awk/gawk, perl などのコマンドで利用されています。GCC でも（そんなに使いやすいわけではないけど）regex という正規表現ライブラリが用意されています。
正規表現は、特殊な文法を用いてある特徴を持った文字列のグループを表現します。例えば、「アルファベットかアンダーラインのみで構成される文字列」や「数字のみで構成される文字列」などです。
正規表現を利用している例として grep というコマンドでは、ある文章にこういったグループと一致する部分があるかどうかをチェックし、一致する文字列が含まれている行を表示します。
正規表現の文法はコマンドによって微妙に異なります。ここでは flex で採用されている正規表現の文法を羅列していきます。
普通の文字はその文字そのものを表します。
改行以外の任意の１文字を表します。
直前の文字が０個以上あることを表します。
直前の文字が１個以上あることを表します。
直前の文字が０個か１個あることを表します。
直前の文字がx個からy個あることを表します。
直前の文字がx個以上あることを表します。
直前の文字がx個あることを表します。
その正規表現を１まとめにして扱います。例えば、AB+ は A が１個に続けて B が１個以上あること（例えば ABBB）を表しますが、(AB)+ は AB が１個以上あること（例えば ABABABAB）を表します。
文字列を表します。メタ文字（特殊文字）を含んでいても、それをメタ文字として扱いません。
文字列の中の任意の１文字を表します。[a-z] のように、文字コードに即して範囲指定することもできます。
その文字列に含まれていない任意の１文字を表します。
前後の正規表現のうちのどちらか１つを表します。つまり、「または」です。
前の正規表現を表しますが、後ろの正規表現の表す文字列が後に続いていなければなりません。
行頭を表します。
行末を表します。
C のものとよく似たエスケープシーケンスを表します。また、\ に続くメタ文字をメタ文字として扱わないことを表します。例えば、\+ は \ が１個以上あることを表すのではなく、+ が１文字あることを表します。
入力ストリームの終端を表します。
ある範囲の文字を表します。[ ] の中で使います。
種類 範囲 [:digit:] 数値を表します。0-9 と同じです。 [:alpha:] アルファベットを表します。A-Za-z と同じです。 [:upper:] 大文字を表します。A-Z と同じです。 [:lower:] 小文字を表します。a-z と同じです。 [:alnum:] アルファベットと数値を表します。0-9A-Za-z と同じです。 [:xdigit:] １６進用の数字を表します。0-9A-Fa-f と同じです。 [:blank:] 空白かタブを表します。（空白）\t と同じです。 [:space:] タブ、改行、垂直移動、改ページ、復帰、空白を表します。 [:cntrl:] 制御文字を表します。\x00-\x1F と同じです。 [:graph:] 表示可能文字を表します。!-~ と同じです。 [:print:] 表示可能文字とタブ、改行、改ページ、復帰、空白を表します。\t\n\f\r !-~ と同じです。 [:punct:] 記号を表します。!-\/:-@\[-`{-~ と同じです。
「英字かアンダーラインで始まり、以下に英数字かアンダーラインのいずれかが０個以上続く文字列」を表します。つまり、C/C++ などで使われる識別子を表します。
空白かタブが１個以上続くことを表します。
整数値を表します。
数学で用いられる極普通の小数値を表します。プログラミング言語では 0.2 を .2 と書いたり 1.0 を 1. と書いたりすることもありますが、ここではそれは考えません。
プログラミング言語で用いられるあらゆる数値を表します。0, 1, 1.0, 0.1, 1., .1, 1e1, 1E+1, 1e-1, 1.1E-1, 1.e-1, .1E1 の全てとマッチし、01, e, 1e, ., .e , .1e-, 1e+ などのような変なものとはマッチしません。どういう構造になってるか一度よく考えてみてください。
シフトJISコードを表します。これと [\t\n -~] の OR をとった正規表現は、シフトJISコードの任意の１文字になります（半角カナは考慮外です）。
EUCコードを表します（半角カナは考慮外です）。
flex のインプットは次のように構成されています。
%{
C の宣言文
%}
flex の宣言文
%%
トークン規則
%%
C の追加コード
flex を実行すると、そのままでは lex.yy.c という名前の C のソースファイルが出力されます。-oファイル名 というオプションを立てることによって、出力ファイル名を指定することが出来ます。
また、トークン規則の部分以外では /* ... */ の形でコメント（インプットと無関係な文字列）を書くことが出来ます。
出力ファイルの先頭に出力される C コードです。%{ と %} と書かれた行で囲みます。
通常、#include, #define 文や関数のプロトタイプ宣言などを書いておきます。
flex 用の宣言文を書きます。
ある正規表現に対するエイリアス（別名）や、状態識別子を宣言します。
エイリアス 正規表現
%s 状態識別子
%x 状態識別子
このエイリアスは {エイリアス} という形で使います。もし abc というもののエイリアスとして ABC というのを作った場合、{ABC}+ は abc+ ではなく (abc)+ と同じになります。
状態は、あるトークン判別を行うかどうかの分岐を行うために使います。デフォルトの状態は INITIAL です。
%s で宣言された状態は INITIAL 状態に含まれます。つまり、INITIAL 状態は同時にその %s で宣言された状態でもあります。
%x で宣言された状態は INITIAL 状態に含まれません。つまり、INITIAL 状態の時はその %x で宣言された状態とはみなされません。
あるトークンを表す正規表現を書き、次にそのトークンを見つけたときに実行する C のコード（アクション）を書きます。
[<状態識別子[,状態識別子,...]>]正規表現 アクション
アクションは１行に書きます。複数行にまたがって書きたい場合は { } で囲みます。
<状態識別子> は開始条件で、そこに指定された状態の時のみこのトークンを判別することを示します。複数の状態で有効にする時は、カンマ ( , ) で区切って指定します。また、省略すると INITIAL 状態を指定したことになります。
現在の状態を変更するには、アクションで BEGIN(状態識別子); と指定します。
bison で yylval などがあったように、flex でも特殊な変数が用意されています。
変数名 説明 yytext そのトークンを表す文字列です。ポインタもしくは配列として提供され、型は flex の宣言文のところで %pointer, %array と書くことにより指定できます。デフォルトはポインタになってます。 yyleng トークンの長さです。 yyin 入力ストリームです。事前に NULL を入れておけば、トークン解析関数を呼んだ時に stdin に設定されます。 yyout 出力ストリームです。事前に NULL を入れておけば、トークン解析関数を呼んだ時に stdout に設定されます。 YY_START 現在の状態を表します。
特殊なアクションとしては、BEGIN を含めて
アクション 説明 ECHO トークンを表示します。 BEGIN() 現在の状態を変更します。 REJECT 普段は一致する正規表現のうち最もトークンが長くなるものを選びます。REJECT を行うと次に長いトークンを探そうとします。 yymore() 次にトークンを探して得られる結果が現在のトークンと合成されるようにします。 yyless(n) 現在のトークンの先頭から n 文字目のところまで解析位置を戻します。 unput(c) 入力に文字 c を返します。ungetc みたいなものです。次の解析はその文字を含めて行われます。yytext がポインタの場合、その内容は壊れます。また、EOF は返せません。 input() 入力ストリームから１文字取得します。flex は C++ のコードも出力できますが、その時は yyinput という名前になります。 yyrestart(in) 入力ストリームを in に変更します。 yyterminate() 解析を終了します。
があります。
なお、どれかの正規表現に一致する最も長いトークンが見つかった時に、それが複数の正規表現にマッチする場合は、上に書いてある方のものが優先されます。例えば、
. printf("One character %s\n", yytext);
"+" printf("Plus\n");となっていると、+ の方とはどうやっても一致しません。
出力ファイルの一番最後に出力される C コードです。main 関数など、必要な処理をここに書くことが出来ます。構文解析しないのであれば、flex の出力ファイルをそのままコンパイルするだけで済むことがあります。
いくつかの具体例を使って、flex の使い方を見ていきます。
前回やったのと全く同じ形の、単純なトークン解析を行います。つまり、数値、文字、ファイル終端の３つの終端トークンしか扱いません。
解析結果は構文解析に回さないので、トークンが切り出せた時に単にそのトークンの種類を表示するだけにします。
%{
#include <stdio.h>
#include <stdlib.h>
%}これらは（flex 自身に必要なため）勝手にインクルードされるようで、別にここでインクルードする必要はありません。まぁ、気休めです。
いくつかのエイリアスを宣言しておきます。
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
NUMBER {FLOAT}{EXPONENT}?
WSPACE [[:blank:]]+NONZERO は 0 以外の数字１文字、DIGIT は数字１文字、FLOAT は小数、EXPONENT は指数、NUMBER は数値一般、WSPACE は空白を表します。
{NUMBER} {
printf("length: %3d / A number: (%s) %lg\n", yyleng, yytext, atof(yytext));
}
{WSPACE} {
printf("length: %3d / Whitespace(s): (%s)\n", yyleng, yytext);
}
\n {
printf("Return\n");
}
. {
printf("length: %3d / A character: (%s) %d\n", yyleng, yytext, yytext[0]);
}
<<EOF>> {
printf("\nEND\n");
return 0;
}次のような終端トークンに分割します。
・
{NUMBER} → (([1-9][[:digit:]]*\.?|0\.|\.[[:digit:]])[[:digit:]]*|0)([eE](-|\+?)[[:digit:]]+)? ややっこしいですが、数値です。
・
{WSPACE} → [[:blank:]]+ 空白かタブが１個以上つながったものです。
・ \n
改行です。
・ .
改行以外の任意の文字１個です。
・ <<EOF>>
入力終了です。この解析は yylex 関数で行われているので、何か値を返せば yylex 関数を抜け出せます。逆に言えば、何か値を返すまでは EOF が来ようが yylex 関数は終了しません。無限に EOF が評価される状況になったりするので、EOF では必ず値を返しましょう。
ここには、main 関数などを書きます。
int main(int argc, char** argv)
{
if(argc > 1)
yyin = fopen(argv[1], "r");
return yylex();
}トークン解析関数 yylex を呼んでいます。普通は標準入力を解析しますが、コマンドラインにファイルが指定されている場合は、そのファイルを解析します。
fclose を呼んでませんが、どうせプログラムが終わると自動的にファイルが閉じられるので別にこれで構いません。
fopen の戻り値も確認していませんが、失敗すると NULL が入り、その時は yylex 内で yyin に stdin が代入されるので問題ありません。
以上のインプットをまとめると、次のようになります。
%{
#include <stdio.h>
#include <stdlib.h>
%}
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
NUMBER {FLOAT}{EXPONENT}?
WSPACE [[:blank:]]+
%%
{NUMBER} {
printf("length: %3d / A number: (%s) %lg\n", yyleng, yytext, atof(yytext));
}
{WSPACE} {
printf("length: %3d / Whitespace(s): (%s)\n", yyleng, yytext);
}
\n {
printf("Return\n");
}
. {
printf("length: %3d / A character: (%s) %d\n", yyleng, yytext, yytext[0]);
}
<<EOF>> {
printf("\nEND\n");
return 0;
}
%%
int main(int argc, char** argv)
{
if(argc > 1)
yyin = fopen(argv[1], "r");
return yylex();
}これを test.l というファイルに保存します。これを flex に通します。
flex -otest.yy.c test.l
すると、test.yy.c という C のファイルが出力されます。これをコンパイルしてやれば完成です。但し、libfl.a というライブラリをリンクする必要があるので、-lfl というオプションをつけておく必要があります。
gcc -O -o test test.yy.c -lfl
以下に実行例を示します。^D は Ctrl+D を入力したことを表します。
1.1e1 + 1e-1 - .1 *(0+1) length: 5 / A number: (1.1e1) 11 length: 1 / Whitespace(s): ( ) length: 1 / A character: (+) 43 length: 1 / Whitespace(s): ( ) length: 4 / A number: (1e-1) 0.1 length: 1 / Whitespace(s): ( ) length: 1 / A character: (-) 45 length: 1 / Whitespace(s): ( ) length: 2 / A number: (.1) 0.1 length: 1 / Whitespace(s): ( ) length: 1 / A character: (*) 42 length: 1 / A character: (() 40 length: 1 / A number: (0) 0 length: 1 / A character: (+) 43 length: 1 / A number: (1) 1 length: 1 / A character: ()) 41 Return ^D END
見事トークンが解析されていますね。flex の作者に乾杯！（酒は飲まないので烏龍茶で）
折角 flex を使っているので、今度はもうちょっと複雑なトークン解析を行ってみます。
４−１と同じで問題ありません。
%x STRING
%x CHARA
%x COMMENT
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
TYPE void|char|int|float|double|short|long|signed|unsigned|sizeof
STO_CLASS extern|static|auto|register
TYPEDEF typedef|enum|struct|union
CONTROL if|else|for|while|do|switch|case|default|goto|return|break|continue
TYPE_QUAL const|volatile
C_KEYWORDS {TYPE}|{STO_CLASS}|{TYPEDEF}|{CONTROL}|{TYPE_QUAL}
ALLOC new|delete
BOOL bool|false|true
EXCEPTION try|catch|throw
CLASS class|public|protected|private|friend|explicit|mutable|inline|virtual|operator|this
CAST static_cast|reinterpret_cast|const_cast|dynamic_cast
TEMPLATE template|typename
NAMESPACE namespace|using
TYPEID typeid
CPP_KEYWORDS {ALLOC}|{BOOL}|{EXCEPTION}|{CLASS}|{CAST}|{TEMPLATE}|{NAMESPACE}|{TYPEID}
INTEGER {NONZERO}{DIGIT}*|0
NUMBER {FLOAT}{EXPONENT}?
KEYWORDS {C_KEYWORDS}|{CPP_KEYWORDS}
ID [_[:alpha:]][_[:alnum:]]*
OPERATOR [+\-*/%&|^~=<>!,.?:()\{\}\[\]]|[+\-*/%&|^=<>!]=|"++"|--|&&|"||"|->|".*"|"->*"
WSPACE [[:blank:]]+INTEGER（整数）、ID（識別子）、KEYWORDS（キーワード）、OPERATOR（演算子）が増えました。
また、KEYWORDS の定義が長くなるのを防ぐためだけに、TYPE（型）、STO_CLASS（記憶クラス）、TYPEDEF（型定義）、CONTROL（制御文）、TYPE_QUAL（型修飾子）、C_KEYWORDS（C キーワード）、ALLOC（動的確保）、BOOL（論理型）、EXCEPTION（例外処理）、CLASS（クラス関連）、CAST（C++ キャスト）、TEMPLATE（テンプレート）、NAMESPACE（名前空間）、TYPEID（タイプＩＤ）、CPP_KEYWORDS（C++ 固有のキーワード）も追加しました。
また、状態 STRING（文字列）、CHARA（文字）、COMMENT（コメント）も宣言します。
<<EOF>> printf("END\n"); return 0;
{INTEGER} printf("An integer: (%s) %d\n", yytext, atoi(yytext));
{NUMBER} printf("A float: (%s) %lg\n", yytext, atof(yytext));
{KEYWORDS} printf("A keyword: (%s)\n", yytext);
{ID} printf("An id.: (%s)\n", yytext);
{OPERATOR} printf("An operator: (%s)\n", yytext);
{WSPACE} printf("Whitespace(s): (%s)\n", yytext);
\n printf("Return\n");
; printf("Semicolon\n");
^#.*$ printf("Preprocessor directive\n");終了、整数、小数、予約語、識別子、演算子、空白、改行、セミコロン、そしてプリプロセッサディレクティブ（無視）です。整数は {INTEGER} と {NUMBER} の両方にマッチしますが、より上に書いてある {INTEGER} の方が優先されます。
"/*" BEGIN(COMMENT); yymore();
<COMMENT>"*/" printf("Comment(s): (%s)\n", yytext); BEGIN(INITIAL);
<COMMENT>"*" yymore();
<COMMENT>[^*]+ yymore();コメントです。/* が現れると COMMENT 状態に移ります。COMMENT は %x で宣言したので、開始条件 %lt;COMMENT%gt; を指定しているところしかマッチングを行いません。こうやれば、コメントだけの判定に専念できるわけです。
先ず、*/ が現れると終了です。で、現れなければ * が現れるまで飛ばします。そして、* が現れると、それが */ でなければ飛ばし、*/ であれば終了します。
\" BEGIN(STRING); yymore();
<STRING>\n printf("Irregal literal: %s", yytext); BEGIN(INITIAL);
<STRING>([^\"\n]|\\\"|\\\n)+ yymore();
<STRING>\" printf("Literal string: %s\n", yytext); BEGIN(INITIAL);
' BEGIN(CHARA); yymore();
<CHARA>([^'\n]|\\'|\\\n)+ yymore();
<CHARA>\n printf("Irregal literal: %s", yytext); BEGIN(INITIAL);
<CHARA>' printf("Literal character: %s\n", yytext); BEGIN(INITIAL);文字列、文字リテラルです。" が現れると STRING 状態に、' が現れると CHARA 状態に移ります。
文字列リテラルの場合は " が、文字リテラルの場合は ' が現れるまで飛ばすわけですが、例外としてそれぞれ \" と \' も飛ばします。また、途中で改行が現れるとリテラルの判定を終了し、不正なリテラルであると出力します。
. printf("Irregal character: (%s)\n", yytext);不正な文字です。優先順位の関係で多分一番下に置くのが普通だと思います。
ちなみに、これを忘れるとどれにもマッチしない場合が現れることがあります。その場合は、マッチしないトークンが出力されるようです。
%{
#include <stdio.h>
#include <stdlib.h>
%}
%x STRING
%x CHARA
%x COMMENT
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
TYPE void|char|int|float|double|short|long|signed|unsigned|sizeof
STO_CLASS extern|static|auto|register
TYPEDEF typedef|enum|struct|union
CONTROL if|else|for|while|do|switch|case|default|goto|return|break|continue
TYPE_QUAL const|volatile
C_KEYWORDS {TYPE}|{STO_CLASS}|{TYPEDEF}|{CONTROL}|{TYPE_QUAL}
ALLOC new|delete
BOOL bool|false|true
EXCEPTION try|catch|throw
CLASS class|public|protected|private|friend|explicit|mutable|inline|virtual|operator|this
CAST static_cast|reinterpret_cast|const_cast|dynamic_cast
TEMPLATE template|typename
NAMESPACE namespace|using
TYPEID typeid
CPP_KEYWORDS {ALLOC}|{BOOL}|{EXCEPTION}|{CLASS}|{CAST}|{TEMPLATE}|{NAMESPACE}|{TYPEID}
INTEGER {NONZERO}{DIGIT}*|0
NUMBER {FLOAT}{EXPONENT}?
KEYWORDS {C_KEYWORDS}|{CPP_KEYWORDS}
ID [_[:alpha:]][_[:alnum:]]*
OPERATOR [+\-*/%&|^~=<>!,.?:()\{\}\[\]]|[+\-*/%&|^=<>!]=|"++"|--|&&|"||"|->|".*"|"->*"
WSPACE [[:blank:]]+
<<EOF>> printf("END\n"); return 0;
{INTEGER} printf("An integer: (%s) %d\n", yytext, atoi(yytext));
{NUMBER} printf("A float: (%s) %lg\n", yytext, atof(yytext));
{KEYWORDS} printf("A keyword: (%s)\n", yytext);
{ID} printf("An id.: (%s)\n", yytext);
{OPERATOR} printf("An operator: (%s)\n", yytext);
{WSPACE} printf("Whitespace(s): (%s)\n", yytext);
\n printf("Return\n");
; printf("Semicolon\n");
"/*" BEGIN(COMMENT); yymore();
<COMMENT>"*/" printf("Comment(s): (%s)\n", yytext); BEGIN(INITIAL);
<COMMENT>"*" yymore();
<COMMENT>[^*]+ yymore();
\" BEGIN(STRING); yymore();
<STRING>\n printf("Irregal literal: %s", yytext); BEGIN(INITIAL);
<STRING>([^\"\n]|\\\"|\\\n)+ yymore();
<STRING>\" printf("Literal string: %s\n", yytext); BEGIN(INITIAL);
' BEGIN(CHARA); yymore();
<CHARA>([^'\n]|\\'|\\\n)+ yymore();
<CHARA>\n printf("Irregal literal: %s", yytext); BEGIN(INITIAL);
<CHARA>' printf("Literal character: %s\n", yytext); BEGIN(INITIAL);
. printf("Irregal character: (%s)\n", yytext);
int main(int argc, char** argv)
{
if(argc > 1)
yyin = fopen(argv[1], "r");
return yylex();
}これでエスケープシーケンスとトリグラフ（三文字表記）の処理を追加すればもう C++ のソースをトークン解析できちゃいます（プリプロセッサディレクティブはプリプロセッサが処理するべきものですが、プリプロセッサが処理した後にも # で始まる情報が（別の形で）残されるので、それを無視する処理を上に追加してあるわけです）。素晴らしいですね。
プリプロセッサの処理を真面目にして、そして出力を工夫すれば、C++ のソースを色付き html に変換することもできそうです。
さて、トークンを解析するだけでは面白くないので、bison とあわせて使ってみます。
ここで注意することは、そのままでは %token で宣言された終端トークン識別子は *.tab.c ファイルの中で定義されているということです。これでは不便なので、これらの定義をヘッダファイルにも出力するようにします。
そのためには、bison を実行する時に -d オプションを追加するか、もしくは bison の宣言文のところで %defines という宣言を追加するかします。そうすれば、*.tab.h というヘッダファイルが出力されます。
あとはそれを flex インプットの C の宣言文のところでインクルードしてやればいいわけですね。
トークン解析の方法として４−１のものを、構文解析の方法として前回の４−２のものを採用して、簡単な計算機を作りたいと思います。
先ず、bison インプットの方を作ります。ファイル名は calc.y にしました。
%{
#include <stdio.h>
#include <math.h>
#define YYSTYPE double
void yyerror(const char* s);
int yylex(void);
%}
%defines
%token NUM
%left '+' '-'
%left '*' '/'
%left NEG
%right '^'
%%
input : /* empty */
| input line
;
line : '\n'
| expr '\n'
{ printf("\t%.10g\n\n", $1); }
| error '\n'
{
fprintf(stderr,
"Location: (%d,%d) - (%d,%d)\n\n",
@1.first_line, @1.first_column,
@1.last_line, @1.last_column);
yyerrok;
}
;
/* expression */
expr : NUM
| expr '+' expr
{ $$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{
if($3 != 0)
$$ = $1 / $3;
else
{
fprintf(stderr,
"Division by 0: (%d,%d) - (%d,%d)\n",
@3.first_line, @3.first_column,
@3.last_line, @3.last_column);
$$ = 1;
}
}
| expr '^' expr
{
double integer;
double fraction = modf($3, &integer);
if($1 < 0 && fraction != 0 || $1 == 0 && $3 <= 0)
{
fprintf(stderr,
"Irregal exponentiation: (%d,%d) - (%d,%d)\n",
@$.first_line, @$.first_column,
@$.last_line, @$.last_column);
$$ = 1;
}
else
$$ = pow($1, $3);
} | '+' expr
%prec NEG
{ $$ = $2; }
| '-' expr
%prec NEG
{ $$ = -$2; }
| '(' expr ')'
{ $$ = $2; }
;
%%
int main(void)
{
yylloc.first_line = yylloc.last_line = 1;
yylloc.first_column = yylloc.last_column = 0;
return yyparse();
}
/* エラー表示関数 */
void yyerror(const char* s)
{
fprintf(stderr, "Error: %s\n", s);
}%defines が追加され、yylex の定義がなくなりました。
また、エラー処理もしてあります。０除算（未定義）と、負の値の非整数での累乗（虚数）、そして０の０か負の値での累乗（未定義）はエラーです。
前回と大して変わらないのでもうこれで構いませんね。
次は flex インプットです。ファイル名は calc.l にしました。
%{
#include <stdio.h>
#include <stdlib.h>
#define YYSTYPE double
#include "calc.tab.h"
extern YYLTYPE yylloc;
void next_location(void);
%}
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
NUMBER {FLOAT}{EXPONENT}?
WSPACE [[:blank:]]+bison インプットで YYSTYPE を定義しましたが、calc.tab.h にはそれは反映されません。なので、こちらでも calc.tab.h をインクルードする前に定義しておく必要があります。これは YYSTYPE の定義を bison 側と flex 側の共通ヘッダファイル内で行うようにすれば特に問題ないことです（ここではしませんが）。
そして（これが信じられないことですが）yylloc の extern も行われません。なので、これも手動で宣言する必要があります。yylloc を非公開にするつもりなら static 変数にしておけばいいし、何より yylloc の型である YYLTYPE を公開する必要もないのですが（YYLTYPE は calc.tab.h でもちゃんと定義されています）、何かよく分からない仕様です。
まぁ、とにかくこれで yylval, yylloc, NUM が flex 側でも使えるようになります。
他は特にいいでしょう。
%%
{NUMBER} {
next_location();
yylloc.last_column += yyleng;
yylval = atof(yytext);
return NUM;
}
{WSPACE} {
yylloc.last_column += yyleng;
}
\n {
next_location();
yylloc.last_line++;
yylloc.last_column = 0;
return yytext[0];
}
. {
next_location();
yylloc.last_column++;
return yytext[0];
}
<<EOF>> {
return 0;
}
%%
/* トークンの始点を更新 */
void next_location(void)
{
yylloc.first_line = yylloc.last_line;
yylloc.first_column = yylloc.last_column + 1;
}これが yylex 関数を生成することを思い出せば、どういうコードを書けばいいかは分かると思います。
数値の時は、意味的な値を設定して、NUM を返します。空白の時は、無視して次に進みます。改行やその他の文字の時は、その文字コードを直接返します。そして、最後は 0 を返します。
あと、トークンの位置も指定しています。
next_location 関数で、トークンの始点を更新します。始点は前の終点の次になります。一番最初は終点を (1,0) に設定してあるので、next_location を呼ぶと始点は (1,1) になります。妥当な値になりますね。
そして、次に終点をずらします。前回の終点の値は始点の１つ前なので、そこにトークンの長さを追加すれば次の終点になります。例えば始点が (3,3) の時に１文字のトークンが現れた時、終点は (3,3) になります。前回の終点は (3,2) なので、そこにトークンの長さを加えるとちゃんと (3,3) になることが分かります。
改行の時は行を進めます。列番号を 0 にしておくのは、一番最初の時と同じ理由ですね。
さて、これらのファイルから実行ファイルを作ります。makefile は次の様になります。Cygwin を使っているので .exe なんてのがついていますが、Linux などではそんなもんは要りません（実のところは Cygwin では日本語が使えないので、上のインプット中の日本語も英語で書いて実行してるのですが）。
calc.exe: calc.tab.c calc.yy.c gcc -O -o calc calc.yy.c calc.tab.c -lfl calc.yy.c: calc.l calc.tab.h flex -ocalc.yy.c calc.l calc.tab.c: calc.y bison calc.y
では、ちゃっちゃと make して、./calc を実行してみましょう。
3 - 1 + 2
4
2 * 3^2 / 5e-2
360
4/0 + 5
Division by 0: (3,3) - (3,3)
6
-2^0.5
-1.414213562
(-2)^0.5
Irregal exponentiation: (5,1) - (5,8)
1
x
Error: parse error
Location: (6,1) - (6,1)
おおー、感動ですねー。いや、bison と flex のおかげなんですけど。
こうなるともっと色んな事をしてみたくなります。というわけで、次にいってみましょう。
変数に代入したり、その変数を使って計算したりできる計算機を作って見ましょう。
以下のような仕様にします。
では、作りましょう。
#ifndef ___CALC_H__20020820_1627_JF38FJEU__INCLUDED___ #define ___CALC_H__20020820_1627_JF38FJEU__INCLUDED___ #define VARNAME_SIZE 63 #endif /* #ifndef ___CALC_H__20020820_1627_JF38FJEU__INCLUDED___ */
変数名の最大長です。bison でも flex でも使うので、共通ヘッダファイル内で定義しておきます。
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include "calc.h"
void yyerror(const char* s);
int yylex(void);
static double* get_var(const char* name);
typedef struct _var_t
{
double value;
char name[VARNAME_SIZE + 1];
struct _var_t* less;
struct _var_t* greater;
} var_t;
static var_t var_tree = { 0, { '\0' }, NULL, NULL };
%}今回はちょっと長いです。何で長くなったのかというと、変数の管理をするのに必要な宣言が増えた分長くなったのです。
先ず、get_var というのは変数名を入れると変数のアドレスを返す関数です。変数は全て double 型にしておきます。何でアドレスを返すかというと、代入できるようにしたいからです。
変数の名前と値を管理する構造体が、次に定義されている var_t です。追加速度と検索速度の両方が必要なので、二分木にしています。で、ルートは var_tree です。
%defines
%union {
double number;
double (*fp)(double);
char string[VARNAME_SIZE + 1];
}
%token <number> NUM
%token <string> VAR
%token <fp> FUNC
%type <number> expr
%left '+' '-'
%left '*' '/'
%left NEG
%right '^'今回は %union, %type 宣言を使ってます。
先ず、%union 宣言では、意味的な値の型が複数あることを宣言します（１つでも使えますが）。そして、型と、それに対応する識別子を宣言します。yylval は %union で指定したのと全く同じ形をした共用体になります。
そして、終端トークンとして NUM, VAR, FUNC の３つを宣言しています。NUM は数値、VAR は変数、FUNC は関数型演算子です。名前の前に < > で囲んであるのは %union で宣言した型識別子です。これらの終端トークンが対応する型を持つ（意味的な値として共用体のそのメンバを使う）ことを表します。
%type は非終端トークンの型を指定するのに使います。ここでは、expr（式）の型を number（数値）だと宣言しています。
/* input */
input : /* empty */
| input line
;
/* statement */
line : '\n'
| expr '\n'
{
*get_var("ans") = $1;
printf("\t%.10lg\n\n", $1);
}
| VAR '=' expr '\n'
{
*get_var("ans") = *get_var($1) = $3;
printf("\t%.10lg\n\n", $3);
}
| error '\n'
{
fprintf(stderr,
"Location: (%d,%d) - (%d,%d)\n\n",
@1.first_line, @1.first_column,
@1.last_line, @1.last_column);
yyerrok;
}
;
/* expression */
expr : NUM
| VAR
{ $$ = *get_var($1); }
| FUNC '(' expr ')'
{ $$ = $1($3); }
| expr '+' expr
{ $$ = $1 + $3; }
| expr '-' expr
{ $$ = $1 - $3; }
| expr '*' expr
{ $$ = $1 * $3; }
| expr '/' expr
{
if($3 != 0)
$$ = $1 / $3;
else
{
fprintf(stderr,
"Division by 0: (%d,%d) - (%d,%d)\n",
@3.first_line, @3.first_column,
@3.last_line, @3.last_column);
$$ = 1;
}
}
| expr '^' expr
{
double integer;
double fraction = modf($3, &integer);
if($1 < 0 && fraction != 0 || $1 == 0 && $3 <= 0)
{
fprintf(stderr,
"Irregal exponentiation: (%d,%d) - (%d,%d)\n",
@$.first_line, @$.first_column,
@$.last_line, @$.last_column);
$$ = 1;
}
else
$$ = pow($1, $3);
}
| '+' expr
%prec NEG
{ $$ = $2; }
| '-' expr
%prec NEG
{ $$ = -$2; }
| '(' expr ')'
{ $$ = $2; }
;注目するところは、
line : ...
| expr '\n'
{
*get_var("ans") = $1;
printf("\t%.10lg\n\n", $1);
}
| VAR '=' expr '\n'
{
*get_var("ans") = *get_var($1) = $3;
printf("\t%s = %.10lg\n\n", $1, $3);
}
| ...
;
expr : ...
| VAR
{ $$ = *get_var($1); }
| FUNC '(' expr ')'
{ $$ = $1($3); }
| ...
;の部分です。ある意味、これ以外５−１から変更するところがなかったところも注目すべきことなのかもしれません。
line では、代入文を定義しています。文法は上で書いたとおりです。
$x はもちろん x 番目のトークンの意味的な値ですが、$1 は VAR なので string メンバが、$3 は expr なので number メンバがそれぞれ自動的に使用されます。いちいちインプット中でメンバを指定する必要はありません。
get_var は上に書いてあるように使います。これが仕様です。変な分岐は全く必要ないように作ります（つまり、メモリ確保に失敗すると問答無用で exit します）。
変数 ans にも代入しておきます。これで前回の結果を参照できるようになるわけです。
expr では、変数と関数型演算式を定義しています。意味的な値が関数ポインタでもちゃんと使えますね。
int main(void)
{
yylloc.first_line = yylloc.last_line = 1;
yylloc.first_column = yylloc.last_column = 0;
*get_var("pi") = M_PI;
*get_var("e") = M_E;
return yyparse();
}
void yyerror(const char* s)
{
fprintf(stderr, "Error: %s\n", s);
}
double* get_var(const char* name)
{
var_t* var = &var_tree;
var_t** pvar;
if(var_tree.name[0] == '\0')
{
strcpy(var_tree.name, name);
return &var_tree.value;
}
for(pvar = &var; (*pvar) != NULL; )
{
int compare = strcmp(name, (*pvar)->name);
if(compare == 0)
return &(*pvar)->value;
pvar = (compare < 0) ? &(*pvar)->less : &(*pvar)->greater;
}
var = (*pvar) = (var_t*)malloc(sizeof (var_t));
if((*pvar) == NULL)
exit(1);
var->value = 0;
var->less = NULL;
var->greater = NULL;
strcpy(var->name, name);
return &var->value;
}main では、円周率とネイピア数（自然対数の底）をあらかじめ追加しておきます。他によく使う定数があればあらかじめ追加しておくといいですね。p がちょうどアルファベットの真ん中付近にあるので、二分木のバランスをとるために円周率の方を先に追加しておきます（アルファベットの前半をよく使うようであればネイピア数の方を先に追加した方がいいかもしれません）。
二分木のメモリの開放は、プログラムが終われば自動的に行われるのでそれに任せます。要するに手抜きです。
get_var では、識別子を検索して、見つかれば素直に変数のアドレスを返し、見つからなければ新しくメモリを確保してから返します。何というか、それ以上でも以下でもありません。
%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "calc.h"
#include "calc.tab.h"
extern YYLTYPE yylloc;
/* トークンの始点を更新 */
void next_location();
/* 関数型演算子の定義 */
#define DEF_FUNC(func) do{ next_location(); yylval.fp = func; return FUNC; } while(0)
/* 四捨五入 */
double round(double n);
%}型を %union で指定すると、YYSTYPE の定義が要らなくなります。共用体の定義に VARNAME_SIZE の定義が必要なので、calc.tab.h をインクルードする前に calc.h をインクルードする必要があります。
DEF_FUNC は、関数型演算子の定義を楽にするためのマクロです。余談になりますが、do-while にしてあるのは、複文マクロになるところを単文マクロにするためのテクニックです。ただ { } で囲んだだけの場合はマクロの後にセミコロンを付けると複文になり、if(...) DEF_FUNC(...); else ... と書くとエラーになってしまいます（if(...){ DEF_FUNC(...); }else ... なら問題ありません）。今回の様に制御文がない場合は、全ての文をカンマで区切り、全体を ( ) で囲むという手もあります。その場合、最後の式が値を返す場合には、マクロをその値として扱うことができます。代入可能な場合はちょっと危険なので、最後は代入不可能な形にしておくと安心です（普通はそこまで気にする必要はないと思いますが）。
round は小数点以下を四捨五入する関数です。
NONZERO [1-9]
DIGIT [[:digit:]]
FLOAT ({NONZERO}{DIGIT}*\.?|0\.|\.{DIGIT}){DIGIT}*|0
EXPONENT [eE](-|\+?){DIGIT}+
NUMBER {FLOAT}{EXPONENT}?
ID [_[:alpha:]][_[:alnum:]]*
WSPACE [[:blank:]]+
%%
{NUMBER} {
next_location();
yylval.number = atof(yytext);
return NUM;
}
{WSPACE} {
yylloc.last_column += yyleng;
}
sin DEF_FUNC(sin);
cos DEF_FUNC(cos);
tan DEF_FUNC(tan);
sinh DEF_FUNC(sinh);
cosh DEF_FUNC(cosh);
tanh DEF_FUNC(tanh);
asin DEF_FUNC(asin);
acos DEF_FUNC(acos);
atan DEF_FUNC(atan);
log DEF_FUNC(log10);
ln DEF_FUNC(log);
exp DEF_FUNC(exp);
sqrt DEF_FUNC(sqrt);
floor DEF_FUNC(floor);
ceil DEF_FUNC(ceil);
int DEF_FUNC(round);
{ID} {
next_location();
strncpy(yylval.string, yytext, VARNAME_SIZE);
yylval.string[VARNAME_SIZE] = '\0';
return VAR;
}
\n {
next_location();
yylloc.last_line++;
yylloc.last_column = 0;
return yytext[0];
}
. {
next_location();
return yytext[0];
}
<<EOF>> {
next_location();
return 0;
}
%%
/* トークンの始点を更新 */
void next_location()
{
yylloc.first_line = yylloc.last_line;
yylloc.first_column = yylloc.last_column + 1;
yylloc.last_column += yyleng;
}
/* 四捨五入 */
double round(double n)
{
return floor(n + 0.5);
}面倒なので、next_location の中に yyleng を足す部分も入れました。改行の時に二度手間になりますが、まぁ、いいです。
新しく増えたのは、関数型演算子と変数名の定義です。優先順位の関係上、識別子は関数型演算子の後に定義します。
関数型演算子の定義は DEF_FUNC を呼ぶだけです（マクロなのでこの表現は若干不正確ですが）。即ち、next_location を呼んで、yylval.fp に関数のアドレスを代入して、FUNC を返します。関数型演算子は三角関数 sin, cos, tan 、双曲線関数 sinh, cosh, tanh 、逆三角関数 asin, acos, atan 、常用対数 log 、自然対数 ln 、ネイピア数に対する指数関数 exp 、平方根 sqrt 、切り捨て関数 floor 、切り上げ関数 ceil 、そして四捨五入関数 int です。
変数名は VARNAME_SIZE 文字までに制限しているので、strncpy を使って VARNAME_SIZE 文字までしかコピーしません。この関数は元の文字列が VARNAME_SIZE を超えている場合には最後にヌルキャラクタがつきません。なので、最後に手動でヌルキャラクタをつける必要があります。もっとも、yylval は静的な変数なので 0 で初期化されており、yylval.string[VARNAME_SIZE] の値はその後のどんな操作でも変えられないので、この作業は必要ありませんが。まぁ、何かバグがあったときの保険とでも思っておいてください（flex 自身のバグを含む）。
calc.exe: calc.tab.c calc.yy.c gcc -O -o calc calc.yy.c calc.tab.c -lfl calc.yy.c: calc.l calc.h calc.tab.h flex -ocalc.yy.c calc.l calc.tab.c: calc.y calc.h bison calc.y
makefile は calc.h が増えた以外に特に変更はありません。ではコンパイルして、実行してみましょう。
13^2 - 12^2
25
sqrt(ans)
5
rad = pi / 180
rad = 0.01745329252
sin(45 * rad)
0.7071067812
cos(45 * rad)
0.7071067812
acos(ans)
0.7853981634
ans / rad
45特に何を計算するというわけでもないのですが、とりあえず追加した機能は正常に動作しているようです。素晴らしい！
以上、flex も使って計算機を作ってみたわけですが、結構簡単にできるのでびっくりです。bison & flex さまさまです。
bison も flex ももっと色んな機能があるようで、使い倒すにはまだまだ時間がかかりそうです。そのうちでいいので、何か実用的なものでも１つ作ってみたいですね。
flex を使って、タブをスペースに変換するプログラム tab2sp と、C++ のソースを HTML に変換するプログラム cpp2html を作ってみました。２つをパイプで繋いで実行する srcconv も作っておきました。
ここにおいておきます。Cygwin 用なので makefile 内に .exe 拡張子があるわけですが、変数にしておいたのですぐ外せると思います。
上の４−２には結構穴があったので、修正してます。ただ、あんまりデバッグしてないので穴があったらごめんなさい。
Last update was done on 2002.8.21