Forthを作ってみる / 条件分岐を実装する

条件分岐を実装する

今まで作ったForthには、以下の機能が実装されている

• 値をスタックに積む
• 足し算する
• 表示する

条件分岐や繰り返し構造がない。せめてifくらいないとカッコつかない。 で、ifワードを実装する。ちなみにワードとはForthの機能単位だ。

文法は、こうなる。

4 5 <
if
    Trueの時の処理
else
    Falseの時の処理
then

ちょっと変わっている。 ifワードは直前の計算結果、つまりスタックトップの値を取り出し真偽を判定し、処理を分岐させる。 elseはなくても良い。

コード化されたプログラムはこんな並びにする。

ifコード, False処理開始位置(または、ifブロック脱出位置), Trueの時の処理... , elseコード, ifブロック脱出位置 , Falseの時の処理... , thenコード, 以降の処理(ifブロックの外),,, 

ifコードとelseコードの直後にジャンプ先を入れたのは、

• 実行時にelseの位置やthenの位置を探すのは効率悪い
• コード化されているelseコードとthenコードを構文解析しながら探すのは面倒だ

と考えたからである。

構文解析は、こんな感じでやっていこう。 まず、分岐スタック'if_stack'を用意する。これは、「未確定のジャンプ先を保存するプログラム位置」を保存するためのスタックである。 ややこしいが、要はFalse処理開始位置とifブロック脱出位置を一時保存するためのスタックである。

"if"を見つけたら、

• prog[現在位置]にifコードを埋める
• prog[現在位置 + 1](False処理開始位置の格納番地)の値はまだ決まっていないのでそのまま空けておく
• 「現在位置+1」を分岐スタックにpushする

書いてて分からなくなる。

"else"を見つけたら、

• prog[現在位置]にelseコードを埋め込む

• else位置が確定したので、分岐スタックからpopした場所(False処理開始位置の格納番地)に「現在位置 + 2」(False処理開始番地)を代入する
• prog[現在位置 + 1](ifブロック脱出位置の格納番地)の値はまだ決まっていないのでそのまま空けておく

「現在位置 + 1」を分岐スタックにpushする

"then"を見つけたら、

• prog[現在位置]にthenコードを埋め込む
• then位置が確定したので、分岐スタックからpopした場所(ifブロック脱出位置の格納番地)に「現在位置 + 1」(ifブロック脱出位置)を代入する

この例ではif - else - thenだが、else処理のないif - then形式も処理できる。 その場合は、ifコードの次にifブロック脱出位置が格納される。

また、ifがネストする場合は、分岐スタックに格納番地が積み上がっていき、その時点の最も内側のifコードの解析を行う。

コード

まず、分岐スタックだが、

char if_stack[10];              /* 分岐スタック */
int if_pos;                     /* 分岐スタックの位置ポインタ */

/* 分岐スタックに番地を積む */
void push_if_stack(char adrs)
{
    if_stack[if_pos] = adrs;
    if_pos--;
}


/* 分岐スタックから番地を取り出す */
char pop_if_stack(void)
{
    if_pos++;
    return if_stack[if_pos];
}

構文解析関数parse()に以下の処理を加えた。

       } else if (strcmp(token, "if") == 0) {
           prog[idx] = CODE_IF;
           push_if_stack(idx + 1);
           idx += 2;
       } else if (strcmp(token, "else") == 0) {
           prog[idx] = CODE_ELSE;
           prog[pop_if_stack()] = idx + 2;
           push_if_stack(idx + 1);
           idx += 2;
       } else if (strcmp(token, "then") == 0) {
           prog[idx] = CODE_THEN;
           prog[pop_if_stack()] = idx + 1;
           idx++;
       }

プログラム処理関数proc_prog()の追加処理。

       case CODE_IF:
           if (pop()) {
               prog_cnt += 2;
           } else {
               prog_cnt = prog[prog_cnt + 1];
           }
           break;
       case CODE_ELSE:
           prog_cnt = prog[prog_cnt + 1];
           break;
       case CODE_THEN:
           prog_cnt++;
           break;

testfile/test2を試してみる。

3
if
	4 5 + .
else
	1 2 + .
then

結果

$./a.out testfile/test2
9

test3はif - then形式、test4はifのネストとなっている。

ソースコード

戻る 前へ 次へ