シンプルな再帰下降のサンプル

+-*と数字1文字だけを受け付ける再帰下降パーサ

再帰下降は計算機業界のロンダートからの後方宙返り。
プログラムを書く人は知っていて決して損はしません。

再帰下降はオペレータの優先順位をどこかにデータで持っているのではなくて、より優先順位の高いオペレータを処理する関数を呼び出す親子関係で、優先順位の高い・低いを表現します。

再帰下降で検索すると立派なパーサはいっぱい出てくるけど、結局どういう事か良くわからないで終わりそうです。ここはひとつ、シンプルに + - * の3つのオペレータと、数字1文字だけを受け付けるパーサを書いてみましょう。
+-に対応するのは、優先順位の同じオペレータの処理の例として、それと * に対応するのは優先順位の高いオペレータをどう処理するかを示すためです。2桁以上の数字の対応は字句解析の範囲なので、1桁で充分でしょう。
あと、せっかくですから、結果を計算するためにスタックを用意します。
短いソースなので、読み解くのは難しくないと思います。

この例ではexpr()は一度しか呼ばれませんが、優先順位を指定する()を実装したら、括弧のなかで再帰的にexpr()を呼ぶようになるでしょう。
再帰は無いので、ただの下降パーサですが、優先順位をどう処理しているのか、感じはつかめると思います。

t1.c

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

# include <stdio.h>

char* text="2-3*4+5*6" ;
char* ptr ;
char token ;

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

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

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


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


//	数値
void digit(void){
	get_token() ;
	if(token>='0' && token<='9'){
		push(token-'0') ;
		printf("number(%d)\n", token-'0') ;
		get_token() ;
	}
}

//	掛け算	
void mul(void){
	digit() ;
	while(1){
		if(token=='*'){
			digit() ;
			printf("mul\n") ;
			push(pop() * pop()) ;
		}
		else{
			break ;
		}
	}
}

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

//	式の評価
void expr(void){
	while(*ptr!=0){
		add() ;
	}
}

int main(void){
	ptr=text ;
	expr() ;

	printf("answer=%d\n", pop()) ;

	return 0 ;
}

実行結果

$ ./t1
number(2)
number(3)
number(4)
mul
minus
number(5)
number(6)
mul
plus
answer=20

---

()に対応したバージョンの シンプルな再帰下降のサンプル(2) を載せました。