計算機システム実験：システムプログラム
課題2についての補足説明

• シェル用構文解析器
• パイプラインの作り方

シェル用構文解析器

シェルを作成するためには，利用者が打ち込んだ行を，シェルの構文に従って解釈し，何を実行すれば良いのか調べる必要があります． それを構文解析と言います． この実験では構文解析部分をしっかり作ることが目的ではありませんので，構文解析しやすい構文を自分で決めて構いません． 例えば

% wc < data > result

秋C学期のプログラミング言語処理では，字句解析，構文解析を勉強しますので，その知識を使ってシェルの構文を構文解析するプログラムを作ってみるのも良いでしょう．

または，解析木を出力するようなプログラムを用意してありますので，シェルの構文解析の部分に，このプログラムを使用しても構いません． 以下は，用意してあるシェル用構文解析器の説明です．

プログラムは，次の場所にあります．

~syspro/shell/

cp -rp などでコピーして使ってください．必要な部分は，次のファイルです．

command.c

command構造体操作

command.h

command構造体データ構造

lexer.c

字句解析器

lexer.h

字句解析器データ構造

parser.c

構文解析器

parser.h

構文解析器データ構造

executer.c

プログラムの実行（画面に表示）

executer.h

そのインタフェース

mysh.c

シェルのmainプログラム

parse() が返した木構造を解析して実行（画面に表示）するものが，executer.c に含まれている関数です． このサンプルは，木構造の内容を画面に表示するようになっています．

次のような手順で，executer.c を書き換えていくとよいでしょう．

1. １行として簡単なもの（パイプも入出力の切り替えもなし）を与えたときに，どのような木構造になるか調べる． id がどうなるか，argc, argv がどうなるか，sinfile, soutfile, out_mode がどうなるかを調べる．
2. execute_single_command() でコマンドを実行する． fork()システムコールと execve() システムコール(またはexecv() や execvp() )を使って実行する． リターンバリューとして，PID を返す．
3. fork() した場合，親プロセス側は，親は，wait(0), wait3() などで子供が終了することを待たなければならない．どこで wait すべきかをよく考える． 必ずしも fork() をした関数やループで wait しなければならいことはない．
4. 標準入力の切り替え（<）を与えた時に command 構造体がどうなるかを調べる．
5. 標準入力を切り替えを実現する． open() システム・コールとdup() (または，dup2())システム・コール，close() システム・コールを用いる．
6. 標準出力の切り替え（>），標準エラーの切り替え（>&）について，標準入力の切り替えと同様のことを行う． out_mode にも注意する．
7. パイプ（|)が打ち込まれた時に command 構造体がどうなるかを調べる．
8. パイプ（|)を実現する．まず，pipe() システム・コールでパイプを作成し，fork() してから親子で左右の枝を分担して再起，または，ループする． fork() した後，パイプの不要な口を閉じることを忘れないようにする．
9. パイプラインでは，一番最後のコマンドだけを wait すればよい．

fork() のタイミングには注意してください． 内部コマンドの場合，fork() をしてはいけません． ただし，標準出力がパイプの場合，まずパイプを作成してからfork() する必要があります． fork() すべきかどうかを，木を先読みして調べる方法もあります．

配列と木構造の探索については，２年生の教科書を読み返して復習して下さい． 配列の場合には，「ループ」することが基本です．パイプラインは，再帰ではなくループを使った方が簡単に実現できるようになっています． 構造体の場合には，関数呼び出し（場合によっては再帰呼び出し）を使います． fork() する時には，２重に検索実行しないように気をつける必要があります．

ループの数は，１つとは限りません． ２つのループを使った方が簡単な場合もあります． ２つのループとは，２重ループではなくて，１つのループを２回やるものです．

    for( i=0 ; i < n; i++ )
    {
    }
    ...
    for( i=0 ; i < n; i++ )
    {
    }

パイプラインの作り方

課題2-1では，プロセスの親子関係を中心に調べなさい． これを調べるには，自分が作成するシェルの参考にするためです． 同じ方法を使ってもよいし，独自の方法を使ってもかまいません．

親子関係を調べるには，ps コマンドを使います． この時，意味はありませんが，ps コマンドには，X ウインドウ関係のプログラム（すぐには終了しない）を使うとよいようです．

% csh 
% emacs | ps -l 
% emacs | kterm | ps -l 
% sh 
$ emacs | ps -l
$ emacs | kterm | ps -l
$ 

% strace -f -o sh.log sh 
$ ls
$ ls | head
$ exit
% less sh.log 
% egrep 'fork|pie|dup|exec|close|exit|wait' sh.log | less 
% egrep 'fork|pie|dup|exec|exit|wait' sh.log | less 
% 

詳しくは，man strace を見てください．