課題内容 - Level.5 -
変数を使った四則演算コンパイラの授業の例題を参考にすると良い。 インタプリタで良いので、コンパイラの授業の例題をほぼそのまま使うことが出来るが...
作成したプログラムについて
今回作成したプログラムは前回のUNIX実験のLevel5を元にそのプログラムのバ
グ取り，及びその拡張として浮動小数が扱えることを目標として作成した．
ここでは，プログラムをトークンの作成，構文規則，new_node関数，
command関数の４つに分け，追加した部分を中心に説明する．
yaccの構文規則における終端記号をここで生成する．プロンプトで入力された 値を分割したものがvalueとして与えられるので，それらがどのトークンを 判定している．
577行目のgetIDはハッシュでの予約語を検索するもので，ここでは登録した 単語であるかを識別し，そうであった場合にはそれぞれを予約語として認識する．次の600行では変数として使用する値の初め は'$'，あるいは'@'であるとし，それであるものを変数('v')と認識する．602行で はvalueの初めの値が数値であった時にそれを数字('n')と認識させている．最後 にそれらに当てはまらなかったものをファイル('f')としている．
優先順位は下に位置するものほど順位が高い。これによって加算や減算より乗 算や乗算などが先に計算されるようになる．また，同じ優先度の場合には %leftや%rightで指定してどちらが先に解釈されるかを定義している． これらを定義することによってshift/reduce conflictを解消する働きになる．
次に構文規則についての説明を行なう．
以下が今回のプログラムの構文規則となっている．
token()関数により作成されたトークン(last_token)はこの構文規則を通過す ることになる．構文規則ではそれぞれに適応した規則についての還元が行なわ れる．
例えば'n'というトークンを考えたとき，'n'はnumという非終端記号と して還元され{}内の中の処理が行なわれる，その後，numはexpに還元され，同様 に{}内の処理が行なわれる．このような作業をすべてのトークンに対して行なう ことで最終的にtopへ還元され１つの構文木を作成し，処理が行なわれるよう になっている．
上記の部分はrightあるいはleftが変数のnode，則ちtypeが'v'であった時にそ の値を展開するかどうかを判定し，条件にあった場合(例えば1+\$aや@a*2な ど)はgetValue()でその値を取り出し，それをatof()した値をnumberに格納 して，nodeのtypeを'n'に書き換える．それによって以下の部分の演算処理 が行なえる状態にしている．
ここで演算の処理を行なっている．leftとrightのtypeが'n'つまりは数値であ り，自分自身のtypeが演算子であった時に行なわれる．
182行目のtypeが'$>$'であった時を説明すると，自分自身のtypeが'>'であった 時にleftのnumberとrightのnumberを比較し，真なら1を偽なら0をrightの numberに置き換え，不要となったleftのメモリを解放し，rightのnodeを次の nodeとして返す．といった処理を行なっている．省略しているがその他の演算 も同様にして行なっている．
224行からの処理はマイナスの規則をつけるための処理でtypeが'-'でrightの typeが'n'であった場合．例としては(-1+5)などの処理のために用いられる．
追記部分は次のようになっている．
d->typeでswitchさせて処理を行なう．'='の時の代入処理はleftが変数であり， rightに値がある場合に実行する．なお，この変数はhash表に保存されており， 文字列も格納できるためその判別も行なう．また，格納先はchar型で保存して いるため，数値もsprintf()を用いて文字列に変換し格納している．
トークン作成
トークンの作成は次で説明する構文規則に大きく関わってくる．Level5では 数値の計算を行なうため，コマンドラインから入力された値が数値であるか どうかを判断するための部分を追加した．token()関数一部
...
539 int
540 token()
541 {
～省略～
577 switch(getID(value)){
578 case 1:
579 last_token = WAIT;
580 break;
581 case 2:
582 last_token = ANS;
583 break;
584 case 3:
585 last_token = EXIT;
586 break;
587 case 4:
588 last_token = DELETE;
589 break;
590 case 5:
591 last_token = LIST;
592 break;
593 case 6:
594 last_token = DELKY;
595 break;
596 case 7:
597 last_token = DELALL;
598 break;
599 default:
600 if (value[0] == '$'|| value[0] == '@'){
601 last_token = 'v';
602 }else if (isdigit(*value)){
603 last_token='n';
604 }else{ // トークンタイプをファイルにする。
605 last_token = 'f';
606 }
607 break;
608 }
～省略～
594 return last_token;
595 }
596 }
...yaccの構文規則における終端記号をここで生成する．プロンプトで入力された 値を分割したものがvalueとして与えられるので，それらがどのトークンを 判定している．
577行目のgetIDはハッシュでの予約語を検索するもので，ここでは登録した 単語であるかを識別し，そうであった場合にはそれぞれを予約語として認識する．次の600行では変数として使用する値の初め は'$'，あるいは'@'であるとし，それであるものを変数('v')と認識する．602行で はvalueの初めの値が数値であった時にそれを数字('n')と認識させている．最後 にそれらに当てはまらなかったものをファイル('f')としている．
構文規則
優先順位の定義
42 // 優先度をここで決める。下のものほど優先度が高くなる。
43 %right '<' '>' '='
44 %left '+' '-'
45 %left '*' '/' '%'
46 %right '^'
47 %left '|' '&'
48 %left ';'優先順位は下に位置するものほど順位が高い。これによって加算や減算より乗 算や乗算などが先に計算されるようになる．また，同じ優先度の場合には %leftや%rightで指定してどちらが先に解釈されるかを定義している． これらを定義することによってshift/reduce conflictを解消する働きになる．
次に構文規則についての説明を行なう．
以下が今回のプログラムの構文規則となっている．
構文規則
...
52 // 構文解析部
53 top : expr { command($1); free_node($1);}
54 | exp { command($1); free_node($1);}
55 ;
～省略～
72 // 演算や変数の値の格納、参照
73 exp : num { $$ = $1; }
74 //マイナスの規則
75 | '-' num { $$ = new_node('-',NULL,0.0,NULL,$2); }
76 | file { $$ = $1; }
77 | val { $$ = $1; }
78 | cmd val { $$ = new_node($1->type,$1->value,0.0,NULL,$2); }
79 | cmd val '=' exp { $$ = new_node($1->type,$1->value,0.0,$2,$4); }
80 | cmd val '[' exp ']' {
81 $$ = new_node($1->type,$1->value,$4->number,NULL,$2); }
82 | exp '>' exp { $$ = new_node('>',NULL,0.0,$1,$3); }
83 | val '=' exp { $$ = new_node('=',NULL,0.0,$1,$3); }
84 | val '[' exp ']' '=' exp {
85 $$ = new_node('=',NULL,$3->number,$1,$6); free_node($3);}
86 //四則演算の規則
87 | exp '+' exp { $$ = new_node('+',NULL,0.0,$1,$3); }
88 | exp '-' exp { $$ = new_node('-',NULL,0.0,$1,$3); }
89 | exp '*' exp { $$ = new_node('*',NULL,0.0,$1,$3); }
90 | exp '/' exp { $$ = new_node('/',NULL,0.0,$1,$3); }
91 | exp '%' exp { $$ = new_node('%',NULL,0.0,$1,$3); }
92 | exp '^' exp { $$ = new_node('^',NULL,0.0,$1,$3); }
93 | '(' exp ')' { $$ = $2; }
94 ;
～省略～
107 // 変数
108 val : 'v' { $$ = new_node('v',value,0.0,NULL,NULL); };
109 // 整数
110 num : 'n' { $$ = new_node('n',NULL,atof(value),NULL,NULL); };
～省略～
116 arg : 'f' { $$ = new_node('a',value,0.0,NULL,NULL);arg_count++;};
token()関数により作成されたトークン(last_token)はこの構文規則を通過す ることになる．構文規則ではそれぞれに適応した規則についての還元が行なわ れる．
例えば'n'というトークンを考えたとき，'n'はnumという非終端記号と して還元され{}内の中の処理が行なわれる，その後，numはexpに還元され，同様 に{}内の処理が行なわれる．このような作業をすべてのトークンに対して行なう ことで最終的にtopへ還元され１つの構文木を作成し，処理が行なわれるよう になっている．
new_node関数
new_node関数はある規則にreduceした場合に行なわれ，reduce後の新しいノー ドを作成する．四則演算を用いるにおいては，その処理を行なう前に以下のよう な条件をつけ，変数を展開し，演算が行なえる状態に変更する．変数の展開処理
・・・
132 /* ---------------------------------------------------------------------
133 // leftが変数でなおかつtypeが'='じゃない場合に実行される。
134 // 変数の値をハッシテーブルから取り出す。その値がNULLだったらerrorメッセージ表示
135 // NULLでなくても、その値が文字であったらerrorメッセージ表示
136 // NULLでも文字でもなかったらその値をleft->numberに代入し、typeを'n'に変える。
137 // typeを'n'に変えることにより四則演算ができるようにする。
138 ------------------------------------------------------------------------*/
139 if(left && left->type == 'v' && type != '=') {
140 a = getValue(left->value,number);
141 if(a==NULL){
142 fprintf(stdout,"no such variable : %s\n",left->value);
143 }else{
144 if(isdigit(*a) == 0 && a[0] != '-'){
145 if(type!=DELKY)
146 fprintf(stdout,"no number : %s = %s\n",left->value,a);
147 }else{
148 left->number = atof(a);
149 left->type = 'n';
150 }
151 }
152 }
153 /* --------------------------------------------------------------------
154 // rightが変数でなおかつtypeが'='じゃない場合に実行される。
155 // ここで行なう作業は、leftとほぼ同じなので省略
156 -----------------------------------------------------------------------*/
157
158 if(right && right->type == 'v' && value == NULL) {
159 a = getValue(right->value, (int)number);
160 if(a==NULL){
161 fprintf(stdout,"no such variable : %s\n",right->value);
162 }else{
163 if(isalpha(*a) != 0 && a[0] != '-'){
164 if(type!=DELKY)
165 fprintf(stdout,"no number : %s = %s\n",right->value,a);
166 }else{
167 right->number = atof(a);
168 right->type = 'n';
169 }
170 }
171 }
・・・上記の部分はrightあるいはleftが変数のnode，則ちtypeが'v'であった時にそ の値を展開するかどうかを判定し，条件にあった場合(例えば1+\$aや@a*2な ど)はgetValue()でその値を取り出し，それをatof()した値をnumberに格納 して，nodeのtypeを'n'に書き換える．それによって以下の部分の演算処理 が行なえる状態にしている．
演算処理部分
・・・
180 if((left && left->type == 'n') && (right && right->type == 'n')){
181 switch(type) {
182 case '>':
183 right->number = (left->number > right->number);
184 free(left); return right;
185 break;
186 case '+':
187 right->number = left->number + right->number;
188 free(left); return right;
189 break;
190 case '-':
191 right->number = left->number - right->number;
192 free(left); return right;
193 break;
194 case '*':
195 right->number = right->number * left->number;
196 free(left); return right;
197 break;
198 case '/':
199 if(right->number==0) {
200 error("zero divide in compile time");
201 } else {
202 right->number = left->number / right->number;
203 }
204 free(left); return right;
205 break;
206 case '%':
207 if(right->number==0){
208 error("zero divide in compile time");
209 } else {
210 right->number = (int)left->number % (int)right->number;
211 }
212 free(left); return right;
213 break;
214 case '^':
215 right->number = pow(left->number,right->number);
216 free(left); return right;
217 }
218 }
～省略～
224 if(type == '-' && right->type == 'n'){
225 number = -right->number;
226 type = 'n';
227 }
・・・ここで演算の処理を行なっている．leftとrightのtypeが'n'つまりは数値であ り，自分自身のtypeが演算子であった時に行なわれる．
182行目のtypeが'$>$'であった時を説明すると，自分自身のtypeが'>'であった 時にleftのnumberとrightのnumberを比較し，真なら1を偽なら0をrightの numberに置き換え，不要となったleftのメモリを解放し，rightのnodeを次の nodeとして返す．といった処理を行なっている．省略しているがその他の演算 も同様にして行なっている．
224行からの処理はマイナスの規則をつけるための処理でtypeが'-'でrightの typeが'n'であった場合．例としては(-1+5)などの処理のために用いられる．
command関数
command関数では主にコマンドの実行処理を行なう部分である．四則演算を実 装するにあたっては変数の代入と変数の内容確認のためのコマンドの処理，ま た演算の結果の表示を行なっている．追記部分は次のようになっている．
command関数一部
～省略～
272 // コマンドを実行する。コマンドはtypeの値で判断される。
273 if(!d) return;
274 switch(d->type) {
275 case 'v': // typeが'v'であるときは、何も実行しない。
276 return;
277 case 'n': // 四則演算の結果を表示する。
278 printf("answer -> %.10g\n",d->number);
279 return;
280 case '=': // typeが'='の時に実行する。
281 if(d->left->value[0]=='$'||d->left->value[0]=='@'){
282 if(d->right->value != NULL && d->right->value[0] != '$'){
283 // 変数に代入する値である文字列が存在するときにハッシュテーブルに格納
284 insert(d->left->value,d->right->value,(int)d->number);
285 }else{
286 // 変数に代入される値が数字の時にハッシュテーブルに格納。
287 // その時、値は整数型なので文字型に直す。ハッシュテーブルは文字型。
288 sprintf(f,"%.10g",d->right->number);
289 insert(d->left->value,f,(int)d->number);
290 }
291 }
292 return;
～省略～d->typeでswitchさせて処理を行なう．'='の時の代入処理はleftが変数であり， rightに値がある場合に実行する．なお，この変数はhash表に保存されており， 文字列も格納できるためその判別も行なう．また，格納先はchar型で保存して いるため，数値もsprintf()を用いて文字列に変換し格納している．
実行結果
プログラムの実行例を以下に示す．
なお，わかりやすいように別々に表示しているが，それぞれは繋がっていると 考えてもらいたい．
上記の実行例は上から順に
なお，わかりやすいように別々に表示しているが，それぞれは繋がっていると 考えてもらいたい．
j04013 % ./my-shell [~/Documents/classes/junior/unix/myshell] % $a = 0.5 % ans $a $a[0]=0.5
% $a = $a+3*1.5 % ans $a $a[0]=5
% ($a+3)*0.5 answer -> 4
% $b = 2 % $a*$b answer -> 10
% $a = 0.0000000001 % $b = 0.0000000003 % $a+$b answer -> 4e-10
% $a = (1+2)^2+1 % $b = 1-2*3%2 % ans $a $a[0]=10 % ans $b $b[0]=1 % $a>$b answer -> 1
上記の実行例は上から順に
- 少数の変数代入．
- 変数を用いた演算結果を変数に代入．
- ()を用いた計算
- 2変数を使っての演算
- 小さい値の場合の指数表現
- すべての演算を使った場合
処理の流れ
全体的なプログラムの流れを構文規則の還元のされかたを中心に説明する．
例題として以下の数式がどのように処理されるかを示す．なお，$aにはあらか
じめ「3」という値が入っているものとする．
まず，与えられた文字列をtoken()関数内で区切り，数値は'n'として\$aは'v'と
して構文規則へ渡す．
渡されたトークンは規則によって'n'からnumへ，numからexpへと還元(reduce) されていく(図1)．その際に，new_node()関数を呼び出し，type='n'でnumber に「1」を格納したnodeとなっている．
図1
次に'+'のトークンを取り出すが，exp+に還元する規則がないため，次の トークンを呼び出す(図2)．
図2
次のトークンを呼び出すと'n'なので図1の作業を経てexpに還 元される．この時，exp+expという状態はexpへと還元が可能である．しかし， yaccではトークンを先読みしており，今回の場合は'*'が入ってくるので'*'の 処理を優先して(優先順位の定義より)shiftすることとなる(図3)．
図3
shiftを行なうと次のトークンは'('である．この状態も還元できないので shiftする．次は数値の「1」であるのでトークンは'n'であり，それはまた 初めの図1のように還元する(図4)．
図4
次の値は'-'でまた還元できないためにshift．次の値は「$a」であり，'v'か らvalへ，valからexpへと還元される．この時，下図のようにexp-expの状態ができ，これは expへと還元ができる．この際に，$aは展開され，「3」となり，「1-3」の演 算が行なわれ還元されるノードのnumberには-2が格納される．
図5
ここまできた状態でexp+exp*(expとなっており．ここに')'がshiftされること によって(exp)がexpに還元される．次にexp*expが同様にexpに，最後に exp+expとなり，expへと還元．これでトークンはすべてないため，topへと還 元される．これらが還元される際もnew\_node内でその都度，演算が行なわれ その結果を格納したnodeが返される．(図6)
図6
topはcommand関数を実行し，演算の解答を出力する．それが終了したら作成さ れた構文木を辿りメモリの解放を行ない，入力のプロンプトへと戻る．ちなみ に，メモリの解放は個々の演算が還元され，nodeを返す際，値をrightの nodeに蓄え，そのnodeを返し，leftのnodeは演算が終了するとfreeされるので 演算のみを行なう入力をした場合に完成する構文木は右にのみ子を持つもの となる．
例：1+2*(1-$a)
渡されたトークンは規則によって'n'からnumへ，numからexpへと還元(reduce) されていく(図1)．その際に，new_node()関数を呼び出し，type='n'でnumber に「1」を格納したnodeとなっている．
図1次に'+'のトークンを取り出すが，exp+に還元する規則がないため，次の トークンを呼び出す(図2)．
図2次のトークンを呼び出すと'n'なので図1の作業を経てexpに還 元される．この時，exp+expという状態はexpへと還元が可能である．しかし， yaccではトークンを先読みしており，今回の場合は'*'が入ってくるので'*'の 処理を優先して(優先順位の定義より)shiftすることとなる(図3)．
図3shiftを行なうと次のトークンは'('である．この状態も還元できないので shiftする．次は数値の「1」であるのでトークンは'n'であり，それはまた 初めの図1のように還元する(図4)．
図4次の値は'-'でまた還元できないためにshift．次の値は「$a」であり，'v'か らvalへ，valからexpへと還元される．この時，下図のようにexp-expの状態ができ，これは expへと還元ができる．この際に，$aは展開され，「3」となり，「1-3」の演 算が行なわれ還元されるノードのnumberには-2が格納される．
図5ここまできた状態でexp+exp*(expとなっており．ここに')'がshiftされること によって(exp)がexpに還元される．次にexp*expが同様にexpに，最後に exp+expとなり，expへと還元．これでトークンはすべてないため，topへと還 元される．これらが還元される際もnew\_node内でその都度，演算が行なわれ その結果を格納したnodeが返される．(図6)
図6
topはcommand関数を実行し，演算の解答を出力する．それが終了したら作成さ れた構文木を辿りメモリの解放を行ない，入力のプロンプトへと戻る．ちなみ に，メモリの解放は個々の演算が還元され，nodeを返す際，値をrightの nodeに蓄え，そのnodeを返し，leftのnodeは演算が終了するとfreeされるので 演算のみを行なう入力をした場合に完成する構文木は右にのみ子を持つもの となる．