プログラミング言語処理

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

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

組み込みの四則演算子による整数の計算
変数が使える。変数の代入と参照。
関数定義と関数呼び出し、関数の実行の一部
配列

プログラミング言語として、これ以外に必要な機能は何であろうか。ＣやJavaなど、近代的なプログラミング言語にはいろいろな機能がある。

while文やfor文、switch文などの豊富な制御構文
局所変数とブロック（複文）
関数の途中から関数の値を返すreturn文
豊富なデータ型と構造体
ポインター

このほかにもいろいろあるが、tiny Cに加える機能は以下の通りである。

if文
局所変数とブロック文
関数の値を返すreturn文
while文 (とfor文)

なお、goto文はない。繰り返しはwhileやfor文で行う。

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

interp.h : インタプリタのheader
interp.c : インタプリタの関数、文の処理
interp_main.c : インタプリタのmain

文の実行

前回説明した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); } }

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);
    }
}

ASTがNULLの場合はなにもしない。
文に関しては、それぞれの文の処理をする関数を呼び出す。
もしも、式も文の一つなので、文でなければ式を実行するために、 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; }

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文に現れた局所変数について、現在の環境に登録しておく。パラメータの場合には引数と結合しておいたが、局所変数に関しては何の値でもかまわない（つまり、未定義）。上の関数では以下のことを行う。

現在の環境を示すenvpをenvp_saveに保存しておく。
局所変数のリストから、局所変数のシンボルを取り出す。
環境に登録する。Env[envp++] = 局所変数のシンボル
これを、局所変数の全部に繰り返す。
このあとで、リスト中の文を実行する。この間で、変数が参照される場合には、関数getValue/setValueで、値を参照するためにEnvにある変数の値が参照されることになる。
　式が全部実行しおわったら、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引数に０以外の値を与える。

この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"); / もしも、飛べなければエラー */ }

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; }

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; }

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