課題内容-level6-
if文や，while文を付け加えて，実装せよ．
簡単なベンチマーク(階乗数列の計算など)を作り，動作時間を測定せよ．時間の測定には、timeコマンドを使うことが出来る。
リダイレクトやパイプは，if文やwhile 文でも，ちゃんと動作しているだろうか?
tcsh や Perl などと実行時間を比較し，考察せよ。
簡単なベンチマーク(階乗数列の計算など)を作り，動作時間を測定せよ．時間の測定には、timeコマンドを使うことが出来る。
リダイレクトやパイプは，if文やwhile 文でも，ちゃんと動作しているだろうか?
tcsh や Perl などと実行時間を比較し，考察せよ。
if文の実装
プログラムの説明
if ( $a > 5 ) then { $a = 20 } else { $a = 0 }上のような文を実行できるように，shell.yを以下のように実装した．
まず，字句解析の関数tokenを以下に示す．
関数token() (shell.y)
// token()によりtokenを作成する。
int
token()
{
～省略～
switch(getID(value)){
～省略～
case 6: // value == "if"
last_token = IF;
break;
case 7: // value == "then"
last_token = THEN;
break;
case 8: // value == "else"
last_token = ELSE;
break;
～省略～
}
～省略～
}"if"，"then"，"else"の文字列を読み取れば，各々のトークンを返すようにした．
getID()は，ハッシュ表に登録しておいた予約語と引数が一致すると，対応した値を返すものである．
次に，if文の構文規則を以下に示す．
if文の構文規則 (shell.y)
～省略～
%token IF ELSE WHILE THEN STMT
～省略～
%%
～省略～
if_part : IF '(' exp ')' THEN if_stmt { $$ = new_node(IF,NULL,0,$3,$6); }
;
if_stmt : stmt opt_else { $$ = new_node(THEN,NULL,0,$1,$2); }
;
opt_else : { $$ = NULL; } //空規則
| ELSE stmt { $$ = new_node(ELSE,NULL,0,$2,NULL); }
;
～省略～
stmt : '{' expr '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' exp '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' if_part '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' wh_part '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
;
～省略～
exp : num { $$ = $1; }
| '-' num { $$ = new_node('-',NULL,0,NULL,$2); }
| val { $$ = $1; }
| cmd val { $$ = new_node('i',$1->value,0,NULL,$2); }
| exp '>' exp { $$ = new_node('>',NULL,0,$1,$3); }
| val '=' exp { $$ = new_node('=',NULL,0,$1,$3); }
//四則演算の規則
| exp '+' exp { $$ = new_node('+',NULL,0,$1,$3); }
| exp '-' exp { $$ = new_node('-',NULL,0,$1,$3); }
| exp '*' exp { $$ = new_node('*',NULL,0,$1,$3); }
| exp '/' exp { $$ = new_node('/',NULL,0,$1,$3); }
| exp '%' exp { $$ = new_node('%',NULL,0,$1,$3); }
| exp '^' exp { $$ = new_node('^',NULL,0,$1,$3); }
| '(' exp ')' { $$ = $2;}
;
～省略～
%%
C言語のif文とほとんど同じような構文になっている．
stmtの構文規則により，if文の入れ子も出来るようにしている．また，opt_else の構文規則は，else文が省略できるという意味を持っている．
exprは，Level1と同じ構文規則なので，省略する．
expは四則演算の構文規則である．ifの条件文ではexpの構文規則にある「>」しか比較演算子は使えないので注意する．
例文(1)の構文木(図1)で実行過程を説明する．
まず，if_part(図1のIF)が還元され，command関数が呼び出される．
関数command() (shell.y)
void
command(d)
node *d;
{
～省略～
switch(d->type){
～省略～
case IF:
command(d->left);
tmp_ifexp = d->left->number;
command(d->right);
return;
case THEN:
if(tmp_ifexp){
command(d->left);
}else{
command(d->right);
}
tmp_ifexp = 0;
return;
～省略～
}
～省略～
}図1参照
そのとき，d->typeが「IF」なので，「case IF」が実行される．command(left)で条件文「$a > 5」が評価される．command(right)で「if_stmt」が実行される．
「if_stmt」はtypeが「THEN」なので，「case THEN」が実行される．「case THEN」では，条件文が真なら「stmt」，偽なら「opt_else」を実行する．
関数command() (shell.y)
void
command(d)
node *d;
{
～省略～
switch(d->type){
～省略～
// else に続くstmtの実行
case ELSE:
command(d->left);
tmp_ifexp = 0;
return;
// stmt(非終端文字)の実行
case STMT:
command(d->left);
return;
～省略～
}
～省略～
}図1参照
「stmt」を実行すると，「case STMT」を通って，「$a = 20」が実行される．
「opt_else」を実行すると，「case ELSE」，「case STMT」を通って，「$a = 0」が実行される．
以下に例文(1)の実行結果を示す．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 10 if ( $a > 5 ) then { $a = 20 } else { $a = 0 } ans $a $a=20 $a = 1 if ( $a > 5 ) then { $a = 20 } else { $a = 0 } ans $a $a=0 exit
変数の値を確認するには，ansコマンドを用いる．
$aに10を代入すると，ちゃんと条件文を評価して「$a = 20」が実行されたことがわかる(ansコマンドの下の表示は，変数の値の表示であり，変数に値を代入している訳ではない)．$aに1を代入して，同じ例文を入力すると，ちゃんと「$a = 0」が行われているのが確認できる．
リダイレクト・パイプの動作確認
リダイレクトが動いているか確認する．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 10 if ( $a > 5 ) then { ls > a.txt } else { ps > a.txt } exit [nw0409:unixlab2/level6/hash] j04009% less a.txt a.txt cp.shell.y hash.c hash.h hash.o loop loop.c makefile my-shell re ～省略～
a.txtに書き込まれたのは，lsコマンドの内容である．よって，if文でリダイレクトが 実行できることが確認できた．
次にパイプが実行できるか確認する．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 10 if ( $a > 20 ) then { ls } else { cat a.txt | wc } 22 22 159 exit [nw0409:unixlab2/level6/hash] j04009%
cat a.txt | wc の実行結果が表示されている．よって，if文でパイプが実行できることが確認できた．
動作時間の比較
今回作った shell.y と tcsh の動作時間の比較するため，以下のファイルを用意した．
test2 (shell.y用)
$a = 2
if ( $a > 1 ) then { $a = 0 } else { $a = 2 }test2.sh (tcsh用)
#!/bin/tcsh -f
@ a = 2
if ( $a > 1 ) then
@ a = 0
else
@ a = 2
endif2つともif文が100個記述されている．以下がtimeコマンドの実行結果である．
| ユーザー時間 | システム時間 | 経過時間 | |
| shell.y | 0.007 | 0.007 | 0.02 |
| tcsh | 0.031 | 0.030 | 0.08 |
ユーザー時間はシステムコール以外の処理にかかる時間，システム時間は，システムコール や入出力にかかる時間を表す．時間はすべて秒単位である．
表1では，ユーザー時間，システム時間は，共にshell.yが速い．これは，shell.yの演算がtcshの演算(組み込みコマンド)より速いことを示している．また，この例では，shell.yはほとんどシステムコールを使わないので，システム時間も短くなっている．
次に，if文で処理する命令をリダイレクトにしてみると，以下の結果になった．
| ユーザー時間 | システム時間 | 経過時間 | |
| shell.y | 0.021 | 0.106 | 0.16 |
| tcsh | 0.026 | 0.084 | 0.17 |
リダイレクトは10回行った．今度はshell.yのシステム時間が時間がかかっている．これは，リダイレクトの際にshell.yがシステムコールのopenやclose，fork等を使用しているためだと考えられる．
while文の実装
プログラムの説明
while ( $a > 5 ) { $a = $a - 1 }上のような文を実行できるように，shell.yを以下のように実装した．
まず，字句解析関数tokenを以下に示す．
"while"の文字列を読み取れば，トークンWHILEを返すようにしている．
関数token() (shell.y)
int
token()
{
～省略～
switch(getID(value)){
～省略～
case 6: // value == "while"
last_token = WHILE;
break;
～省略～
}
～省略～
}次に，while文の構文規則を以下に示す．
while文の構文規則(shell.y)
%%
～省略～
wh_part : WHILE '(' exp ')' stmt { $$ = new_node(WHILE,NULL,0,$3,$5);}
;
stmt : '{' expr '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' exp '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' if_part '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
| '{' wh_part '}' { $$ = new_node(STMT,NULL,0,$2,NULL); }
;
～省略～
%%while文の構文規則もif文同様にC言語の構文とほぼ変わらない．比較演算子も「>」しか使えない．また，C言語でいうbreak文やcontinue文の機能は無い．exp，exprはif文の構文規則で説明しているので，省略する．
例文(2)の構文木(図2)で実行過程を説明する．
まず，wh_part(図1のWHILE)が還元され，command関数が呼び出される．
関数command() (shell.y)
void
command(d)
node *d;
{
～省略～
switch(d->type){
～省略～
case WHILE:
command(d->left); // exp の実行
while( (tmp_whexp = d->left->number) ){
command(d->right); // stmt の実行
command(d->left); // exp の実行
//リダイレクションがwhileで実行されるときに実行される
if(d->left->number && tmp_exe != NULL && flg_rd >= 0 ){
make_file(tmp_exe,tmp_file,flg_rd);
printf("open\n");
}
～省略～
return;
}
～省略～
}
～省略～
}図2参照
還元されたとき，d->typeが「WHILE」なので，「case WHILE」が実行される．そして，command(d->left)が実行され，条件文exp「$a > 5」が評価される．もし条件文が真なら，command(d->right)を実行し，「case STMT」を通って，exp「$a = $a - 1」が実行される．
再びcommand(d->left)で条件文を評価し，条件文が偽になるまで「stmt」の実行を繰り返す．
以下に例文(2)の実行結果を示す．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 10 while ( $a > 5 ) { $a = $a - 1 } ans $a $a=5 $a = 1 while ( $a > 5 ) { $a = $a - 1 } ans $a $a=1 exit
変数の値を確認するには，ansコマンドを用いる．
$aに10を代入すると，ちゃんと条件文が偽($aが5)になるまで，「$a = $a - 1」が実行されたことがわかる(ansコマンドの下の表示は，変数の値の表示であり，変数に値を代入している訳ではない)．$aに1を代入して，同じ例文を入力すると，条件文が偽なので，「$a = $a - 1」 が一度も実行されず変数$aは1のままであることが確認できる．
リダイレクト・パイプの動作確認
リダイレクトが動くか確認する．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 5 while ( $a > 0 ) { $a = $a - 1; ls>a.txt } open open open open exit [nw0409:unixlab2/level6/hash] j04009% less a.txt a.txt cp.shell.y hash.c hash.h hash.o ～省略～
a.txtにlsの内容が出力されている．また，a.txtのノードの作成時に開かれることも合わせて，5回開いている(ノードの作成時にはopenを出力していない)こともわかる．これで，リダイレクトがwhile文で実行できることが確認できた．
次にパイプが実行できるか確認する．
[nw0409:unixlab2/level6/hash] j04009% ./my-shell $a = 5 while ( $a > 0 ) { $a = $a - 1; cat a.txt | wc } 34 34 264 34 34 264 34 34 264 34 34 264 34 34 264 exit [nw0409:unixlab2/level6/hash] j04009% cat a.txt | wc 34 34 264
tcsh上でやったwcコマンドの結果が，./my-shellで5回表示されている．つまりコマンドが5回実行されたということである．これで，パイプがwhile文で実行できることが確認できた．
動作時間の比較
shell.yとtcsh，Perlで動作時間の比較を行うため，以下のファイルを用意した．
test (shell.y用)
$a = 0
while ( 10000 > $a ) { $a = $a + 1 }test.sh (tcsh用)
#!/bin/tcsh -f
@ a = 0
while ( 10000 > $a )
@ a = $a + 1
endtest.pl (Perl用)
#!/usr/bin/perl
$a = 0;
while ( 10000 > $a){
$a = $a + 1;
}1万回の加算を行う．以下が実行結果(表3)である．
時間はすべて秒単位である．
| ユーザー時間 | システム時間 | 経過時間 | |
| shell.y | 0.059 | 0.007 | 0.07 |
| tcsh | 2.085 | 1.258 | 3.52 |
| Perl | 0.018 | 0.005 | 0.03 |
tcshは，演算回数が増えるとかなり時間がかかるようになった．shell.yもtcshほどではないが時間がかかるようになった．システム時間はshell.yはほとんどシステムコールを使わないので，演算回数では変わらなかった．Perlは，演算回数が増えても，ほかの2つと比べて緩やかに実行時間が増加した．
tcshは，組み込みコマンドを使っているので，それの呼び出し等に時間がかかったと考えられる．
Perlが，shell.yに比べて演算回数で実行時間があまり増加しないのは，Perlが中間コードを作成してから実行されているためだと考えられる．そうすることで，繰り返しの処理が速くなっていると考えられる．また，shell.yは再帰を多く使っている．再帰で計算するより繰り返しで計算するほうが速いので，その差も出ていると思われる．