シンプルな再帰下降のサンプル（３）変数と代入

変数と代入

a-zの変数と、代入=に対応。それから式の区切りを ',' にしました。

まず a=a という式について考えてみましょう。
左側のaは参照、右側は値です。

代入処理をするなら、代入したい変数にアクセスするための情報が必要です。この情報を持っているのが一般に lvalue（left-value）といわれているものです。

右側のaは値でも参照でもいいのですが、

a=3+a*2

のような場合、式の途中のa*2を計算する時に欲しいのはaの値です。そして値を使ってしまったら変数にアクセスする情報は必要ありません。ですから = の右側に変数名が出てきた場合は、変数名から変数の持っている値に変換します。

パースの最中はどっちかわからないので、とりあえずスタックには変数にアクセスするための情報（この場合配列var[]のインデックス）を保存します。
今回はpop()を変更して値に変換するようにしました。変数にアクセスする情報が欲しい時は ref_pop() を使います。

代入もオペレータと同じように expr=expr の形をしているはずなので、add()やmul()と同じく = の右と左をそれぞれ処理しています。
let()の中が add()→while(1)add() ではなく add()→let() なのは a=b=0 のような式に対応するためです。

• や * は左から順に処理をしていけばよかったのですが、= は右から順に処理をしなくてはいけません。つまり演算子の表によくある「結合規則が左←右」ということです。ですから、右側を先に処理するために再帰になっています。

結合規則が左←右というのは、 a=b=0 のような場合 a=(b=0) のように右を先に評価するという意味です。
逆に結合規則が左→右なら 例えば a-b-1 のような場合ですが (a-b)-1 の順で評価します。

演算子の優先順位が関数の呼び出し関係で処理されているのは最初に解説しました。結合規則もどこかにデータを持っているのではなく、 結合規則は呼び出す関数が1つ下なのか自分自身なのかで表現 します。

今までもそうでしたが、今回も最適化とエラー処理はしていません。

t3.c

/*
再帰下降サンプル
cc -o t3 t3.c
*/

# include <stdio.h>

char* text="b=a=5,a=a+(3+4)*5,b*7" ;
char* ptr ;
char token ;

int var[26]={0} ;	//	変数 a-z

//	計算結果を積むスタック
int stack[32] ;
int sp=0 ;
int t_stack[32] ;


int promote(int ref){
	return var[ref] ;
}

void push(int value, int tag){
	stack[sp]=value ;
	t_stack[sp]=tag ;
	sp++ ;
}

int pop(void){
	sp-- ;
	if(t_stack[sp]==1){
		//	スタックトップを数値に変換
		return(promote(stack[sp])) ;
	}
	return(stack[sp]) ;
}

int ref_pop(void){
	sp-- ;
	return(stack[sp]) ;
}


void get_token(void){
	while(*ptr==' ' || *ptr=='\t') ptr++ ;

	token=*ptr ;

	if(*ptr!=0){
		ptr++ ;
	}
}



void expr(void);

void factor(void){
	get_token() ;
	if(token>='0' && token<='9'){
		push(token-'0', 0) ;
		printf("number(%d)\n", token-'0') ;
		get_token() ;
	}
	else if(token>='a' && token<='z'){
		push(token-'a', 1) ;
		printf("var(%c)\n", token) ;
		get_token() ;
	}
	else if(token=='('){
		expr() ;
		get_token() ;
	}
	else if(token==','){
		token=0 ;
	}
}

//	掛け算
void mul(void){
	factor() ;
	while(1){
		if(token=='*'){
			factor() ;
			printf("mul\n") ;
			push(pop() * pop(), 0) ;
		}
		else if(token=='/'){
			factor() ;
			printf("div\n") ;
			int top=pop() ;
			push(pop() / top, 0) ;
		}
		else{
			break ;
		}
	}
}

//	足し算と引き算
void add(void){
	mul() ;
	while(1){
		if(token=='+'){
			mul() ;
			printf("plus\n") ;
			push(pop() + pop(), 0) ;
		}
		else if(token=='-'){
			mul() ;
			printf("minus\n") ;
			int top=pop() ;
			push(pop() - top, 0) ;
		}
		else{
			break ;
		}
	}
}

//	代入
void let(void){
	add() ;
	if(token=='='){
		int top, ref ;
		let() ;
		top=pop() ;
		ref=ref_pop() ;
		var[ref]=top ;

		printf("let(%c)=(%d)\n", ref+'a', top) ;
		push(top, 0) ;
	}
}

//	式の評価
void expr(void){
	let() ;
}

int main(void){
	ptr=text ;
	while(*ptr!=0){
		expr() ;
		printf("answer=%d\n", pop()) ;
	}

	return 0 ;
}

---

代入は、このパーサは 式 としています。式なので値を返します。
これを代入文（Assignment statement）としている言語もあります。
ここから先は各言語の定義が強く出てくるところなので、このパーサはこれで一段落とします。