課題内容-level2-

　Perl や tcsh の様に、$var などの構文を使用しても良いが、 C と同じように、int var などと宣言させる方法もある。
　変数の名前と値の組は、hash 関数を使ってテーブルに格納する。

仕様

　前にこの実験を担当した方々が作成したプログラムでは、変数名と値を単に hash に格納したもので、特定の内部コマンドを使用しないと、変数の参照が出来なかった。
　今回は実際のシェルにより近い動作をする環境変数、シェル変数の設定、および参照が可能にした。

環境変数、シェル変数の設定

環境変数の設定

my-shell% setenv {変数名} = {値}
              or
my-shell% setenv ${変数名} = {値}

シェル変数の設定

my-shell% {変数名} = {値}
           or
my-shell% ${変数名} = {値}

　変数名、値は、アルファベットと、アラビア数字、特定の記号 ( * + , - . / : ~ ) で構成できる。
　'=' の間にはスペース (' ') はあってもなくても機能する。
　環境変数で既に存在する変数名で、シェル変数を設定した場合は、環境変数を更新する。
　しかし、シェル変数で既に存在する変数名で環境変数を設定した場合は、そのまま環境変数を設定する。
　環境変数は、関数 setenv() を使用して保存する。
　シェル変数はハッシュを作成し、そこに格納する。
　尚、環境変数を my-shell で設定するときに setenv という内部コマンドで設定する。

環境変数、シェル変数の参照

設定されたシェル変数を参照するには、

my-shell% echo ${変数名}

のように、 echo を使用して展開された変数の値を見る事ができる。

実行例

% test = hoge
% echo $test
hoge

設定した環境変数は従来のシェルコマンド ( env など) でも参照できる。
環境変数、シェル変数を含めた全ての変数を表示するには、

my-shell% list

と、する。
list は my-shell の内部コマンドとし、環境変数は *environ[] から環境変数一覧を取得し、シェル変数はハッシュに登録されている全てのシェル変数を取得するようにする。

実行例

% test1 = hoge
% test2 = hoge
% setenv TEST = hoge
% list
TERM_PROGRAM=Apple_Terminal
TERM=xterm-color
SHELL=/bin/bash
   ～ 省略 ～
_=./my-shell
TEST=hoge

test1 = hoge
test2 = hoge

　追加補足： ${変数名} で変数が展開されるので、変数の値にシェルコマンドを代入して実行する事ができる。
　尚、環境変数と、シェル変数で、同じ名前の変数があった場合、環境変数が優先される。

実行例

% test = ps
% $test
  PID  TT  STAT      TIME COMMAND
 3620  p1  S      0:04.17 -bash
10906  p1  S+     0:00.04 ./my-shell
 1011  p2  S+     0:00.81 -bash
 5305  p3  S+     0:00.54 -bash
% setenv test = cal
% list
   ～ 省略 ～
_=./my-shell
test=cal

test = ps
% $test
    January 2007
 S  M Tu  W Th  F  S
    1  2  3  4  5  6
 7  8  9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31

環境変数、シェル変数の削除

　環境変数、シェル変数を削除する場合は、

my-shell% delete {{変数名} or ${変数名}}...

　変数名は、変数名を複数渡せば、一度に変数を削除可能。変数名が環境変数、シェル変数の二つとも存在するばあい、両方を削除する。

実行例

% test = hoge
% test1 = hoge
% setenv test = hoge
% list | grep hoge
test=hoge
test = hoge
test1 = hoge
% delete test test1
% list | grep hoge
%

実装

　上記のような仕様にするために行った実装を説明する。

キューの作成

　queue.cを作成し、キューを操作するための関数を一通り作成した。

キューの関数一覧

void que_push(char *value);    // キューに値を格納する
char *que_pop(void);           // キューの先頭の値を取り出す
char *que_front(void);         // キューの先頭の値を返す
char *que_back(void);          // キューの最後の値を返す
int que_size(void);            // キューに格納されている値の数を返す
int que_free(void);            // キューに格納できる値の数を返す
int que_empty(void);           // キューが空かどうか判定する
void que_clear(void);          // キューを空にする

　尚、キューは、 token() で判定された値を格納するのに使用。
　元のサンプルソースでは、 token() で判定された値は、 (char *)value といグローバル変数に格納されていた。　しかし、構文規則を追加するにあたって、グローバル変数のままでは判定された値がきちんと引き渡せない状況が生じた。
　例えばこのような場合である。

グローバル変数だと問題が生じる例

mesi : pan niku { $$ = ryouri($1,$2); }
     | kome ume { $$ = ryouri($1,$2); }
pan  : 'a' { $$ = value; }
kome : 'a' { $$ = value; }
niku : 'b' { $$ = value; }
ume  : 'c' { $$ = value; }

　このような規則を書いた場合、規則 mesi では 2 つある規則のどの規則が適応されたかを判定するためには、規則 pan と規則 kome が同じトークンをとるため、規則 niku か規則 ume のどちらの規則に適応するか調べる必要がある。
　そのため yylex() は 2 回続けて実行されて規則 mesi の 2 つある規則のどの規則かを判定する。そして、規則が確定した時点で、規則 pan 、規則 niku もしくは規則 kome 、規則 ume に対する処理が実行される。
　今回のシェルプログラムでは、 yylex() は token() を実行して、その返り値を返している。
　そうなると、規則 pan や規則 kome の value を代入するという処理を実行する前に、 token() が実行され、そのことにより value は上書きされ、本来入るはずの値が入らなくなる。
　この問題を回避するためにキューを実装し、 token() が 2 回続けて実行された場合も、値が上書きされないようにした。

ハッシュの作成

　hash.cを作成、ハッシュを操作するための関数を作成した。

ハッシュの関数と構造体一覧

typedef struct H_DATA {
  char *key;
  char *data;
  struct H_DATA *next;
}H_DATA;

typedef struct HASH {
    H_DATA *table[TABLE_SIZE];
} HASH;

HASH *make_hash_table();                      // ハッシュテーブルを生成する
void init(HASH *ht);                          // ハッシュテーブルを初期化する
int hash(char *key);                          // ハッシュを計算する
char *getValue(HASH *ht,char *key);           // キーに対応する値を返す
void get_all_print(HASH *ht);                 // 格納されている全ての値を返す
int insert(HASH *ht,char *key,char *data);    // キーと値を登録する
int delete(HASH *ht,char *key);               // キーと対応する値を削除する

　ハッシュテーブルを変数格納用と、内部コマンドで使用している予約語格納用に 2 つを使用するため、関数 make_hash_table() を作成し、異なるハッシュテーブルを作成出来るようにした。

ハッシュ・サンプルプログラム

int main(int argv, char *argc[])
{
    HASH *ht1;
    HASH *ht2;
    ht1 = make_hash_table();
    ht2 = make_hash_table();
    
    init(ht1);
    init(ht2);
    
    insert(ht1, "test1", "hoge1");
    insert(ht1, "test2", "hoge1");
    insert(ht2, "test1", "hogehoge1");
    insert(ht2, "test2", "hogehoge2");
    
    printf("getValue(ht1, \"test1\") => %s\n",getValue(ht1, "test1"));
    printf("getValue(ht2, \"test1\") => %s\n",getValue(ht2, "test1"));
    
    delete(ht1, "test1");
    
    printf("all_print (hash_table 'ht1')\n");
    get_all_print(ht1);
    printf("all_print (hash_table 'ht2')\n");
    get_all_print(ht2);
    
    return 0;
}

ハッシュ・サンプルプログラム実行結果

getValue(ht1, "test1") => hoge1
getValue(ht2, "test1") => hogehoge1
all_print (hash_table 'ht1')
test2 = hoge1
all_print (hash_table 'ht2')
test1 = hogehoge1
test2 = hogehoge2

　実行結果を見て分かる通り、同じキーでも、ハッシュテーブルが異なれば違う値を返し、また、ハッシュテーブルごとにキーの削除が出来ていることが確認できる。
　ハッシュテーブルの作成や、予約語の登録は関数 main() の中で行っている。

関数 main() の変更点

===============↓↓追加↓↓====================↓↓追加↓↓===============
#define COM_WORD_NUM 3
char *com_word[] = {"delete", "list", "setenv"};
char *com_word_num[] = {"1", "2", "3"};
extern char **environ;
HASH *word;
HASH *var;
===============↑↑追加↑↑====================↑↑追加↑↑===============

               ～ 省略 ～                        ～ 省略 ～

int main() 
{
    char buf[BUFSIZ];
===============↓↓追加↓↓====================↓↓追加↓↓===============
    int c;
    word = make_hash_table();
    var = make_hash_table();
    init(word);
    init(var);
    for(c=0;c

　予約語は配列 com_word[] の中に登録し、配列 com_word_num[] は各予約語のタイプを表す文字列を格納してある。
　関数 main() では予約語をキーとし、それに対するタイプを値とし、ハッシュテーブルに格納している。

関数 token() の変更

　変数識別用のトークンと、内部コマンド識別用のトークンを用意する必要があるため、その処理を追加した。
　まず、トークン 'f' を判定している条件式の中に、内部コマンドかどうかを判定する条件式を追加した。

token() 変更点 (内部コマンド判定)

    } else if(('a' <= c && c <= 'z') || ('A' <=c && c <= 'Z') ||
        ('*'<= c && c <= ':') || '~'== c){
        file = ptr - 1;
        while (('a' <= c && c <= 'z') || ('A' <=c && c <= 'Z') ||
            ('*' <= c && c <= ':') || '~' == c) c = *ptr++;
        ptr--;
        length = ptr - file;
        value = (char *)malloc(length+1);
        for(i=0;i

　入力された文字列が内部コマンド名と一致するならば、トークン 'w' を返す。
　文字列が内部コマンド名と一致するかどうかは、予約語が格納されているハッシュテーブルから文字列をキーとして検索を行い、値の有無で内部コマンドであるかを判定する。
　わざわざハッシュに内部コマンド名を予約語として登録して、そこから比較してるのは、単に一回の処理で判定できるからである。
　別の実装方法として関数 strcmp() を使用して入力された文字列と全ての内部コマンド名を比較し、一致する場合に内部コマンドと判定する方法があるが、それでは内部コマンドを後々増やす事も想定すると、非常に無駄が多くなってしまう。
　また、予約語でない文字列の方が圧倒的に多いことも考慮すると関数 strcmp() で毎回比較する無駄は避けたい。

構文解析の変更

新たに変数を識別するための構文規則と、内部コマンドを識別するための構文規則を追加した。

構文解析 expr 変更点

     | expr '>' file     { $$ = make_file($1, $3->value,0); }
     | expr '<' file     { $$ = make_file($1, $3->value,1); }
     | expr '>' '>' file { $$ = make_file($1, $4->value,2); }
===============↓↓追加↓↓====================↓↓追加↓↓===============
     | com               { $$ = new_node($1->type,make_args($1,NULL,0),NULL,NULL); }
     | com args          { $$ = new_node($1->type,make_args($1,$2,arg_count),
                                                                   NULL,NULL); }
     | com file '=' file { $$ = new_node($1->type,NULL,$1,
                                                    new_node('=',NULL,$2,$4)); }
     | file '=' file     { $$ = new_node('=',NULL,$1,$3); }
===============↑↑追加↑↑====================↑↑追加↑↑===============
     | file              { $$ = new_node('c',make_args($1,NULL,0),NULL,NULL); }
     | file              { arg_count=0; }
       args              { $$ = new_node('c',make_args($1,$3,arg_count),
                                                                   NULL,NULL); }
     | '(' expr ')'      { $$ = $2; }
     ;

　構文規則 com は内部コマンドである事を示す。内部コマンドが単体で実行される場合 ( com ) と、引数をとる場合 ( com args ) 、環境変数を設定する内部コマンド用に 3 つの規則を追加した。更に変数設定用に ( file '=' file ) を追加。

構文解析 file 変更点

file : 'f'      { $$ = new_node('f',que_pop(),NULL,NULL); }
===============↓↓追加↓↓====================↓↓追加↓↓===============
     | 'v'      { $$ = new_node('v',que_pop(),NULL,NULL); }
     ;
===============↑↑追加↑↑====================↑↑追加↑↑===============

　構文規則 file には、変数を表すトークン 'v' を追加。変数は構文解析で作成されたコマンドが実行される直前で展開されるので、構文規則 expr 内で使用されている規則 file を使用した規則も問題なく実行可能である。

構文解析 arg 変更点

arg  : 'f' { $$ = new_node('f',que_pop(),NULL,NULL); }
===============↓↓追加↓↓====================↓↓追加↓↓===============
     | 'v' { $$ = new_node('v',que_pop(),NULL,NULL); }
     | 'w' { $$ = new_node('f',que_pop(),NULL,NULL); }
     ;
===============↑↑追加↑↑====================↑↑追加↑↑===============

　構文規則 arg には、変数を表すトークン 'v' と内部コマンドを表すトークン 'w' を追加。ここで内部コマンドを表す 'w' を追加しているのは、内部コマンドして登録されている文字列も引数として渡せるようにするためである。

構文解析 com 追加

com  : 'w' { $$ = new_node(atoi(getValue(word, que_front())),que_pop(),
                                                                   NULL,NULL); }
     ;

　構文規則 com は内部コマンドであることを示している。ここでの処理は予約語が保存されているハッシュテーブルから予約語のタイプを示す値を引き出し、内部コマンド名をノードの value として new_node() をで新しいノードを作成している。

関数 make_argv() の変更

　変数にも対応する用に以下のように変更を加えた。

構文解析 com 追加

int make_argv(char **com, node *arguments, int i)
{
    while(arguments) {
        if(arguments->type == 'f' && arguments->value){                // 変更前
                    ↓↓変更↓↓
        if((arguments->type == 'f' || arguments->type == 'v')
                                              && arguments->value){    // 変更後

関数 expand_var() の作成

　構造解析で作成されたコマンドが実行される前に、この関数で変数の展開を行う。
　変数は文字列の頭に '$' がある事によって変数となる。
文字列の頭が '$' であるかどうかを変数かどうかを識別し、変数であった場合は '$' 以下の文字列をキーとし、変数格納用ハッシュテーブルから値を参照する。　そして変数名と値を入れ替える作業を行う。このとき、ハッシュに値がない場合はその部分は削られる。

関数 expand_var() の作成

int expand_var(char **com)
{
    int i=0, c=0;
    char **com2;
    
    com2 = (char **)calloc((i + 1), sizeof(char *));
    for(i=0;com[i]!=NULL;i++) {
        if ((char)*com[i] == '$') {
            if (getenv(com[i]+1) != NULL) {
                com2[c] = getenv(com[i]+1);
                c++;
            }
            else if (getValue(var, com[i]+1) != NULL) {
                com2[c] = getValue(var,com[i]+1);
                c++;
            }
        }
        else {
            com2[c] = com[i];
            c++;
        }
    }
    com2[c] = NULL;
    for(i=0;com2[i]!=NULL;i++) com[i] = com2[i];
    com[i] = NULL;
    return i;
}/pre>

　この関数は関数 command() 中の関数 execute() が実行される直前に置いてある。

関数 command() の変更

　新たに、変数登録処理と、変数削除処理 ( 内部コマンド delete ) 、変数一覧取得処理 ( 内部コマンド list ) 、環境変数設定処理 ( 内部コマンド setenv ) の 4 つの処理を追加した。

変数登録処理

      case '=':
        if (d->left->type =='v') var_key = d->left->value + 1;
        else var_key = d->left->value;
        if (getenv(d->left->value) != NULL || d->value != NULL) {
            if (d->right->type == 'v') {
                setenv(var_key, getValue(var, d->right->value + 1), 1);
                if(SHELL_DEBUG) printf("setenv : %s\n", getenv(d->left->value));
            }
            else {
                setenv(var_key, d->right->value, 1);
                if(SHELL_DEBUG) printf("setenv : %s\n", getenv(d->left->value));
            }
        }
        else {
            if (d->right->type == 'v') {
                insert(var, var_key, getValue(var, d->right->value + 1));
                if(SHELL_DEBUG) printf("insert : %s\n", 
                                                 getValue(var, d->left->value));
            }
            else {
                insert(var, var_key, d->right->value);
                if(SHELL_DEBUG) printf("insert : %s\n", 
                                                 getValue(var, d->left->value));
            }
        }
        return;

my-shell% {変数名} = {値}
           or
my-shell% ${変数名} = {値}

　上記の記述で、変数を設定できる。
ここでの左辺がキーになるわけだが、 '$' が先頭に付加している場合がある、この場合 '$' 以下の文字列をキーとする処理を加える。
　また、環境変数で既にキーが設定されている、もしくは d->value に値が入っている場合(内部コマンド setenv から実行された場合)は、環境変数を設定する。
　そうでない場合はシェル変数を設定する。また、右辺の値が変数である場合は変数の展開を行う。

変数削除処理 ( 内部コマンド delete )

      case 1:
        if ((del_var = (char **)d->value)) {
            for (i=1;del_var[i] != NULL;i++) {
                if (*del_var[i] == '$') {
                    delete(var, del_var[i]+1);
                    unsetenv(del_var[i]+1);
                }
                else {
                    delete(var, del_var[i]);
                    unsetenv(del_var[i]);
                }
            }
        }
        return;

　与えられた引数をキーとし、環境変数、シェル変数の両方を削除する。この場合も '$' が先頭にある場合は、 '$' 以下の文字列をキーとする。

変数一覧取得処理 ( 内部コマンド list )

      case 2:
        for (i=0;environ[i] != NULL;i++)
            printf("%s\n",environ[i]);
        printf("\n");
        get_all_print(var);
        return;

　配列 *environ[] に環境変数の値が格納されているので、配列 *environ[] の全ての要素を出力し、関数 get_all_print() で全てのシェル変数を出力している。

環境変数設定処理 ( 内部コマンド setenv )

      case 3:
        if (d->value == NULL && d->right->type == '=') {
            d->right->value = (char *)malloc(sizeof(char)*7);
            strcpy(d->right->value,"setenv");
            command(d->right);
        }
        return;

　環境変数を設定するようにするために d->right->value に値を代入して、変数登録処理を実行する。 <>

課題内容
仕様
実装

<-previous problem　　　 go to top　　　 next problem->　　　