数式の構文解析

Cプログラミング講座



0.参考にした書籍内のページ

今回の講座は、「プログラミング言語C、第2版」P.92〜96の逆ポーランド記法解析プログラム及び、P150〜152のCの宣言文解析プログラムを参考にしています。

当該ページを読み、それでは実際の数式を構文解析するにはどれぐらい大変なのか、と考えました。
実際に作成し、作成中に気付いた注意点や、苦労した点を交えつつ、解説をしています。


1.構文解析の重要さ

構文解析というのは、定められた文法や規則に基づき、文章を理解することを指します。
プログラムにおいて大きな分野であり、かつ様々な形で利用され、その有用さは私たちが普段身をもって体験していると思います。

たとえば数式の構文解析の場合、コンピュータにとって処理しやすい逆ポーランド記法による数式なら、要素の切り出しとスタックの処理を作れば解析は比較的容易に行えます。
ですが実際の数式を解析して、計算させたい時、私たちにとっては理解しやすい数式が、コンピュータにとってはかなり複雑であることに気付かされます。
ですので今回は少し難しいかもしれませんが、私たちが普段用いる数式を構文解析し、答えを求めるプログラムを作れないかなと考え、かつ実際に作ってみました。


2.数式の構文解析プログラム

/* eval.c                               */
/* 数式を構文解析し、解を求める         */
/* コマンドライン第1引数として          */
/* シングルクォートで囲んで文字列を渡す */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define STR_LENGTH 256

enum token {NUMBER = 1, OPERATER = 2, LEFTPAREN = 3, RIGHTPAREN = 4};
//トークンの種類を定義する列挙型

struct count {	//トークン別に数をカウントする構造体
	int leftparen;	//カッコ
	int number;			//数
	int operater;		//演算子
	int sign;				//符号
	int rightparen;	//カッコとじ
};

char *mystrrep(char str1[STR_LENGTH], const char *str2, const char *str3);
int isoperator(char c);
char *getoperator(char *exp);
int gettoken(char *str, char *token);
int check(char *exp);
int calc(char *str, int i);
int eval(char *str);

/*
 * 関数名:main
 * コマンドライン引数:式として計算したい文字列
 * 機能:文字列を解析し、式として計算、値を返す
 * 返り値:引数エラー
 */
int main(int argc, char *argv[]){
	char exp[STR_LENGTH];
	if (argc < 2){
		printf("引数エラー\n第1引数として計算式を指定して下さい\n");
		return 1;
	}
	
	sprintf(exp, "(%s)", argv[1]);	//統一のため、計算する式自体も()で囲む
	while (strchr(exp, ' ')){	//スペースがある場合、消去
		mystrrep(exp, " ", "");
	}
	if (check(exp)){	//式が正規表現かチェック
		//正規表現でなければ、計算しない
		return 1;
	} else {	//チェックを通ったら、答えを求める
		printf("expression:%s\nanswer:%d\n", argv[1], eval(exp));
	}
	return 0;
}

/*
 * 関数名:mystrrep
 * 引数:文字列str1、文字列中の置換したい文字列str2、置換する文字列str3
 * 機能:str1中の最初のstr2パターンをstr3に置換する
 * 返り値:置換した先頭のアドレス
 */
char *mystrrep(char str1[STR_LENGTH], const char *str2, const char *str3){
	char temp[STR_LENGTH], *p;	//一時保存配列tempとポインタ操作用変数p
	
	if (strlen(str1) - strlen(str2) + strlen(str3) >= STR_LENGTH){
		//置換しても領域をオーバーしないかチェック
		printf("置換後の文字数が多すぎます\n");	//オーバーする場合は処理を終了
		return NULL;
	}
	
	p = str1;	//置換を行う
	if (p = strstr(p, str2)){	//str2のパターンが見つかる時真
		strcpy(temp, p + strlen(str2));	//置換される文字以降を一時保存
		*p = '\0';	//str2が現れる地点で文字列を切る
		strcat(str1, str3);	//str3を繋げたあとに
		strcat(str1, temp);	//元の文字列のstr2パターン以降を戻す
	}
	return p;
}


/*
 * 関数名:isoperator
 * 引数:1文字
 * 機能:引数の文字が演算子かであるかどうか判定する
 *      判定するのは加減乗除
 * 返り値:演算子であった場合1、そうでない時0
 */
int isoperator(char c){
	if (c == '+' || c == '-' || c == '*' || c == '/')
		return 1;
	else
		return 0;
}


/*
 * 関数名:getoperator
 * 引数:計算式を指し示すポインタ
 * 機能:計算式中の最初に現れる演算子の位置を求める
 *      カッコ内の演算子は判定しない
 * 返り値:演算子の位置のポインタ
 */
char *getoperator(char *exp){
	int i, count = 0;
	
	for (i = 0; (count != 0 || exp[i] != ')') && exp[i] != '\0'; i++){
		//現在検証中の式の外部のカッコとじまで探す
		//エラー回避用に文字列終端でも終了
		if (count == 0 && isoperator(exp[i])){
			//カッコ内ではない演算子の時返す
			return &exp[i];
		} else if (exp[i] == '('){
			//式中のカッコがある場合カウントする
			count++;
		} else if (exp[i] == ')'){
			//対応するカッコで外れる
			count--;
		}
	}
	return NULL;
}


/*
 * 関数名:gettoken
 * 引数:分解対象の文字列str、分解したトークンを格納する文字列token
 * 機能:文字列strから、カッコ、数字、演算子のいずれかを切り出す、末尾だとヌル文字
 * 返り値:切り出されたトークンに対応する整数
 *        (数字:1、演算子:2、カッコ:3、カッコとじ:4、それ以外はその文字のASCIIコード)
 */
int gettoken(char *str, char *token){
	int i = 0, j = 0;	//文字列操作用変数i
	while (str[i] == ' ')	//スペースを読み飛ばす
		i++;
	if (str[i] == '('){	//カッコを発見した場合
		strcpy(token, "(");
		return LEFTPAREN;
		
	} else if (str[i] == ')'){	//カッコとじを発見した場合
		strcpy(token, ")");
		return RIGHTPAREN;
	
	} else if (isdigit(str[i])){	//数字を発見した場合
		while (isdigit(str[i])){	//数である文字列部分を切り出す
			token[j] = str[i];
			i++;
			j++;
		}
		token[i] = '\0';
		return NUMBER;		//数字であることを返す
		
	} else if (isoperator(str[i])){	//演算子を発見した場合
		sprintf(token, "%c", str[i]);	//演算子を格納
		return OPERATER;
	} else {
		return str[i];
	}
}


/*
 * 関数名:check
 * 引数:数式の文字列
 * 機能:数式が正規表現となっているかチェックする
 * 返り値:正規表現の時0、そうでない時は1を返す
 */
int check(char *exp){
	int n, n0 = -1;
	//取得したトークンの種類を格納するn
	//前のトークンの値を保存するn0
	char token[10];	//トークンを格納する文字列、数字9ケタまで
	struct count c;	//トークンを種類別にカウントする構造体
	memset((void *)&c, 0, sizeof(struct count));	//構造体初期化
	
	while (*exp != '\0'){	//文字列終端でストップ
		switch(n = gettoken(exp, token)){	//トークンを取得、種類により分岐
		case NUMBER:	//数である時、式の先頭か、演算子または'('の後である
			if (n0 == -1 || n0 == OPERATER || n0 == LEFTPAREN){
				c.number++;
			} else {	//そうでないなら構文エラー
				printf("式の構文エラー\n");
				return 1;
			}
			break;
			
		case OPERATER:	//演算子である場合、')'の後か、数の後である、符号時の判定も行う
			if (n0 == RIGHTPAREN || n0 == NUMBER){
				c.operater++;
			} else if ((token[0] == '+' || token[0] == '-') && (n0 == -1 || n0 == LEFTPAREN)){
				//演算子が+か-である場合、式の先頭か')'の後なら負符号である
				c.sign++;
			} else {
				printf("式の構文エラー\n");
				return 1;
			}
			break;
			
		case LEFTPAREN:	//'('である場合、式の先頭か演算子の後か'('の後である
			if (n0 == -1 || n0 == OPERATER || n0 == LEFTPAREN){
				c.leftparen++;
			} else {
				printf("式の構文エラー\n");
				return 1;
			}
			break;
			
		case RIGHTPAREN:	//')'である場合、数の後か')'の後である
			if (n0 == NUMBER || n0 == RIGHTPAREN){
				c.rightparen++;
			} else {
				printf("式の構文エラー\n");
				return 1;
			}
			break;
		
		case '\0':	//ヌル文字の場合
			break;
		
		default:
			//取得したトークンが、式に関するものかヌル文字でない場合もエラー
			printf("式の構文エラー\n");
			return 1;
		}
		n0 = n;
		if (c.leftparen - c.rightparen < 0){	//'('より')'が多く現れたら、その時点で構文エラー
			printf("式の構文エラー\n");
			return 1;
		}
		exp = exp + strlen(token);	//次のトークンを取得するためにexpを進める
	}
	if (n != NUMBER && n != RIGHTPAREN){	//式末尾は数か')'でないといけない
		if (c.leftparen - c.rightparen != 0){	//カッコの数も合っているかチェック
			printf("式の構文エラー\n");
			return 1;
		}
	}
	
	//ここまでのチェックにひっかからなければ、正規表現
	return 0;
}


/*
 * 関数名:calc
 * 引数:式文字列、演算子の位置を示す変数
 * 機能:演算子の種類に従い、左右の値で計算する
 *      計算の終了した式は答えの値で置換する
 * 返り値:演算子により計算された式の値
 */
int calc(char *str, int i){
	int j = i, k,  temp = 0, a, b;
	//式中を配列で操作するための添え字j
	//文字列置換字に使うループ用変数k
	//式の値を保存する変数temp
	//式の左辺、右辺の値を保存するa,b
	
	char exp[STR_LENGTH], val[10];
	//演算している式を保存する文字列exp
	//値を文字列として使用するval
	
	char *pl, *pr, *next;
	//左辺の値の先頭pl、右辺の値の終端pr
	//右辺の先の演算子をチェックする時に使うnext
	
	while(1){	//左辺の値を検索する
		j--;
		if (str[j] == ')'){	//左辺終端がカッコとじである場合
			while (str[j] != '('){
				//カッコまで進めて、evalで左辺値を求める
				j--;
				if (j == -1){	//式の範囲をはみださないようにjの値をチェック
					printf("式の構文エラー\n左辺の値が取得できませんでした\n");
					exit(1);
				}
			}
			pl = str + j;	//左辺値の先頭を保存
			a = eval(pl);
			//左辺の値は得たので、ループを抜ける
			break;
			
		} else if (isdigit(str[j])){	//数だった場合
			while (isdigit(str[j - 1])){	//数の先頭までずらしてatoi
				j--;
				if (j == 0){	//式の範囲をはみださないようにjの値をチェック
					printf("式の構文エラー\n左辺の値が取得できませんでした\n");
					exit(1);
				}
			}
			pl = str + j;	//左辺の先頭を保存
			a = atoi(pl);	//値を取得して、ループを抜ける
			break;
		} else if (str[j] == '('){	//演算子が式先頭のマイナスだった場合
			a = 0;	//左辺値は0として演算すればよい
			pl = str + j + 1;
			break;
		}
	}
	
	j = i;	//今度は右辺の値を格納する
	while (str[j] != ')'){	//最大で右辺終端まで
		j++;
		if (str[j] == '('){	//右辺がカッコである場合
			pr = str + j;	//右辺値の値先頭アドレスを保存
			if (str[i] == '+' || str[i] == '-'){	//現在の式の演算子が加減である場合、先の乗除をチェックする
				if ((next = getoperator(pr)) != NULL){	//右辺の先に乗除がないか
					switch(*next){
					case '*':
					case '/':
						b = calc(pr, next - pr);	//乗除があった場合、先に計算
						break;
					case '+':
					case '-':
						b = eval(pr);	//そうでないなら、普通に右辺値を求める
					}
				} else {	//演算子がない場合
					b = eval(pr);	//右辺値を求める
				}
			} else {	//演算子自体が乗除なら、前から計算するので値をもらう
				b = eval(pr);
			}
			
			//右辺値終端を式の終わりと見るため
			//右辺値の終端を探す
			if (str[j] == '('){	//右辺先頭がカッコである場合
				while (str[j] != ')'){
					j++;
					if (str[j] == '\0'){
						printf("式の構文エラー\n右辺の値が取得できませんでした\n");
						exit(1);
					}
				}
			} else if (isdigit(str[j])){
				while (isdigit(str[j + 1]))
					j++;
			} else {
				printf("式の構文エラー\n右辺の値が取得できませんでした\n");
				exit(1);
			}
			//このときstr + jは右辺値の終端を指す
			break;
			
		} else if (isdigit(str[j])){	//右辺値が数の場合
			pr = str + j;	//右辺値先頭を保存
			if (str[i] == '+' || str[i] == '-'){
				if ((next = getoperator(pr)) != NULL){	//同じく右辺の先の乗除をチェック
					switch(*next){
					case '*':
					case '/':
						b = calc(pr, next - pr);	//先に計算
						break;
					case '+':
					case '-':
						b = atoi(pr);	//右辺値を求める
					}
				} else {
					b = atoi(pr);	//atoiで数を求める
				}
			} else {
				b = atoi(pr);	//自身の演算が乗除であった場合、先に計算
			}
			
			if (str[j] == '('){	//右辺先頭がカッコである場合
				while (str[j] != ')'){
					j++;
					if (str[j] == '\0'){
						printf("式の構文エラー\n右辺の値が取得できませんでした\n");
						exit(1);
					}
				}
			} else if (isdigit(str[j])){
				while (isdigit(str[j + 1]))
					j++;
			} else {
				printf("式の構文エラー\n右辺の値が取得できませんでした\n");
				exit(1);
			}
			break;
		}
	}
	
	//右辺、左辺の値を受け取ったので演算する
	switch(str[i]){
	case '+':
		temp = a + b;
		break;
	case '-':
		temp = a - b;
		break;
	case '*':
		temp = a * b;
		break;
	case '/':
		if (b == 0){	//0による割り算を回避
			printf("0による除算が行われました\n");
			exit(1);
		} else {
			temp = a / b;
		}
		break;
	}
	
	//計算の終わった式を消去する
	//左辺値の先頭が式の始まり、右辺値の計算より、str + jが終端である
	k = 0;
	while (pl + k <= str + j){	//まずは演算した式をexpにコピー
		exp[k] = pl[k];
		k++;
	}
	exp[k] = '\0';
	
	if (temp >= 0){	//値を文字列に写す
		sprintf(val, "%d", temp);
	} else {
		sprintf(val, "(%d)", temp);
	}
	
	mystrrep(str, exp, val);	//置換
	return temp;
}


/*
 * 関数名:eval
 * 引数:計算したい文字列
 * 機能:文字列を数式として計算し、処理する、再帰処理にも用いる
 *      最終的に、引数として渡した計算式も答えの値で置換される
 * 返り値:計算された式の値
 */
int eval(char *str){
	int i, temp, count = 0;
	//ループ用変数i、演算結果を保存するtemp、カッコのカウント用count
	char *p, exp[20], val[10];
	//ポインタ操作用p、演算した式exp、値を文字列として使用するval
	
	p = str + 1;	//式先頭は'('なので、必ず1つずらす
	temp = atoi(p);	//もしカッコ内が数だけの場合のため保存
	
	do {	//式中のカッコを探す(先に計算しておく)
		if (*p == '('){	//カッコを見つけた場合
			if ((temp = eval(p)) < 0){	//evalを適用
				count++;
				//負数だった場合カッコつきで置換されるので1つカウント
			}
		} else if (*p == ')'){	//カッコとじが現れた場合
			count--;
			//式終端のカッコとじか判定するためにカウントを減らす
		} else if (*p == '\0'){
			printf("式の構文エラー、カッコの位置が不正です\n");
			exit(1);
		}
		p++;	//式中のポインタを1つ進める
	} while (count != 0 || *p != ')');
	//式終端のカッコとじの場合のみループを抜ける
	
	while ((p = getoperator(str + 1)) != NULL){	//演算子を求め計算していく
		temp = calc(str, p - str);
	}
	
	count = 0;
	i = 0;
	//evalで計算していた式を、答えで置換するために
	//式先頭と対応するカッコまでをexpに保存
	do {
		if (str[i] == '('){
			count++;
		} else if (str[i] == ')'){
			count--;
		} else if (str[i] == '\0'){
			printf("式の構文エラー、カッコの位置が不正です\n");
			exit(1);
		}
		exp[i] = str[i];
		i++;
	} while (count != 0);	//式終了のカッコまでループ
	exp[i] = '\0';
	
	if (temp >= 0){	//答えで置換するためにvalに数文字列を作る
		sprintf(val, "%d", temp);
	} else {
		sprintf(val, "(%d)", temp);
	}
	mystrrep(str, exp, val);	//関数calcでも行っているが、値で式を置換
	
	return temp;
}

eval.cは、コマンドライン引数で渡した数式を構文解析し、答えを求めるプログラムです。
答えを関数の返り値とする他、引数として渡した文字列も答えの値に書き換えます
ですので、表示するならば前もってコピーをとっておかないといけません。

第1引数に数式を渡すとそれを解析してくれるのですが、マイナス記号やスペースなどは、端末が文字列として引数を受け取ってくれませんので、「eval '1-(2*(4+3))'などのように(シングルクォート)」などで囲んで渡します。
今の所、負数、カッコ、乗除優先に対応した演算を行います。
仕様として、値は全て整数とし、式中の除算もCにおけるint型同士の除算の仕様になります。
注意点ですが、渡す数式において最初の負数にカッコは必要ありませんが、第2項からは必ずカッコで囲う形であること。
式の最後は数かカッコとじである(イコールもいらない)という仕様になっています。

なお、数や演算子の間はスペースがあっても大丈夫なように作っています。

主要な関数は3つあります。

以上の関数を使いながら数式の答を求めます。
なお、ここで言う数式は、カッコで始まり、対応するカッコとじで終了する一連の文字列を指すこととします。

その他各関数に用いる雑関数として、

があります


3.プログラムの流れ及び主要関数eval,calc,checkの解説

主な流れとしては、まず引数として渡した数式を仕様統一のため、sprintfを用いて()でくくります。
そして、スペースがあった場合、それも消去します。
得られた計算式をcheck関数に渡し、式が構文的に正しいかチェック、ここでは簡略化しており、カッコ、カッコとじ、数、演算子、符号があるべき順序で並んでいるか、を検証します。
構文的に正しければ、計算式に対しeval関数を適用し、計算式(コマンドライン引数)と答を表示、そうでないならそのまま終了します。
以下各関数の説明です。

eval関数

式を受け取ったeval関数では、まずカッコでくくられた式の中身が、数が1項のみであるケースの場合、最終的に値で式を置換しなければいけないので値を保存します。
その後、式中のカッコを検索し、見つかればその地点にeval関数を再帰的に適用します。
eval関数の仕様上、適用された式は必ず1つの項に置換されるので、後の演算時には1項ごとの演算が可能となります。またこの時、eval関数で扱っている式の外部のカッコを判定しないために、カッコの数をカウント(対応をチェック)して、問題を解決しています。
カッコの検索が終了したら、次は数式から演算子を探し、その位置をcalc関数に渡し、関数内で左右の値と渡された演算子により演算された答を格納します
数式は置換され、calc関数に渡していた演算子は消えるので、再び数式中に演算子がなくなるまでcalc関数を適用します。
ここで重要なのが関数getoperatorの仕様なのですが、関数getoperatorはもし現在の数式の中にカッコがあった場合、その中の演算子は判定しないように作られています。
これにより、負数があった場合カッコをつけて置換することで、符号であるマイナスを判定することなく、演算子を探すことができます。
calc関数内での置換処理により、式中の演算子がなくなれば、今までeval関数で解析していた式全体を答えで置換します。この時、負数の場合はカッコをつけて置換します。

以上がeval関数の動作です。ポイントは、仕様を統一して、カッコ処理に自身を使うことができるようにしている、という所です。

calc関数

関数calcはコード量は多いですが、計算規則や符号によりパターン分けをしているだけなので、関数evalよりもやっていることは簡単です。
関数calcは引数として演算子の位置を渡されているので、その地点より前の文字列から左辺の値を取得します。
正の数であれば、数字の終わりまで見て、関数atoiを使えばいいですし、負数の場合は対応するカッコの先頭を関数evalに渡せば値を取得できます。
もし、渡された演算子が符号の'-'であった場合、左オペランドは存在しません。
ですが先の段落で述べたとおり、左オペランドは0として減算を行えば負数を取得できますので、左オペランドが取得できなかった場合は、0を左オペランドとして渡す事にします。
またこの時、最終的に計算式を演算結果で置換しなければならないので、式の左端と右端を保存のため、左辺先頭の地点をポインタplに保存しておきます。

続いて右辺、こちらは現在見ている演算子が加減であった場合、乗除優先のため、値を取得する前に、一つ先の演算子をチェックする必要があります。
もし乗除があれば、先にそちらの項に関数calcを適用すると、最後には置換されて演算が終了しますので、置換された値を右オペランドとして取得すれば、乗除優先の問題が解決できます。
最後に式の右端を求めておき、これで右辺に関する処理は終わりです。

あとは演算子の種類により左辺と右辺の値を演算、先ほど求めた左端と右端の間の文字列を、求められた答えで置換して、値を保存、これで関数calcの役割は終了です。

式の演算処理に関しては、この2つの関数を再帰的に呼び出すことで答えが定まるように作られています。
複雑でしたが、一度きちんと設計を行い、関数の動作を明確にしてからコーディングすることで、うまく作る事ができたと思います。

check関数

関数checkは単純で、計算式から要素を切り出す関数gettokenを使い、1つ前に何を切り出したか、という情報から式が構文的に正しいかどうかチェックするだけです。
左右カッコ、演算子、数をそれぞれ切り出しながら、コメントに書かれた判定法により、式が正しいか判定します。
もしここで式に不正があった場合、そのまま渡すと予期せぬエラーが起こってしまいます。
複雑なプログラムである場合、渡される関数のほうで対策するよりも、渡す前に判定できるものは全てやっておいた方がプログラムの安定化にも繋がります


4.まとめ、反省点、より良いプログラムなど

一応、仕様内で色々な数式が処理できるプログラムは書けました。
ですが、作成中は色んな入力でバグが見つかり、あるバグを直せば別の入力で予期しない動作になる、といった事がよく起こりデバッグがとにかく大変でした。
なので、ある程度指針を決めてきちんとノートで設計を考え、関数の役割や数式の処理を確立させたところ、その後に作ったプログラムではかなり動作が安定しました。
デバッグの際は、式として渡された文字がどのように置換されているか、どのように演算子を取得しているか、といった点を表示させてみたりすることで原因が見つけやすかったです。
プログラムとしては完成しましたが、実際手軽に使用できる電卓というほどの便利さと精度には程遠いです。構文規則が単純な数式ですらかなり苦労したので、自然言語の構文解析などは恐ろしく難しいものだなと感じます。

なお、値を文字列で置換しながら計算結果を保存するという方式は、最初思いついて友人に聞いてみたところ、「突飛な発想ではないか」と言われましたが、「数式の構文解析」などでWeb検索をかけてみたところVisual C#のテクニック解説のページが見つかり、同様の手法で数式を処理しているのを見て安心し、この手法で作成を進めようと思いました。
ほとんどはライブラリ関数に頼っているのであまり参考にはなりませんでしたが、URLも載せておきます。
http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/01/

また、プログラム作成に行き詰ってWeb検索をしていた際に、文字列を置換せずに計算しているプログラムを見つけました。
複雑に再帰を使っていて、値の保存も変数で行っているようです。
プログラム作成の指針が違っていたのであまり参考にはなりませんでしたが、項や演算子による分解をたくみに使っていて、よりスマートなプログラムであると思います。

http://www005.upp.so-net.ne.jp/h-masuda/cl/CAlgo/eval01.html


第1回講座へ
第2回講座へ

Cプログラミング講座 トップページへ


ページ作成者:elde
連絡先:s111058@wakayama-u.ac.jp