PCで文書作成とかしていて、ちょっと電卓が使いたくなることは、 ちょくちょくあります。
Windowsなら、スタートメニューからGUIベースの電卓が起動できますが、 立派なキーボードが付いてるPCで、 マウスで一所懸命ボタンをクリックするのなんて、 冷静に考えるとなんかバカです。
もちろんあの電卓でもキーボードから入力することは出来ますが、 演算子の優先順位は見てくれませんし、括弧を使った計算もできません。 それに、一般に、電卓で何十個もの数値を足す場合などは、 「ああ、入力ミスしてないかなあ」と途中で不安になるものです。 また、途中で入力ミスに気付いた場合、 最後の入力だけクリアして入れ直すことは一応出来るようなんですが、 どこまでどうクリアされてるのかよくわからなくて、 結局最初から入れ直したりしてません? 私は(プログラマの癖に)機械オンチなので、よく最初から入れ直してます。 私だけかも知れませんが(^^;。
てなわけで、機械オンチの私としては、 UNIXなら標準で付いているbcを是非とも使いたいわけです。
UNIXを知らない人のために一応説明しますと、 bcとは、コマンドラインで使える電卓です。 コマンドラインから起動して、
1 + 3 * 2
のように入力してリターンキーを押すと、ちゃんと "7" と表示してくれます。 GUIな電卓に比べて、入力した式の全てがちゃんと見えていますし、 優先順位も見てくれますし、括弧も使えます。
ところで、私のマシンには、自宅のも会社のも、 cygwin(UNIXのツールをWindowsに移植したもの)一式が入れてありますが、 どうもその中に bc は入っていないようです。
でも、gccとbisonとflexは入ってる... なら作れるじゃん、 てなわけで、今回は電卓ネタです。
わかる人はもうわかっているでしょうけど、今回はlex/yaccネタです。
lex/yaccが何か、という話は後述しますが、 本屋に行ってyaccの入門書を一冊買って来ると、 たいてい最初に電卓を作っていたりします(NUTSHELLハンドブックは例外か?)。
でも、そういう例題のプログラムって、やっぱり異様に単純化されていて、 YYSTYPEをデフォルトのままにしてたりとか、 解析木も作らずにアクション内で直接計算してたりとかで、 最初の例題としては悪くはないのでしょうけど、 lex/yaccの使用法として、 それだけで何か実用的なツールが作れるというレベルに達してなくて、 どうも面白くありません。
てなわけで、今回はもうちょっと色々遊んでみることにします。
四則演算・括弧
電卓を名乗る以上、これは必須でしょう。 当然、演算子の優先順位は考慮してくれる必要があります。
整数と実数を混ぜた演算を許すようにして、 (Cがそうであるように)整数同士の演算は整数で行なうこととします。
ところで、bcでは、式を入れてリターン叩けば結果が出るんですけど、 今回は、電卓として使用する際、 式の終わりにはセミコロンを付けなければいけない、 という仕様にしちゃいました。 後述する関数定義などで、複数行に渡る式を書く可能性があるためなんですが、 実際に電卓として使うには結構不便ですねこりゃ(^^;
関数定義
どうせなので関数定義ができるようにしましょう。
define add(a, b) { a + b }
のように定義しておくと、add(3, 5)で8を返すとか。 実用性のほどはいまひとつわかりませんが(笑)。
関数定義内でそれなりに複雑な処理が出来るように、 コンマで区切って式を並べることも出来るようにします。 Perlのように、最後に評価した式の値を関数の値として返す、 という仕様にしときます。
変数
関数が定義できるなら、変数も使えないと、実用的な関数は書けません。 だいたい、関数の引数だって、変数の一種ですし。
関数定義があるのだから、関数内のローカル変数と、 グローバル変数の区別が要りますね。
私的には、変数は使う前に必ず宣言が必要、という言語の方が好きなのですが、 この場合はさすがにちょっと大袈裟なので、 RubyやPythonがそうであるように、最初の代入で宣言されるようにしましょう。 Perlみたいに、初期化もしてない変数が使えちゃうと事故の元ですし。
条件分岐・ループ
こうなると更に遊んで、条件分岐やループもやってみたくなります。
とはいえ、ここまで「式」しか扱えなかった所に、 「文」の概念を持ち込むのも大袈裟ですので、 if や while も式として実現しましょう。
if式:
if 条件式 { 式並び1 } else { 式並び2 }
条件式が真の場合、「式並び1」を評価してその値を返し、 偽の場合、「式並び2」を評価してその値を返します。 もちろんelse以降は省略可能。
while式:
while 条件式 { 式並び }
条件式が真の間、「式並び」を繰り返し評価します。 最後に評価した式の値を、値として返します。
コメント
あまり必要性はないかも知れませんけど、 lexのスタート状態の説明のため(笑) コメントも使えるようにしときます。
UNIX流に、行頭の#から行末までをコメントとします。
なんというか、電卓というよりは、 簡易プログラミング言語になっちゃってるような気もしますが。
この辺に関する参考書は、日本語のものがそこそこ出てますので、 詳細な説明はそちらに譲りますが、まあ簡単に。
コンパイラとかインタプリタとかを作る際には、 入力されたソースに対して「構文解析」を行なう必要があります。
最近の言語だと、まず、入力されたソースを、 レキシカルアナライザでトークンに分割し、 パーサで「解析木」とか「構文木」とか呼ばれるものを 構築することが多いようです。
そういえば、時々、CやJavaのメイリングリストなどで、 こんな質問があったりするようです。
a+++++b;こういうのって、
a++ + ++ b;以外に解釈のしようがないと思うんだけど、 うちのコンパイラはエラーにしちゃうようです。
なぜですか?
確かにもっともな疑問ではあるのですが、 レキシカルアナライザとパーサが独立して動作している限り、 レキシカルアナライザはCやJavaの構文を知りませんから、
a ++ ++ + b;
というトークン分割をしてしまうのは、ま、ある意味当然でして、 このトークン並びがパーサに渡されて、そこでエラーにされてしまうわけです。
んで、lexとyaccについてですが、 lexはレキシカルアナライザを、 yaccはパーサを 自動生成してくれるツールです。 UNIXなら、通常どちらも標準で付いてきます。
lex/yacc共に、定義ファイルを食って、Cのソースを吐きます。
どちらもかなり古いツールなので、 データの受け渡しにグローバル変数を使ってるあたり等、 今見るとかなりトホホなのですが、 それでも、少なくともyaccの方は、 gccやらPerlやらRubyやらの処理系を作成するために、 まだ現役でバリバリ使われているようです。
lexのGNU版がflex、yaccのGNU版がbisonです。 Windowsでは、cygwinをFULL.EXEから入れれば、これらが使えます。
前述のように、今回の電卓では、 レキシカルアナライザの生成にlex(flex)を使用します。
ま、自分でCでゴリゴリ書いても、 レキシカルアナライザぐらい書けるでしょうが、 lexを使う方が楽なのは確かです。
で... 今回の電卓用のlexの定義ファイル calc.lを、 順に説明していこうかと思ったのですが...
正規表現を知っている人なら、まあ見りゃわかるか、 ってことで、ここでは軽く流すにとどめます。
最初の %{ から %} までは、Cのコードを直接記述しています。 ここに書いたCのコードは、lexにより生成されるCのコードにも そのまま入ってきます。
見ればわかるように、#includeやら宣言やらをしています。 YY_INPUTをundefして再定義してますが、これについては後述。
その後の %start は、スタート状態を宣言しています。 ここではCOMMENTというスタート状態を宣言しているわけですが、 これも後述。
次の %% から %% までが、規則の本体です。
電卓プログラムの規則の定義を見ていくと、 まず、<INITIAL>とあるのは、デフォルトのスタート状態です。 とりあえず付けるもんだと思っていてください。 あとは、正規表現(拡張正規表現ですが、 普通の正規表現を知っている人なら、ここで使っている例は、 たいてい見ればわかるでしょう)と、 ごく短いCのコード(大半はreturn XXXX;だけ)がずっと並んでいますね。
入力が正規表現にマッチした時、 このCのコード(アクションと呼びます)が起動されます。 そして、ここでreturnする値が、そのトークンの種類になります。
ところで、一口にトークンと言っても、 その持つ意味合いとしては3通りあります。
んで、calc.lの方に話を戻しますと、
<INITIAL>"define" return DEFINE;
から、
<INITIAL>"%" return MOD;
までは、説明するまでもないでしょう。 正規表現で文字列を引っ掛けて、そのトークンの種類を返しているだけです。 あ、ちなみに、 LP・RPはそれぞれleft parenとright parenの略、 LC・RCはそれぞれleft curly parenとright curly parenの略、 LB・RBはそれぞれleft bracketとright bracketの略です。
ただし、中にはこんな規則もあって、
<INITIAL>"=" return ASSIGN; <INITIAL>"==" return EQ;
「あれ、"="がASSIGNなら、"=="はASSIGNふたつに解釈されちゃうんじゃないかな」 と思った方がおられるかも知れませんが、 lexはちゃんと、「できるだけ長い文字列をトークンとして切り出せるように」 規則を選んでくれるので問題はありません。 さらに、長さが同じなら、先に書いた規則が優先されます。
<INITIAL>[A-Za-z_][0-9]* {
yylval.identifier = clc_malloc(strlen(yytext) + 1);
strcpy(yylval.identifier, yytext);
return IDENTIFIER;
}
これは、変数名を切り出す規則です。
yylval共用体の、identifierというメンバに、 変数名を複写しています(ここで使用している clc_mallocというメモリ確保ルーチンについては後述します)。
次の3つの規則、
<INITIAL>[1-9][0-9]* {
Expression *expression = clc_alloc_expression(INT_EXPRESSION);
sscanf(yytext, "%d", &expression->u.int_value);
yylval.expression = expression;
return INT_LITERAL;
}
<INITIAL>"0" {
Expression *expression = clc_alloc_expression(INT_EXPRESSION);
expression->u.int_value = 0;
yylval.expression = expression;
return INT_LITERAL;
}
<INITIAL>[0-9]*\.[0-9]* {
Expression *expression = clc_alloc_expression(DOUBLE_EXPRESSION);
sscanf(yytext, "%lf", &expression->u.double_value);
yylval.expression = expression;
return DOUBLE_LITERAL;
}
は、数値のリテラルを切り出す規則です。
そのまた次の、
<INITIAL>[ \t\n] ;
この規則で、空白文字(スペース・タブ・改行)を無視しています。 ちなみに、電卓でなくて、ちゃんとしたコンパイラを作っているのなら、 エラーメッセージ中に行番号を含めることが多いでしょうから、 改行について別途アクションを書いて、行番号を数えれば良いでしょう。
次ですが、
<INITIAL>^# BEGIN COMMENT;
この規則で、コメントの開始を認識しています。
コメントは、「行頭の#から行末まで」ですから、 以下のように書いちゃっても良いわけですが、
<INITIAL>^#.*\n ;
こうすると、コメント全体が、一旦yytextに保持されることになります。
昔の処理系だと、サイズ固定のcharの配列になっていて、 しかもそのサイズはそんなに大きくなかったりしたりするようなんですが、 コメントは、かなり長い可能性があるので、これでは具合が悪いです。
それに、Cの文字列リテラルなんかだと、 リテラルの中で8進表現なんか使えたりして、
<INITIAL>\".*\"
みたいな簡単な規則で済ませるわけにもいきません。
てなわけで、コメントの「始まり」を認識した時点で、 BEGIN COMMENT によりスタート状態を変更します。
スタート状態がCOMMENTになると、<INITIAL>で始まる規則ではなく、 <COMMENT>で始まる規則が使われます。
よって、
<COMMENT>. ;
この規則により、 (.は任意の1文字にマッチするので)コメントの読み飛ばしができます。
改行が来た場合には、
<COMMENT>\n BEGIN INITIAL;
により、スタート状態をINITIALに戻します。
<INITIAL>. clc_compile_error(CHARACTER_INVALID_ERR, NULL);
これは、INITIAL状態の他の全ての規則に引っ掛からない 任意の1文字(.は任意の1文字にマッチするので)が来た場合の規則ですから、 何だかよくわからん文字が来たぞ、ってことでエラーにしてますね。
今回作っているのは、コマンドラインで使う電卓ですから、 コマンド行編集が出来た方がいいに決まってますね。
古典的なUNIXの標準のbcでは、式の入力中、backspaceぐらいは使えても、 「式のずーっと前の方を、1文字だけ直したい」 というのはなかなか面倒だったりしました。
# ま、Emacsのshell modeからしか使わないなら、関係ないって話もありますが(^^;
コマンド行編集機能を自分で実装するのは大変ですから、 GNUのreadline()ライブラリを使っちゃうとします。 readline()ライブラリは、 PC UNIX(LinuxとかFreeBSDとか)やcygwinといった gcc環境にはたいてい入っているようです。
これの使い方は非常に簡単で、fgets()等の代わりに、
char *p;
...
p = readline(">");
...
free(p);
のように書くだけです。 readline()の引数はプロンプトの文字列、 戻り値が入力された文字列になります。 入力された戻り値はヒープに確保されますので、 後で忘れずfree()する必要があります。
通常のCUIツールなら、これだけで充分なんですが、 lexの場合、標準の入力ルーチンを持っているので、 ちょっと話がややこしいです。
lex標準の入力ルーチンは、 普通にFILE*から入力を食うようになっていて、そのFILE*は、 yyinというグローバル変数(まったく!)で設定するようになっています。
入力ルーチンを置き換える方法は、処理系によって違ったりするようなんですが、 flexやFreeBSDの標準のlexでは、YY_INPUTマクロを置き換えることで行なうようです。
calc.lの冒頭より: #undef YY_INPUT #define YY_INPUT(buf, result, max_size) (result = my_yyinput(buf, max_size))
こんな感じで自分の入力ルーチンを定義します。 入力ルーチンは、バッファとバッファサイズを受け取り(fgets()流)、 バッファに文字列を詰め込んで、詰め込んだ文字数を返します。 バッファは'\0'で終端させる必要はありません。
calc.lでは、規則部の終わりに%%の行があって、 それ以後に置き換えた入力ルーチンがずらずらと書いてあります。 YY_INPUTの再定義をしなければ、この辺は要りません。
電卓とはいえ、関数定義も書けるとなれば、 ファイルから食うこともあるかな、ってことで、 モードにより、tty_input()とfile_input()を呼び分けるようにしています。
tty_input()の方では、readline()で取れた文字列を、 max_sizeの分だけ、切り取って返すようにしています。 readline()で取った文字列が余った場合は、
static char *st_readline_buffer; static int st_readline_used_len;
を使ってバッファリングしています。
ま、静的なデータを使うことに抵抗がないではないですが、 lex/yacc使っといて、今更それを言ってもしょうがないですし。
あまりにもあちこちで聞くのでここで繰り返すのもアレなんですが(^^; yaccというのは、 Yet Another Compiler Compiler の略だそうで、要は「コンパイラ生成器」ってことなんでしょうけど、 実際にはそれはいくらなんでも言い過ぎで(^^; yaccがやってくれるのは、コンパイラの中でも、 「構文解析器(パーサ)」の生成だけです。
yaccは、文法を与えることにより、構文解析器を自動生成してくれます。 構文解析と言えば、チョムスキーの...
いや、やっぱり、自分でもよくわかっとらんようなことを 書こうとしちゃいけませんね(^^;
ま、ざっくり言えば、yaccがやってくれることは、 テトリスのようなもんだと思ってください。
たとえば、整数の四則演算ができる電卓を作るなら、 以下のような構文規則を与えます。
expression /* 「式」とは... */
: term /* 「項」 */
| expression '+' term /* または、「式」 + 「項」 */
| expression '-' term /* または、「式」 - 「項」 */
;
term /* 「項」とは... */
: primary_expression /* 「一次式」 */
| term '*' primary_expression /* または、「項」 * 「一次式」*/
| term '/' primary_expression /* または、「項」 / 「一次式」*/
;
primary_expression /* 「一次式」とは... */
: INTEGER_LITERAL /* 整数の即値 */
| VARIABLE_NAME /* または、変数名 */
;
この規則の中には、 「乗除算は加減算より優先順位が高い」 「加減算・乗除算共に結合規則は左から右だ」 という規則が含まれています。 実際には、yaccでは、 演算子の優先順位を別途定義することが出来るのですけれども、 私は、いつも、 K&Rの付録に載っている C の構文規則をまる写ししてしまうので(^^; 結局、yaccの機能には頼らず、 このように構文規則中で優先順位を規定しています。
例えば、「12 + 3 * a」という入力があったとすると、 yacc内部のスタックに、 レキシカルアナライザで分割されたトークンが、 テトリスのブロックの如く、右の方から降ってきます。
このように、トークンが降ってきて積み上がることを、 shiftと呼びます。
「12」というトークンは、INTEGER_LITERALですから、 トークンが落ちると同時に、上記規則のうち
primary_expression /* 「一次式」とは... */
: INTEGER_LITERAL /* 整数の即値 */
にひっかかり、 「primary_expression」に変換されます。
このように、何らかの規則に引っかかって変換されることを、 reduce(還元)と呼びます。
「primary_expression」は、さらに、
term /* 「項」とは... */
: primary_expression /* 「一次式」 */
にひっかかって、「term」にreduceされ、
さらに、
expression /* 「式」とは... */
: term /* 「項」 */
により、「expression」にreduceされます。
次に、「+」が降ってきます。この状態では、どの規則にもマッチしませんから、 おとなしくshiftします。
次に、「3」が降ってきます。
さっきと同じ規則により、「3」(INTEGER_LITERAL)は、 「primary_expression」を経由して「term」にreduceされます。
ここで、次の規則にマッチしたわけですが、
expression /* 「式」とは... */
| expression '+' term /* または、「式」 + 「項」 */
yaccは、これまたテトリスがそうであるように、
次に落ちてくるトークンが何であるかを、ひとつだけ先読みしています。
ここでは、次に落ちてくるのが「*」であることが分かっているので、
term /* 「項」とは... */
| term '*' primary_expression /* または、「項」 * 「一次式」*/
にマッチできる可能性があると考えて、さらにshiftします。
さらに、「a」(VARIABLE_NAME)が降ってきて、
「primary_expression」にreduceされると、
term /* 「項」とは... */
| term '*' primary_expression /* または、「項」 * 「一次式」*/
にマッチして、「term」にreduceされます。
さらに、「expression」「+」「term」は、
expression /* 「式」とは... */
| expression '+' term /* または、「式」 + 「項」 */
にマッチするので、最終的に「expression」にreduceされます。
ところで、yaccでパーサを作る際に結構面倒なのは、 実は構文規則のデバッグだったりします。
yacc自体、エラーには随分寛大な方で、 例えば規則の後ろのセミコロンを付け忘れても、 なんとかそれらしく解釈しようと努力する、 なんて余計なことをしてくれるおかげで、 余計厄介なんですが、それは置いておくとしても、 構文自体のコンフリクトの解消も、かなり大変だったりします。
コンフリクトとは、 あるトークンが降ってきたとき、複数通りのreduceが考えられたり、 shiftしたもんだかreduceしたもんだかわからん、 という状態を指します。 ものの本には、reduceとreduceのコンフリクトは致命的だけど、 shiftとreduceのコンフリクトはたいしたことないよ、 なんて書いてあったりしますけど(shiftが優先される)、 やっぱり気持ちが悪いので、全て潰しておきたいものです。
yaccをかける際に、-vオプションを付けると、 標準yaccの場合、y.outputというファイルが生成されます (bisonでは.yファイルのサフィックスに.outputを付けたファイルができる)。 このy.outputファイルには、 どこでどうコンフリクトが起きているかが記述されています。
とりあえず、先程の構文規則の以下の部分を、
expression /* 「式」とは... */
| expression '+' term /* または、「式」 + 「項」 */
こんなふうに変更しちまいましょう。
expression /* 「式」とは... */
| expression '*' term /* または、「式」 * 「項」?(間違い) */
この変更により、3個所のshift/reduceコンフリクトが発生します。
% yacc -dv test.y yacc: 3 shift/reduce conflicts
んで、y.output(bisonならtest.output)ファイルを見てみます。
まず、前半部分は、.yファイルに書いてある規則そのままです。 ただし、"|"(または)で規定された規則は展開されて、 各規則に番号が振られています。
0 $accept : expression $end 1 expression : term 2 | expression MUL term 3 | expression SUB term 4 term : primary_expression 5 | term MUL primary_expression 6 | term DIV primary_expression 7 primary_expression : INTEGER_LITERAL 8 | VARIABLE_NAME
続きは、パーサが取り得る「状態」を順次記述しています。
先程のテトリスの例だと、パーサは、なんかトークンが降ってくる度に、 スタックの頭の方をいちいちスキャンして、 「あ、このパターンはこの規則にマッチしてるじゃん」 と認識しているみたいに見えるかも知れませんが、 それではコンパイルが遅くなってしまいます。
というわけで、実際には、yaccは、パーサを生成する段階で、 パーサが取り得る状態を全てリストアップし、 「この状態の時にこれが降ってきたら次はこの状態になるんだな」 というテーブル(パーステーブル)を作ります。 y.outputの後半には、それが延々と記述されているわけです。 麻雀で言う所の、「××待ち」って奴でしょうか。 私は麻雀やらないんでよくわからないんですが(^^;
んで、それぞれの状態について、ここでコレが降ってきたら、 この状態にshiftする、またはこの規則に基づいてreduceする、 ということが記述されています。 例えば、先程無理矢理コンフリクトを起こした規則では、 y.outputには、以下のように出力されています。
4: shift/reduce conflict (shift 8, reduce 1) on '*' state 4 expression : term . (1) term : term . '*' primary_expression (5) term : term . '/' primary_expression (6) '*' shift 8 '/' shift 9 $end reduce 1 '-' reduce 1
'*'が降ってきたとき、 8という状態(state)にシフトしていいんだか、 1という規則にもとづいてreduceしていいんだかわからん、 と言ってますね。 state 4 というのが状態の番号、 以下の3行が、今の状態だとそのうちreduceしそうな規則で ピリオドは、今、その規則にマッチするのに、 どこまで来てるか(うーんうまく表現できない)を意味しています。
8という状態とは、y.outputによれば、以下の状態で、
state 8 term : term '*' . primary_expression (5) INTEGER_LITERAL shift 1 VARIABLE_NAME shift 2 . error primary_expression goto 12
1の規則とは、以下の規則ですね(shiftする番号はstateの番号で、 reduceする番号はruleの番号であることに注意してください)。
1 expression : term
要するに、「項」がある所に'*'が降ってきたら、 「項」の続きだと思ってshiftしていいのか、 「項」をもう終わりとして expressionにreduceしていいのかを決めかねていることになります。 これはつまり、'+'を'*'に変えちゃったせいで、 えらく低い優先順位の'*'が出来ちゃったことによる混乱です。
state 4 のreduce条件にある通り、termのある所に '-'が来たら無条件で expressionにreduceしていいわけですが、 '*'でも同じことになる、ということですからね。
ま、y.outputの意味はこんな所なんですが、 この報告から原因を究明し、コンフリクトを潰すのは、 少なくとも私にとってはなかなか困難だったりしてます。 ホントに(;_;)
てなわけで、今回の電卓の構文規則 (calc.y)を見ていきます。
先頭の %{ から %} までには、lexと同様、Cのコードが書けます。 ここで、YYDEBUGを1にしてますが、これがあると、 yydebugをデバッガとかで非ゼロにしてやることで、 パースの状態を実行時に見ることができます。
次の
%union {
char *identifier;
ParameterList *parameter_list;
Expression *expression;
}
において、トークンや非終端子の型となる共用体を定義しています。
トークンの型については、calc.lの所でちょっとだけ説明しました。 トークンの値は色々な型を持つので、共用体にするわけですね。
非終端子というのは、先程の例のtermとかprimary_expressionとかを指します。 トークンは、構文規則では末端なので、トークンが組み合わさったものを、 トークンと対比して非終端子と呼びます。
非終端子も、やっぱり色々な型を持つので、トークンと一緒に共用体にします。
この共用体が、すなわちテトリス風yaccスタックの要素の型になるわけです。
そして、以下の部分で、トークンの宣言(必要であればその型も)と、 型の必要な非終端子の宣言を行なっています。 非終端子は、型が不要なら、特に宣言する必要はありません。
%token <expression> INT_LITERAL
%token <expression> DOUBLE_LITERAL
%token <identifier> IDENTIFIER
%token DEFINE IF ELSE WHILE LP RP LC RC SEMICOLON COMMA ASSIGN
EQ NE GT GE LT LE ADD SUB MUL DIV MOD
%type <parameter_list> parameter_list
%type <expression> expression expression_list
equality_expression relational_expression
additive_expression multiplicative_expression
unary_expression postfix_expression primary_expression
if_expression while_expression
ここでトークンを宣言することにより、 y.tab.hというヘッダファイルでトークンの種類を表す名前が #defineされて(-dオプションを付けた場合)、 lex側のファイルでも使えるようになります。
そして、%%以降がいよいよ構文規則です。
最初の規則で、パース対象全体を表現します。
translation_unit
: definition_or_expression
| translation_unit definition_or_expression
;
今回の電卓では、関数定義するか、 式を直接入れて計算させるかの繰り返しですから、 翻訳単位(translation_unit)とは、 definition_or_expressionの繰り返しだよ、 ということを言っています。 再帰的定義で繰り返しを表現している所に注意してください。 これはyaccの定石です。
そいで、definition_or_expressionとは何かと言えば、 関数定義(function_definition)または、 式(expression)にセミコロンを付けたものだよ、と言ってます。
definition_or_expression
: function_definition
| expression SEMICOLON
{
clc_eval_expression($1);
}
...
構文規則の下に、中括弧で囲まれたCのソースが挿入されていますが、 これは(lex同様)アクションと呼ばれるコードで、 reduceと同時に実行されます。
アクションの中で具体的に何をしているか、ということは後述しますが、 アクションの中では、yaccのスタックの内容を、 $1〜$nという表記により参照することができます。
たとえば、以下の規則では、
additive_expression
...
| additive_expression ADD multiplicative_expression
{
$$ = clc_create_binary_expression(ADD_EXPRESSION, $1, $3);
}
additive_expression を $1で、
ADD を $2で、
multipricative_expression を $3で、
それぞれ参照できます。
$$は、reduceした後にスタックに生成される要素です。
ちなみにこれ、最終的にCのコードに展開された時、 どのようになっているかというと、FreeBSD付属のyaccでは、 こんなふうになりました。
{
yyval.expression = clc_create_binary_expression(ADD_EXPRESSION, yyvsp[-2].expression, yyvsp[0].expression);
}
yyvspというのが、スタックの先頭を指してますので、 yyvsp[0], yyvsp[-1], yyvsp[-2] により先頭の3つを参照できます。 そして、yyvsp[n]自体は共用体なのですが、 additive_expression, multipricative_expression共に型の宣言をしてあるので、 ちゃんと共用体のexpressionメンバを参照してくれるわけです。
図にすると、こんな感じでしょうか。
構文規則の詳細はいちいち説明しません。 まあ、たいした規則じゃないですし、見ればわかると思いますので。
私、yaccはずっと使ってますけど、 yaccのエラー規則を書くのは実はこれが初めてだったりします(^^;
今まで作ってきたのは、たいていファイルを食ってコンパイルして何かする、 というものだったので、エラーが出たらその場で終了、 という方針でさほど困らんじゃん、と思っていたからです。
Cコンパイラとかで、ソースをコンパイルすると、 エラーメッセージがずらずらずらーっと出てきますよね。
でも、私は横着なんで、どうせ最初の1個か2個しか見ないんです。 後の方のエラーは、最初のエラーの波及効果で出てることが多いので、 最初のエラーを潰して、残りのエラーがちょっとでも減れば、 結局トータルの所要時間は減ることになります。 コンパイルなんて今時のマシンなら一瞬なんですから。
でも、今回作っているのは対話的な電卓なので、 さすがに1回のシンタックスエラーで全てを終了されてしまってはたまりません。 というわけで、最も原始的なエラーリカバリを付けました。
definition_or_expression
: function_definition
| expression SEMICOLON
{
clc_eval_expression($1);
}
| error
{
yyclearin;
}
;
「error」というトークンは、エラーにマッチします。 つまり、関数定義や、式の途中で文法エラーが発生したら、 その場でreduceしてしまえ、ということです。 アクションの中のyyclearinは、先読みしてあるトークンを破棄します。
ところで、エラー状態からの回復というのは、なかなか微妙な問題で、 たとえば、
1 + 2 + 3 + 4;
と入れるべき所を、
1 + 2 + 3 3 + 4;
と入れると、ふたつ目の3でエラーになって、 そこまでの入力を破棄するわけですが、 次に、いきなり+が来たってエラーに決まってますから、 エラーメッセージが2回表示され... たら嬉しくないですよね。
というわけで、yaccでは、 「最低3つのトークンをエラーなしで読み込めた時」までは、 エラーの報告を抑止するそうです。
上のプログラムの、yyclearin; の下に、
yyerrok;
を付け加えると、即座に正常状態に復帰するようになります。
この電卓の場合、式の入力ではセミコロン、 関数定義の入力では'}'という、終端になる記号があるので、 たとえば、
| expression error SEMICOLON
のようにして、 セミコロンまでを読み飛ばすようにした方が良いかもしれません。
電卓の場合どれだけの必然性があるかわかりませんけれども、 私は、何かプログラムを書く時には、 出来るだけライブラリ(モジュール)の形にしています。
というわけで、ここのルールに基き、 この電卓モジュールは、"CLC"という名前にします。CALCの略... ヒネリも何もないですね。
CLCのパブリックヘッダファイルCLC.hは、 以下のようになっています。
#ifndef PUBLIC_CLC_H_INCLUDED
#define PUBLIC_CLC_H_INCLUDED
#include <stdio.h>
typedef struct CLC_Interpreter_tag *CLC_Interpreter;
typedef enum {
CLC_TTY_INPUT_MODE = 1,
CLC_FILE_INPUT_MODE
} CLC_InputMode;
CLC_Interpreter CLC_create_interpreter(void);
void CLC_interpret(CLC_Interpreter interpreter, FILE *fp,
CLC_InputMode input_mode);
void CLC_dispose_interpreter(CLC_Interpreter interpreter);
#endif PUBLIC_CLC_H_INCLUDED
CLC_create_interpreter()で電卓のインタプリタのインスタンスを生成します。 他の関数は、このインスタンスに対して何かをするものですので、 インタプリタを第1引数に取ります。
CLC_interpret()は、インタプリタを用いて実際に解釈を実行します。 ひとつのインタプリタのインスタンスに対し、複数回、 CLC_interpret()を呼び出しても構いません。 インタプリタが同じなら、関数定義・グローバル変数は継続して使えますので、 例えば、関数が定義されたファイルを事前に読み込んでおいて、 それから対話モードでインタプリタを起動する、という使い方が出来ます。
んで、第1引数として受け取ったインタプリタですが、 CLC内部において、これを延々と引数で持って回るのは面倒臭いので、 今回の実装では、 とっととグローバル変数(clc_current_interpreter)に入れてしまっています。 外部のインタフェースに影響を与えない範囲でなら、 この程度の手抜きはアリだと思ってます。私の場合。
calc.yにおけるアクションの大半は、 解析木の構築を行なうためのものです。
いちいち説明するほどのものでもないので、 create.cと、 calc.hを見てください。 木構造を、葉の方から順に作っていってます。
clc_create_binary_expression()において、 一応最適化らしきことをやっています。 つまり、2項演算子の両側が定数だったら、 その場で評価して定数のノードに畳み込んじゃってます。
で、最終的には、関数定義の場合は、最後にclc_function_define()がコールされ、 インタプリタの関数リストに FunctionDefinitionを追加します。
電卓感覚で式を入力している場合は、clc_eval_expression()がコールされ、 式の評価が開始されます。
解析木の評価は、eval.cでやってます。
解析木を評価する eval.c では、解析木に対して、一切書き込みを行ないません。 式の評価は、解析木に対しては、純粋にread onlyです。
基本的には、eval_expression()を起点として、 解析木を帰りがけ順(post order)でトラバースし、 評価した結果を、共用体を含む構造体Valueに詰めて、 構造体の実体返しで順次返しているだけです。
構造体Valueの定義は、こんなふうになっています。
typedef struct {
ValueType type;
union {
int int_value;
double double_value;
} u;
} Value;
この電卓で扱う型は、整数型と実数型だけなので、 intとdouble共用体で結果を返すわけですね。
eval_expression()から呼び出される、各種の評価関数は、 eval_int_expression(), eval_double_expression()のようなごく簡単なものを除いて、 第1引数に LocalEnvironment * を取ります。 これは、関数を実行中に、 現在実行中の関数の環境を保持するための構造体です。
よって、最初はNULLなのですが、関数呼び出しがあった時に新しく生成されます。 eval_function_call_expression()を参照してください。
現在は、LocalEnvironmentは、 ローカル変数(Variableにより連結リストで保持される)を保持するための ポインタだけを持っています。
typedef struct Variable_tag {
char *name;
Value value;
struct Variable_tag *next;
} Variable;
typedef struct {
Variable *variable;
} LocalEnvironment;
変数を評価している所(eval_identifier_expression())では、 先にローカル変数を検索してから、グローバル変数を検索しています。 代入する所では、先にローカル変数を検索し、次にグローバル変数を検索してから、 どちらにもその名前の変数が存在しなければ、 関数実行中ならローカル変数に、さもなければグローバル変数に、 新しい変数を生成しています。
...てえことは、関数内では、新しくグローバル変数を作り出すことは、 不可能ってことになっちゃいますね。(^^;
ちなみに、グローバル変数は、CLC_Interpreterが保持しています。 ま、当たり前ですが。
次は、Cプログラマの共通の悩みの種、メモリ管理です。
今回は、以下のようなアプローチを採用しています。
今回の電卓のエラー処理は、大きくふたつに分けられます。
コンパイル時のエラーは、clc_compile_error()を呼び出しています。
文法エラーは、yaccが生成した解析ルーチンが捕捉して、 yyerrorという関数をコールします(名前決め打ち...)。 てなわけで、これを再定義してやれば、 自分のエラー処理ルーチンを呼び出すことができます。
さて、コンパイル時のエラーは、 関数の呼び出し階層がそんなに深くならないので、 現在作成中の解析木をストレージごと破棄してやればそれでいいんでしょうが、 問題は、解析木の評価中に発生するエラーです。
解析木の評価は、解析木を再帰でもって辿りながら行ないます。 つまり、関数の呼び出し階層のかなり深い所で、 突然エラーが発生するかも知れません。
Cにおけるエラー処理の方法としてよく見るのは、
といった方法ですが、これ、どちらの方法を取るにせよ、 いかにもチェックを忘れそうですし、何より面倒臭いです。 さらに、今回のプログラムでは、Value構造体を返すために、 関数の戻り値は既に使われています。
「C++やJavaなら例外処理が使えるのに...」
いや全くその通り。
C++やJavaが使える/使いたいならそうすれば良いでしょう。
でも、人生そうそう思い通りにはいかないのが人の世の常なのであって、 何らかの事情でCを使わなければならないとか、 個人的趣味でどうしてもCを使いたいとか(^^; の場合に、 隣りの芝生を羨んでも得るものがあるわけじゃなし、 Cを使うなら、Cなりの方法をとるのがオトナの判断というものです。
C++やJavaの例外処理機構ってのは、要するに、
というものです。
Cなら、まさにsetjmp()/longjmp()がそのような動きをします。
...そこのボク、ひかないように。
かのDijkstra先生をひもとくまでもなく、 周りの人はみんなgotoはダメだって言う、 関数の中にしかジャンプできないgotoでもこんなに悪く言われるのに、 ましてや関数すら飛び越してジャンプしてしまう(?)「long」な 「jmp」なんてとんでもない、という意識ってのは、 世間にはやっぱりあるのかも知れません。
でも、何事も、良いか悪いかはちゃんと調べてみなければわかりません。 自分で使いもしないうちから、「こんなのダメだ」と否定するのも、 頭の悪い話ですよね。
てなわけで、setjmp()/longjmp()を簡単に説明すると、
setjmp()は、環境を保存した時にはゼロを返し、 longjmp()から戻って来た時には、longjmpの第2引数を返します。
たとえば、Javaで、
try {
処理;
} catch (HogeHogeException err) {
HogeHogeExceptionの時の処理;
} catch (PiyoPiyoException piyo) {
PiyoPiyoExceptionの時の処理;
}
こうなっているものを、setjmp()/longjmp()で置き換えるとこうなります。
/* 呼び出し元の環境を保持するために、グローバル変数をひとつ用意する */
jmp_buf recovery_environment;
/* エラーコードの定義 */
#define HOGE_HOGE_EXCEPTION (1)
#define PIYO_PIYO_EXCEPTION (2)
...
int error_code;
if ((error_code = setjmp(recovery_environment)) == 0) {
処理;
} else if (error_code == HOGE_HOGE_EXCEPTION) {
HOGE_HOGE_EXCEPTIONの時の処理;
} else if (error_code == PIYO_PIYO_EXCEPTION) {
PIYO_PIYO_EXCEPTIONの時の処理;
} else {
/* ここには来ない筈... */
assert(0);
}
例外を投げる方は、こんな感じです。
Java版: throw new HogeHogeException(); C版: /* recovery_environmentに設定した環境まで戻る */ longjmp(recovery_environment, HOGE_HOGE_EXCEPTION);
どうでしょう?
いつもこんな単純な置き換えで済むわけではないですが、 状況を限れば、使えるワザだと思います。
# 2000/6/15追記: # 今回の例の場合、関数の中でエラーが発生するとローカル変数の領域を開放 # し損ないますな。よく考えたら (^^; # ま、これぐらいなら放っとこうかという気になりますが、そのうち気が向いたら # 直すかも知れません。
ところで、setjmp()が、「呼び出し元の環境を保存する」には、 jmp_bufという型を使用しますが、setjmp()を呼び出す際に、
setjmp(recovery_environment)
のように、& も付けずに呼び出してます。
注意深い人は、「あれえ? Cだと引数は常に値渡しの筈だから、 こんなふうに呼び出しても、 recovery_environmentには何も設定できないよなあ」と思ったかも知れません。
てなわけで、jmp_bufの定義を見てみると...
typedef struct { int _jb[_JBLEN + 1]; } jmp_buf[1];
jmp_bufという型は、 構造体の配列(要素数1)として定義されていますね。 配列だから、式の中では、勝手にポインタに読み替えられていたわけです。
...なんか、姑息なワザというか、混乱を増すだけなんじゃないかって気がしますが。
とりあえず、HTMLは、こっち。
tar + gzで固めたものは、こっち
LHA圧縮形式は、こっち
Windows用実行形式(圧縮版)は、こっち
注)cygwin.dllが必要です。
コンパイルする場合は、展開したディレクトリ(mycalc)から、 サブディレクトリmemory/とdebug/に、それぞれcdしてmakeし、 その上でmycalc直下でmakeをかけてください。
改行コードは、tar + gz版はLF、LHA版は CR+LFです。
補足(2003/4/21)
以前、ここに置いてあったソースは、 interface.cのCLC_create_interpreterにおいて、variableメンバの 初期化が抜けていました。 2003/4/21にこの問題は修正しました。
CLC_FILE_INPUT_MODEにもバグがあるような気がしますが、とりあえずこちらは放置です。
今回は、C言語の話からちょっと離れてしまいました。
しかも長い! HTMLだけ見ても、いつもの倍ちかくいってます。
# 更新が遅れたのは、他のことをやってたためで、必ずしも文章が長いから # だけではないんですが...
次回は、もうちょっと軽めのネタで行ってみたいと思います (^^;
ひとつ上のページに戻る | ひとつ前の話 | ひとつ後の話 | トップページに戻る