シンプルな再帰下降のサンプル（２） #再帰下降パーサ

力弱く ( ) に対応

前回は三種類のオペレータと数字1桁だけに対応したパーサを掲載し、オペレータの優先順位を解決する方法を示しました。
（シンプルな再帰下降のサンプル）
それに優先順位を変更する'('と')'への対応を追加します。
あと / の対応とホワイトスペースの読み飛ばしも。

'('に出会ったらexpr()を呼び出します。')'も含めて対応していない文字に出会ったらexpr()から抜けてきます。
これで再帰下降っぽくなりました。

t2.c

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

#include <stdio.h>

char* text="2*(3+4)*5" ;
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){
	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') ;
		printf("number(%d)\n", token-'0') ;
		get_token() ;
	}
	else if(token=='('){
		expr() ;
		get_token() ;
	}
}

//	掛け算	
void mul(void){
	factor() ;
	while(1){
		if(token=='*'){
			factor() ;
			printf("mul\n") ;
			push(pop() * pop()) ;
		}
		else if(token=='/'){
			factor() ;
			printf("div\n") ;
			int top=pop() ;
			push(pop() / top) ;
		}
		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){
	add() ;
}

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

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

	return 0 ;
}

解説

このパーサは数字一文字と四則演算のオペレータ + - * / それから ( を受け付け、算数の優先順位の通りに計算して結果を出力します。構文木は生成しません。

以下、+ ,* , (　について解説します。+と-、*と/は優先順位が同じですので、それぞれの後者は省略します。

main()からexpr()を呼んだ時にget_token()のptrは先頭の2を指しています(char text="2*(3+4)*5"の先頭の2です)。
add()の中ではまずmul()を呼び出します。これは+は expr+expr の形、たとえば 3+4 のような形をしているはずだから、まず+より左側を処理する必要があるからです。
同様にmul()も expr * expr の形をしているはずなので、まず先にfactor()を呼び出します。factor()は * よりも高い優先順位を持つモノの解析をします。
factor()は、数字が出てきたら数値をpush()して抜けます。また、開き括弧 ( が出てきたら、再帰的にexpr()を呼び出します。それ以外は単に関数を抜けてきます。

さて、最初の状態

2*(3+4)*5
^
でexpr()を呼ぶとexpr()→add()→mul()→factor()と呼ばれ、factor()がget_token()を呼び出したら'2'が返って来ます。factor()は2をpush()して抜けます。
戻ってきた所はmul()のwhile()です¹。ここまでで＊より左側にあって優先順位の高いものは、すべて数値になってpush()されているはずですから、* が出てきたら掛け算をしたいです。ですがまだ * の後ろの式が数値になっていません。そこで

2*(3+4)*5
　^

ここから後ろを数値に直すのに、もう一度factor()を呼びます。
factor()は'('が出てきたのでexpr()を呼び出します。そうすると()で囲まれた中が数値になってpush()されて帰って来ます。

mul()まで戻ってきた時には、2と(3+4)はそれぞれ数値になってpush()されていますから、それを取り出して掛け算をして、それをまたpush()します。

これでmain()に戻ってきた時には、結果がpush()されているはずです。

add()の中でmul()が2回以上呼ばれるのも、+,-の前後の式の優先順位の高い部分を数値になおすためで、mul()と同様です。
while()は、2+3+4+5 のような場合に対応する繰り返しです。

複数桁の数字への対応

複数桁の数字への対応はfactor()で行う方法も考えられますが、「数は'0'～'9'の1回以上の繰り返し」と定義すると、オペレータの優先順位とは関係なく解釈できます。こういう場合はget_token()の中で処理をして、「数値だよ」というステータスを付けて数値を返す方法もあります。
C言語の 0x00ff のような数も 1.2e-34 のような数も、factor()の中では数値として一律に扱えるので便利です。
複数桁の数字への対応のような処理は字句解析と言い、構文解析と切り離して処理するのが一般的です。

最後にシンプルな再帰下降のサンプル（３）変数と代入で変数と代入に対応して一回りということで。

ループを使うのは左再帰の解決法の１つです。 ↩