数式解析

　数式解析とは字句解析によってできたトークン列の関係性を把握し、構文木を作ることです。これを行うことにより、定められた文法や規則に基づき、計算式をチェックすることができます。

　　上のような図を構文木といいます。
　()や√のような先にしなければならない計算が下の方へなど、演算子の計算手順に合わせて計算式を成り立たせます。

■数式解析プログラム

#include <stdio.h>

#define NOTOKEN		(-3)
#define TokenError	(-2)
#define EOF			(-1)
#define Number	0	// 整数
#define Plus	1	// +
#define Minus	2	// -
#define Aster	3	// *
#define Slash	4	// /
#define LPar	5	// (
#define RPar	6	// )

char *nextch = "";
int has_stock = -1; // -1:初期状態  0:字句を戻していない状態  1:字句を戻した状態
int stock_code;
int stock_value;

// 字句操作関数群
void setText(char *s);
int  nextToken(int *value);
void putBack(void);

int expression(void);

#define BUFFSIZE	256

int syntaxError = 0;

/*
 * 因子 ::= 整数 | '(' 式 ')'
 */
int factor(void){
	int code, value;
	code = nextToken(&value);

	// (
	if (code == LPar) {
		int answer = expression();
		code = nextToken(&value);
		if (code != RPar)
			syntaxError = 1;
		return answer;
	}

	if (code != Number)
		syntaxError = 1;

	return value;
}

/*
 * 項 ::= 因子 | 項 (*|/) 因子
 */
int term(void){
	int code, value, answer;

	answer = factor();
	if (syntaxError)
		return answer;
	while (((code = nextToken(&value)) == Aster ) || (code == Slash)){ // * or / を見つけたら計算する。
		int t = factor();
		if (code == Aster)
			answer *= t;
		else
			answer /= t;
	}
	putBack();
	return answer;
}

/*
 * 式 ::= (+|-)? 項 | 式 (+|-) 項
 */
int expression(void){
	int code, value, answer, sign = 1;

	code = nextToken(&value);
	if (code == Minus)	//ここで数字が+か-を判断する。
		sign = -1;
	else if (code == Plus)
		;
	else
		putBack();

	answer = sign * term();
	if (syntaxError)
		return answer;
	while (((code = nextToken(&value)) == Plus ) || (code == Minus)){//+ or -を見つけたら計算する。
		int t = term();
		answer += (code == Plus) ? t : (-t);
	}
	putBack();
	return answer;
}

/*
 * 行 ::= 式?  EOF
 */
void line(void){
	int code, value, answer;

	code = nextToken(&value);
	if (code != EOF){
		putBack();
		answer = expression();
		if (!syntaxError)
			printf("\t%d\n", answer);
		code = nextToken(&value);
		if (code != EOF)
			syntaxError = 1;
	}
}
void setText(char *s){
	nextch = s;	//この中に解析対象の文字列を入れる。
}

int getToken(int *value){
	int c;

	// 空白を読み捨てる。
	while (isspace(*nextch))
		nextch++;

	if (!*nextch)
		return EOF;

	c = *nextch++;
	if (c == '+')
		return Plus;
	if (c == '-')
		return Minus;
	if (c == '*')
		return Aster;
	if (c == '/')
		return Slash;
	if (c == '(')
		return LPar;
	if (c == ')')
		return RPar;

	if (isdigit(c)){
		*value = 0;
		while (isdigit(c)){
			*value = 10 * *value + c - '0';
			c = *nextch++;
		}
		nextch--;
		return Number;
	}

	return TokenError; // エラー
}

/*
 * 字句をひとつ戻す。（ように見せかける）
 */
void putBack(void){
	if (has_stock == 0)
		has_stock = 1;
}

/*
 * 次の字句の字句コードを返す。
 * 次の字句が整数の場合は、
 * その数値を *valueへセットし、字句コードNumberを返す。
 */
int nextToken(int *value){
	if (has_stock > 0){
		has_stock = 0;
		*value = stock_value;
		return stock_code;
	}
	has_stock = 0;
	stock_code = getToken(&stock_value);
	*value = stock_value;
	return stock_code;
}

int main(){
	char buff[BUFFSIZE];

	fprintf(stderr, "%% ");
	while (gets(buff)){
		syntaxError = 0;
		setText(buff);
		line();
		if (syntaxError)
			fprintf(stderr, "構文エラー！\n");

		fprintf(stderr, "%% ");
	}
	fprintf(stderr, "See you.");

	return 0;
}

　※このプログラムでは√の計算はできません。次のステップで√の計算ができるようになります。

■完成写真

次のステップでは、これまで学んだことを活かして関数電卓を作ってみましょう。