インタプリタ(1) 関数と文

前回、インタープリタの主に式に関連する部分を説明した。 今回は、文の処理を加え、本格的なプログラムが書けるように拡張してみよう。 前回は、以下の機能をつくった。

プログラミング言語として、これ以外に必要な機能は何であろうか。C やJavaなど、近代的なプログラミング言語にはいろいろな機能がある。 このほかにもいろいろあるが、tiny Cに加える機能は以下の通りである。 なお、goto文はない。繰り返しはwhileやfor文で行う。

説明するプログラムは、以下にある。

文の実行

前回説明したexecuteCallFuncの中で、本体の実行するために executeStatementを呼び出している。executeStatementは、文のASTのopを見 て、それぞれの処理の関数を呼び出す。
interp.c
void executeStatement(AST *p)
{
    if(p == NULL) return;
    switch(p->op){
    case BLOCK_STATEMENT:
	executeBlock(p->left,p->right);
	break;
    case RETURN_STATEMENT:
	executeReturn(p->left);
	break;
    case IF_STATEMENT:
	executeIf(p->left,getNth(p->right,0),getNth(p->right,1));
	break;
    case WHILE_STATEMENT:
	executeWhile(p->left,p->right);
	break;
    case FOR_STATEMENT:
	executeFor(getNth(p->left,0),getNth(p->left,1),getNth(p->left,2),
		   p->right);
	break;
    default:
	executeExpr(p);
    }
}
  1. ASTがNULLの場合はなにもしない。
  2. 文に関しては、それぞれの文の処理をする関数を呼び出す。
  3. もしも、式も文の一つなので、文でなければ式を実行するために、 executeExprを呼び出す。

IF文の実行

まず、文の処理でも最も簡単なif文の処理から説明をしよう。 if文のASTは、左に条件式、右に条件が成立した時に実行される文(then部)の ASTと条件式が成立しなかった時に実行される式(else部)のリストが入ってい る。これを、取り出して、if文を実行するexecuteIfを呼び出す。

    case IF_STATEMENT:
	executeIf(p->left,getNth(p->right,0),getNth(p->right,1));
	break;
executeIfは以下のようになる。
interp.c
void executeIf(AST *cond, AST *then_part, AST *else_part)
{
    if(executeExpr(cond))
	executeStatement(then_part);
    else 
	executeStatement(else_part);
}
まず、executeExprで条件式を実行し、その結果によって、then部かelse部の 式をexecuteStatementを呼び出して実行する。

複文と局所変数

関数の本体は、複文である。複文を実行するexecuteBlockは関数が呼び出され ると最初に実行されることになる。ブロック文のASTは、左に局所変数のリス ト、右に実行するべき文のASTのリストが入っている。これらをとりだして、 executeBlockを呼び出す。
    case BLOCK_STATEMENT:
	executeBlock(p->left,p->right);
	break;
文を実行している間に局所変数が現れた場合には、ブロック文で宣言された局 所変数を参照しなくてはならない。 しかし、このブロック文が終わった時には、元の値に戻さなくてはならない。 つまり、有効範囲(スコープ)を持つことになる。 なお、局所変数として宣言されていない変数は、 大域変数として、シンボルテーブルの中のシンボルのvalの値が参照される。

excuteBlockでは、局所変数をつくり、リストの中の文を順番に実行する。

interp.c
void executeBlock(AST *local_vars,AST *statements)
{
    AST *vars;
    int envp_save;

    envp_save = envp;
    for(vars = local_vars; vars != NULL; vars = getNext(vars))
	Env[envp++].var = getSymbol(getFirst(vars));
    for( ; statements != NULL; statements = getNext(statements))
	executeStatement(getFirst(statements));
    envp = envp_save;
    return;
}
局所変数に対する処理は基本的には関数のパラメータ変数に対する式と同じで ある。block文に現れた局所変数について、現在の環境に登録しておく。 パラメータの場合には引数と結合しておいたが、局所変数に関しては何の値でもか まわない(つまり、未定義)。上の関数では以下のことを行う。
  1. 現在の環境を示すenvpをenvp_saveに保存しておく。
  2. 局所変数のリストから、局所変数のシンボルを取り出す。
  3. 環境に登録する。Env[envp++] = 局所変数のシンボル
  4. これを、局所変数の全部に繰り返す。
  5. このあとで、リスト中の文を実行する。この間で、変数が参照される場 合には、関数getValue/setValueで、値を参照するためにEnvにある変数の値が 参照されることになる。
  6.  式が全部実行しおわったら、envpにenv_savepを代入して、環境を呼び 出し前に戻しておく。これによって、局所変数は取り消されることになる。

return文:setjmp/longjumpの使い方

return文は、関数の実行を終了し、関数の戻り値を返す文である。 return文のASTは、左に戻り値の式が入っている。これをとりだして、 executeReturnを呼び出す。

    case RETURN_STATEMENT:
	executeReturn(p->left);
	break;
インタープリターでは関数本体を実行する時に、executeStatementで再帰的に 呼び出しを行って実行をしている。例えば、executeStatementで、IF文を実行 する場合にはexecuteIfを呼び出し、その中でthen部やelse部を実行するのに executeStatementを呼び出している。さらに、then部が複文の場合には、 executeBlockが呼び出され、中の文を実行するためにexecuteStatementを呼び 出し、実行が進んでいく。その途中で、return文が実行されたときには、最初 のexecuteCallFuncのところに戻ってこなくてはならない。

この動作を行うためにsetjmp/longjmpを使わなくてはならない。 setjmp/longjmpは関数の現在の状態を記録しておき、呼び出された先から戻る 機能である。例えば、

#iclude <setjmp.h>
jmp_buf env;

foo() 
{   ...  
    setjmp(env); 
    ... 
    goo1(); 
    ...
}

goo1() 
{ 
   ... 
   goo2(); 
    ...
}

goo2() 
{  
   ... 
   longjmp(env,1);  
}
この例では、fooのsetjmpでenvに状態を覚えておき、goo1, goo2と呼び出され たときに、goo2でlongjmpをすることよって、setjmpの後に戻ってくる。 setjmpでは、はじめにセットしたときに0を、longjmpで戻ってきたときには longjmpで指定された値を返す。したがって、longjmpでは第2引数に0以外の 値を与える。

このsetjmp/longjmpの機能を使ってreturn文をつくる。まず、戻るべき最も最 近の状態jmp_bufを覚えておくために、変数funcReturnEnvを使う。 funcReturnValはreturn文から返される値を格納する変数である。

jmp_buf *funcReturnEnv;
int funcReturnVal;
return文が実行されると実行中の関数を実行しているexecCallFuncにもどらな くてはならない。execCallFuncの中では、executeStatmentを実行する時に以 下のプログラムようにsetjmpを実行し、return文が実行された時に戻る準備を しておく。
  ...
  ret_env_save = funcReturnEnv; /* 元の値をとっておく */
    funcReturnEnv = &ret_env;      /* 今度戻ってくるところにセット */
    if(setjmp(ret_env) != 0){      /* longjmp で戻ってきたとき */
	val = funcReturnVal;       /* returnからの値をとる */
    } else {               /* はじめにセットしたとき,本体を評価 */
	val = evalObject(getNth(func_def,1)); /*なにもなければその値*/
    }
    funcReturnEnv = ret_env_save; /* 前の値に戻す*/
    ...
return文を実行するexecuteReturnでは、返す値をfuncReturnValにいれて、 funcReturnEnvでしめされている場所にもどればよい。
interp.c
void executeReturn(AST *expr)
{
    funcReturnVal = executeExpr(expr); /* 戻り値の式を実行 */
    longjmp(*funcReturnEnv,1);   /* 最近のsetjmpにかえる !!! */
    error("longjmp failed!\n");  /* もしも、飛べなければエラー */
}
以下が、上のsetjmpを組み込んだexecCallFuncである。
interp.c
int executeCallFunc(Symbol *f,AST *args)
{
    int nargs;
    int val;
    AST *params;
    jmp_buf ret_env;
    jmp_buf *ret_env_save;
    
    nargs = 0;
    for(params = f->func_params; params != NULL; 
	params = getNext(params)){
	Env[envp+nargs].var = getSymbol(getFirst(params));
	Env[envp+nargs].val = executeExpr(getNth(args,nargs));
	nargs++;
    }
    ret_env_save = funcReturnEnv;
    funcReturnEnv = &ret_env;
    envp += nargs;
    if(setjmp(ret_env) != 0){
	val = funcReturnVal;
    } else {
	executeStatement(f->func_body);
    }
    envp -= nargs;
    funcReturnEnv = ret_env_save;
    return val;
}
return文が実行されてsetjmpのところにもどってきた時にもenvpが元にもどさ れていることに注意。

while文:制御文

制御文であるwhile文のASTは、左の条件式、右に条件が成立している間実行さ れる文が入っている。これを取り出して、executeWhileを実行する。

    case WHILE_STATEMENT:
	executeWhile(p->left,p->right);
	break;
executeWhileでは、executeExprで条件式を実行し、これが真、すなわち0でな い間、本体の文を実行すればよい。
interp.c
void executeWhile(AST *cond,AST *body)
{
    while(executeExpr(cond))
	executeStatement(body);
}

このほかにも、for文などの制御構造も、シンタックスを決め、その意味にし たがってどの部分を実行するかを制御すれば実装することができる。 (for文については、わざとぬいてあるので、作ってみること)

インタプリタのmainプログラム

最後に、インタプリタのmainプログラムを作る。mainでは、まず、構文解析ルー チンであるyyparseを呼び出す。yyparseはEOFが入力されるまで、構文解析を 行い、外部定義に対して、defineFunctionやdeclareVariableを呼び出す。 その後で、executeCallFuncを使ってmainプログラムを呼び出す。

interp_main.c
int main()
{
    int r;
    yyparse();
    r = executeCallFunc(lookupSymbol("main"),NULL);
    return r;
}

なお、インタプリタのコンパイルの方法については、 こちら を参照のこと。