実験のてびき

渕野 昌 (Sakae' Fuchino)

解説
本実験では,UNIX のスタンダードな tools である lex と yacc の GNU project による改良版の flexbison を用いて,C プログラムの整形ツールと, 簡易電卓(また余力のある人はさらに 簡単な言語のインタプレータ) のプログラムを作成する. flex (lex) は,字句解析プログラムの自動生成 tool で(マニュアルによると flex は fast lexical anayzer generator の略であるとある),bison (yacc) は, 構文解析プログラムの自動生成 tool である(bison の名前の由来は不明だが,GNU やその周辺では gnu, bison, mule など, ウシ・ウマ系の動物の名前をプログラムにつける伝統がある --- yacc は yet another compiler compiler であったと思う). まず,1回目の実験のベースになるプログラム format3.l を 例として見てみよう:

課題1の手引き: C ソース・プログラムの整形ツール

format3.l は C ソース・プログラムが与えられると,これの インデントを整えて出力するようなプログラムである. ただし,このプログラムはまだ完成版ではなく,与える C プログラムによっては うまく整形できないものもある.format3.l は flex の言語で書かれているので.このプログラムから実行プログラムを生成するには, まず flex を用いて format3.l を C の ソースプログラムに変換しなくてはならない.このためには, まず format3.l を自分のディレクトリーとってきて,このファイルを
% flex format3.l 
として flex にかける.この結果 lex.yy.c という名前の C プログラムが出力される. このファイルを今度は
% cc  -o format lex.yy.c
と C コンパイラでコンパイルすると,format という名前の実行プログラムが出力される. このプログラムは標準入力から入力された C ソースファイルを整形して, その結果を標準出力に出力するようになっている. たとえば,
for(;;){
for(;;){
for(;;){
for(;;){
for(;;){
x++;
}
}
}
}
}
というべた書きの C ソースプログラムが,testing-indent.c という名前でセーブされているとして, これを testing-indented.c という名前の整形されたプログラムファイルに変換するには,
% cat testing-indent.c | ./format > testing-indented.c
として先程作成したツール format を呼びだす. この結生成される testing-indented.c は
for(;;){
  for(;;){
    for(;;){
      for(;;){
        for(;;){
          x++;
        }
      }
    }
  }
}
と整形されたものになっている.

課題2のてびき: 簡易電卓プログラムとその解説

簡易電卓プログラム scalc のソースファイルは scalc.lscalc.y があり,scalc.l は flex で自動生成される字句解析のルーチンの (flexのプログラム言語での)ソースプログラム,scalc.y は, bison で自動生成される構文解析(と電卓計算)のルーチンの(bisonのプログラム言語での)ソースプログラムである. 実行プログラムをこれらのソース・ファイルから作成するには,まず,
% bison scalc.y 
として scalc.tab.c を生成する. 次に
% flex scalc.l 
として lex.yy.c というファイルを生成する.このファイルは scalc.y の終り書いた
#include ".../lex.yy.c"
によって scalc.tab.c から呼びだされる.ただし,ここで ... にはもともとの実験のホームページのディレクトリー名が書かれているので, ファイルをコピーして自分のところで実行ファイルを生成するためには, ... を各人の path 名に変更する必要がある. 終りに,
% cc scalc.tab.c -ll -o scalc
として scalc.tab.c をコンパイルすると,実行ファイル scalc が得られる.

scalc は算術表現を標準入力から得て結果を標準出力に出すようになっている. コンソールが標準入力の場合には, ".RET"か"RET"を空行でタイプすると,プログラムからぬけられるようになっている.

例:

% ./scalc
50+1
The result is: 51.000000
34/23
The result is: 1.478261
((20+45)/70+1.34)/34.4678
The result is: 0.065817
.
%
適当でない表現を入力するとエラーメッセージを出して止まる.

例:

% ./scalc
50+1)
parse error
% 
もちろん入出力をリダイレクトして他のプログラムと組み合せて使うことも可能である:

例:

% echo "(30.14+173)*3.1415927+25" | ./scalc
The result is: 663.183141
%

scalc.l と scalc.y を自分のところにコピーして,以上を確かめてみなさい.

scalc のソースプログラムを見てみることにする.scalc.l から, 字句解析の関数 yylex() が生成され,scalc.y から構文解析の関数 yyparse() が生成される.算術表現の計算と表示は,yyparse() の side effect の形で 実現されている.yylex() は yyparse() から subfunction として呼びだされる.

まず,scalc.l を見てみる.lex/flex のプログラムは,

C の宣言文
%%
字句解析の規則
%%
ユーザー・コード
という形をしている,字句解析の規則は,拡張された regular expression と, それにマッチした場合の動作の記述からなる. lex/flex で出力される C 言語のプログラムでは, C の宣言文の部分とユーザーコードの部分が,それぞれプログラムの頭と終りに付加され, 字句解析の規則に対応する yylex とそれに付随した subfunctions などが, これらの間に書きこまれる. 我々の例では,

scalc.l のソースコード:

%%
"+"    return (ADDOP);
"-"    return (SUBOP);
"*"    return (MULOP);
"/"    return (DIVOP);
"("    return (LPAR);
")"    return (RPAR);
"."    return (OWARI);
[0-9]+\.[0-9]*|[0-9]+ { sscanf (yytext, 
         "%lf", &yylval); return (NUMBER); }
[ \t]  ;
^\n    return (OWARI);
\n     return (NL);
.      return (yytext[0]);
%%
となっていて,C の宣言文とユーザーコードの部分は空である. 字句解析の規則の記述は各行が,
正規表現 空白 C 言語による動作の記述
となっている. "ADDOP", "SUBOP" etc. は scalc.y で定義される enumeration type の定数で,それぞれ 加法演算子,減法演算子 に対応する token である.定数にマッチした場合には, "NUMBER" という token それの attribute としての浮動点小数値が返されるが,この attribute は,scalc.y で定義される YYSTYPE という型の yylval という global variable に格納されて構文解析に渡される.

次に scalc.y のソースコードを見てみる.yacc/bison のソースコードも, lex/flex と似た,

%{
C の宣言文
%}

Bison の宣言文

%%
文法規則
%%

ユーザー・コード
という構成になっている.

scalc.y のソースコード:

%{
#define YYSTYPE double
#include <stdio.h> 
#include <math.h> 
%}
%token NL
%token NUMBER
%token LPAR
%token RPAR
%token OWARI
%left ADDOP SUBOP
%left MULOP DIVOP
%left NEG
%%
s       : list
        ;
list    : /* empty */
        | list expr NL { printf ("The result is: %lf\n", $2);}
        | list OWARI { return;}
        ;
expr    : expr ADDOP expr {$$ = $1 + $3;}
        | expr SUBOP expr {$$ = $1 - $3;}
        | expr MULOP expr {$$ = $1 * $3;}
        | expr DIVOP expr {$$ = $1 / $3;}
        | SUBOP expr %prec NEG {$$ = -$2;}
        | LPAR expr RPAR  {$$ = $2;}
        | NUMBER {$$ = $1;}
        ;
%%
yyerror(s) char  *s; { printf ("%s\n",s);}
main()
{yyparse();}
#include "/var/home2/fuchino/public_html/experimentIII-1998/lex.yy.c"
ここで,YYSTYPE は前に述べた,構文解析の各段階で受け渡される semantic value の型で,我々の例では,これは double 型の浮動点小数となっている. コンパイラや次の課題で考察するインタプレータでは, これは,構文木の型として定義されることになる. %token と %left, %right でトークンの宣言がされている. %left, %right はそれぞれ左結合則,右結合則を満たす演算記号の宣言である.

次の %% の後で,文法規則が定義されている. Backus Nauer Form に準ずる書きかたになっていることが分ると思う. { と } で囲まれた部分は,構文にマッチしたときの C であらわされる動作の規定で, たとえば,

expr    : expr ADDOP expr {$$ = $1 + $3;}
            .
            .
            .
となっていて,expr ADDOP expr にマッチしたときには,$$ であらわされる左辺の expr の semantic value を, $1 であらわされる右辺の最初の expr にマッチする表現の semantic value と, $2 であらわされている右辺の二つめに現れる expr にマッチする表現の semantic value の和とする,という動作の規定となっている.

二番目の %% の後には,scalc の main() 関数と,エラーが生じた場合に呼ばれる yyerror() の定義がされている.最後に flex によって生成された, lex.yy.c が読み込まれている. ここで簡易電卓プログラムのときと同様に,

#include ".../lex.yy.c"
の行の path 名をあらかじめ各人のものに変更する必要があることに注意.

簡易電卓プログラムの拡張の可能性の示唆

上の簡易電卓で,比較的簡単に実現できる改良点としては, 次のようなことがらが考えられる: 次に,2回目の実験のおまけの課題のベースになるプログラムの例を見てみよう.

簡易言語のインタープレータとその解説

2回目の実験のおまけの課題では, C を簡易化したような言語のインタープレータを bison と flex を用いて作成する. 以下の例で用いる言語は,次のようなものである: 文法は C に準ずる.ただし, 変数は x1, x2, x3, ... のみがあらかじめ用意されており,すべて double 型 とする(したがって変数の宣言は存在しない). 実行文は
xi = 算術式;
算術式の評価の結果を変数 xi に代入
printstr("...");
記号列 "..." の標準出力への出力
printvar( xi );
変数 xi の値の標準出力への出力
の形をしているもののみとする. flow control としては,
while(算術式){ 
実行文(複数)
}
のみが用意されている. これの解釈は,算術式の評価の結果が正の実数となっている間 '{' と '}' の間の実行文の順次実行をくりかえす.while 文の入れ子は可能である. 算術式と条件文の区別はしない.条件演算子は < のみが用意されていて, これは二項演算子と解釈され,条件が正しいか正しくないかによって,1.0 か 0.0 を 返すものとする.その他の演算子としては,+, -, *, /, が用意されている. C と同じように,/* と */ でかこんだところがコメントとなる. 関数の概念はない.したがって,プログラムは,最初の行から実行され, 最終行に達したところで終了する. 上の言語のインタープレータ itpr のソースファイルを後に示すが,これを,たとえば,
example.x:

printstr("**  This is a test  **\n\n");
x1 = 5;
x0 = 1;
while (0 < x1){
	x1 = x1 - 1;
	x0 = x0 * 2;
	x2 = 5 - x1;
	while (0 < x2 ){
		printstr("*");
		x2 = x2 - 1;
	}
	x2 = x1 + 2;
	while (0 < x2 ){
		printstr(" ");
		x2 = x2 - 1;
	}
    printvar(x0); printstr("\n");
}
に,
% itpr example.x
として実行すると,
**  This is a test  **

*      2.000000
**     4.000000
***    8.000000
****   16.000000
*****  32.000000
% 
という結果が得られる. itpr のソースファイル(複数)を見てみることにする. itpr のソースファイルは, 次のものからなる:
interpreter.h
構文解析の際に生成される中間言語のインタプレータの命令系の説明が記入してある.
interpreter.iprg.c
中間言語のインタープレータとそれに関連する関数
interpreter.tree.c
構文解析でサイドエフェクトとして中間言語のコードを生成してゆく際に必要となる, 構文木の扱いのためのライブラリー
interpreter.misc.c
演算子の定義 etc.
interpreter.y
bison の文法で書かれた構文解析プログラム main etc.
interpreter.l
flex による字句解析プログラム,interpreter.l から生成される lex.yy.c は interpreter.y から生成される interpreter.tab.c から include される.
上のプログラムをベースとして,以下のような考察およびプログラミングを行なうこと: 第二回目の実験のおまけの課題. 次に itpr の改良の可能性について考えてみる. 次のリストでは,上から下にむかって,難易度が上ってゆく:

インタープレータ itrp の拡張の可能性の示唆

  • 論理演算 ||, &&, ! を implement する
  • 記号列で,C と同じように \" として引用符を与えられるように変更する.
  • sin, cosin など,C の数学ライブラリーに含まれている関数が使えるようにする.
  • printstr と printvar を,C での printf のようなものに拡張する.
  • エラーの扱いをもっと気の効いたものにする(行番号の表示, それほど重大でなさそうなエラーからの回復など). これについては bison のマニュアルのここを参照.
  • 記号表の扱いをプログラムして, 定数を例えば constant pi=3.14159265358979; などとして定義できるようにする. また,変数を自分の好きな名前で呼びだせるようにする. なおこれについては bison のマニュアルでの が参考になる.
  • 文字変数(文字列へのポインタ)を導入して文字列のつなげあわせ, 部分文字列の抽出などの操作ができるようにする.
  • subroutine が呼びだせるように言語を改良して, 前の項目での記号表を用いてこれを実現する.

  • Sakae' Fuchino

    Email:fuchino@math.cs.kitami-it.ac.jp

    Last modified: Mon May 22 01:08:57 2000