FANCOMI Ad-Tech Blog

株式会社ファンコミュニケーションズ nend・新規事業のエンジニア・技術ブログ

電卓を作った話

情報科学技術研究所のy_kawasakiです。どうも。

さてさて、Blog強化月間（自分の中で）というわけで、趣味8割位の記事です。業務とは一切関係がありません。

最近、新しいことにチャレンジするという意欲がめっきりなくなってきたお年頃なのですが、最近、弊社に来ているインターン生を見ていると、新しいことにチャレンジするということはいいことだなぁと。そして、先日、立命館大学で行われたソフトウェアプログラミングコンテストに審査員として参加してきて刺激を受けてきたので、新しいことにチャレンジしようと思いましたが、しんどいので昔取った杵柄とやらで、オレオレ言語づくりの一歩手前の電卓を作ることにしました。（どこらへんが新しいことなのかわからない。。。）

www.wantedly.com

概要

電卓ごときに、yaccとかbisonとか、flexとか使うのは趣味に合わないのでレキサーやパーサーは書き下ろしています！というわけで、入力部、字句解析部、構文解析（抽象構文木生成）、計算部から成り立つ電卓です。
だいたい300行程度ですね。頑張ればもっと短くスッキリかけるかなとは思いますが。わりかし読みやすさ重視で書きました。

電卓の仕様

  • 四則演算ができる
  • 優先順位が正しい計算

使用言語


昔取った杵柄ですから、やっぱり、C言語ですね。ここは譲れません。

文法

<addsub> ::= <muldiv> ( '+' <muldiv> | '-' <muldiv> )*
<muldiv> ::= <factor> ( '*' <factor> | '/' <factor>)*
<factor> ::= NUM | '(' <addsub> ')'

解説

入力部

ポイントは、readlineを使ってみた所。

		cmd = readline(">> ");
		if(cmd == NULL){
			free(cmd);
			break;
		}
		add_history(cmd);

これで、過去の履歴呼び出しも、編集も自由自在！

字句解析

関数名：lexer

ごりごり1文字づつ読んでやってます。最近のはやりの言語とか、flexとかだったら、まぁ、正規表現とかを駆使して書くんでしょうか。よくわかりませんが。ルールに従って単純にごりごり書いていくだけなので、そんなに難しくないです。工夫した点は、長くてもOKな数値とか、項がいっぱいあっても大丈夫なように、随時メモリを確保する方式にした点でしょうか。最大個数や最大文字数を決め打ちにすればもっとスッキリ書けるんですけどね。

抽象構文木生成

関数名：evaluateで始まるやつ

構文解析と意味解析を一気にやってる部分。bisonとか使うんですかね。というか、これくらいなら使わなくてもかけますね。というか、文法ルールを考えるのが大変（といっても電卓程度では大したことない）だけど、実装はわりかしスッキリかけてるかなという気がしています。再帰関数を使っているのであまり深いと。。。って、電卓程度では多分大丈夫です。

たとえば、2*(3+1)と入力するとこんな構文木が生成されます。

f:id:fan_y_kawasaki:20171130124337p:plain
構文木イメージ

実行部

関数名：calc

構文木をてっぺんから辿って、と、こちらも大したことはやっていません。こちらも、再帰関数の練習ですかね。再帰関数を使っているのであまり深い（ｒｙ

実行結果

>> 2 * (3 + 1) 

TOKEN TYPE: NI   TOKEN: 2 VALUE: 2
TOKEN TYPE: MUL  TOKEN: *
TOKEN TYPE: LB   TOKEN: (
TOKEN TYPE: NI   TOKEN: 3 VALUE: 3
TOKEN TYPE: PLS  TOKEN: +
TOKEN TYPE: NI   TOKEN: 1 VALUE: 1
TOKEN TYPE: RB   TOKEN: )
 (* 2.000000 (+ 3.000000 1.000000))
Result-> 8.000000
>>

今後の展望

とりあえず、組み込み関数（logとか？）はつけてみたいですね。ゆくゆくは、変数機能や自作関数とか、ってそこまで行くと、もう、オレオレ言語の世界ですね！夢は広がります！（あくまでも夢です）

もしくは、秋葉原でトランジスタを買い込んできて、チクチクとはんだ付けして、いや、冗談です。

最後に

弊社では業務とは関係ないけど、コンパイラをインターンで作ってみたいというインターン生を募集しています。詳細は下のページを見てください！

www.wantedly.com

ソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#include <readline/readline.h>
#include <readline/history.h>

typedef enum _token_type {
	INITIAL,
	IDENT,    /* 識別子 */
	NUM,      /* 数値 */
	NUM_I,    /* 数値（整数）*/
	NUM_D,    /* 数値（実数）*/
	SYMBOL,   /* 記号   */
	PLUS,     /* + */
	MINUS,    /* - */
	MULTI,    /* * */
	DIV,      /* / */
	LB,       /* ( */
	RB,       /* ) */
	END
} TOKEN_TYPE;

typedef struct _token {
	TOKEN_TYPE    type;
	char          *token;
	double        value_d;
	long          value_l;
	struct _token *next;
	struct _token *prev;
} TOKEN;

typedef struct _node {
	char *name;
	struct _node *left;
	struct _node *right;
	double rval;
	TOKEN *token;
} NODE;

NODE *evaluateAddSub();
NODE *evaluateMulDiv();
NODE *evaluateFactor();

TOKEN *token;

NODE *createNode(TOKEN* token)
{
	NODE *node = calloc(1, sizeof(NODE));
	if(node == NULL){
		fprintf(stderr, "Memory Allocation Error");
		exit(EXIT_FAILURE);
	}
	node->left  = NULL;
	node->right = NULL;
	node->name = token->token;
	node->token = token;
	return node;
}

void addChild(NODE *node, NODE *left, NODE *right)
{
	node->left = left;
	node->right = right;
}

// <addsub> ::= <muldiv> ( '+' <muldiv> | '-' <muldiv> )*
NODE *evaluateAddSub()
{
	NODE *left = evaluateMulDiv();
	while(token != NULL && (token->type == PLUS || token->type == MINUS)) {
		NODE *node = createNode(token);
		token = token->next;
		NODE *right = evaluateMulDiv();
		addChild(node, left, right);
		left = node;
	}
	return left;
}

// <muldiv> ::= <factor> ( '*' <factor> | '/' <factor>)*
NODE *evaluateMulDiv()
{
	NODE *left = evaluateFactor();
	while(token != NULL && (token->type == MULTI || token->type == DIV)){
		NODE *node = createNode(token);
		token = token->next;
		NODE *right = evaluateFactor();
		addChild(node, left, right);
		left = node;
	}
	return left;
}

// <factor> ::= NUM | '(' <addsub> ')'
NODE *evaluateFactor()
{
	NODE *node;
	if(token->type == LB){
		token = token->next;
		node = evaluateAddSub();
		if(token->type != RB){
			fprintf(stderr, "Missing ) ?");
			exit(EXIT_FAILURE);
		}
		token = token->next;
	} else {
		node = createNode(token);
		node->rval = token->value_l;
		token = token->next;
	}
	return node;
}

double calc(NODE *node)
{
	if(node->token->type == NUM_I || node->token->type == NUM_D){
		return node->rval;
	}
	double left = calc(node->left);
	double right = calc(node->right);
	if(node->token->type == PLUS) return left + right;
	if(node->token->type == MINUS) return left - right;
	if(node->token->type == MULTI) return left * right;
	if(node->token->type == DIV) return left / right;
}

void lexer(char *s)
{
	unsigned int idx;
	unsigned int bgn;
	TOKEN *t;
	TOKEN_TYPE tt;
	for(idx = 0; s[idx] != '\0'; ) {

		/* 空白文字の処理 */
		if(s[idx] <= ' '){
			idx++;
			continue;
		}

		/* Token */
		bgn = idx;
		/* [a-zA-Z][a-zA-Z0-9]* */
		if(isalpha(s[idx])){
			while(isalnum(s[idx])){
				idx++;
			}
			tt = IDENT;
		}
		/* ([0-9]+)|([0-9]+\.[0-9]+) */
		else if(isdigit(s[idx]) || s[idx] == '.' || (s[idx] == '-' && isdigit(s[idx+1]))) {
			int c = 0;
			if(s[idx] == '.'){
				c += 1;
			}
			idx += 1;
			while(isdigit(s[idx]) || s[idx] == '.') {
				if(s[idx] == '.'){
					c += 1;
				}
				idx++;
			}
			if(c == 0){
				tt = NUM_I;
			} else if(c == 1) {
				tt = NUM_D;
			} else {
				fprintf(stderr, "Parse Error\n");
				return;
			}
		}
		/* それ以外 */
		else {
			switch(s[idx]){
			case '+':
				tt = PLUS;
				break;
			case '-':
				tt = MINUS;
				break;
			case '*':
				tt = MULTI;
				break;
			case '/':
				tt = DIV;
				break;
			case '(':
				tt = LB;
				break;
			case ')':
				tt = RB;
				break;
			default:
				tt = SYMBOL;
				break;
			}	
			idx++;
		}
		
		t = (TOKEN*)malloc(sizeof(TOKEN));
		t->token = (char *)malloc(idx - bgn + 1);
		strncpy(t->token, &s[bgn], idx - bgn);
		t->token[idx - bgn] = '\0';
		t->type = tt;
		if(tt == NUM_I){
			sscanf(t->token, "%ld", &t->value_l);
		} else if(tt == NUM_D) {
			sscanf(t->token, "%lf", &t->value_d);
		}
		t->next = NULL;
		token->next = t;
		t->prev = token;
		token = t;
	}
	return ;
}

void printAST(NODE *node)
{
	int n;
	if(node == NULL){
		return;
	}
	printf(" (%s", node->name);
	NODE *child;
	child = node->left;
	if(child != NULL && (child->token->type == NUM_I || child->token->type == NUM_D)) {
		printf(" %lf", child->rval);
	} else {
		printAST(child);
	}
	child = node->right;
	if(child != NULL && (child->token->type == NUM_I || child->token->type == NUM_D)) {
		printf(" %lf", child->rval);
	} else {
		printAST(child);
	}	
	printf(")");
}


NODE *parser()
{
	NODE *expr;
	if(token->type == INITIAL){
		token = token->next;
	}
	expr = evaluateAddSub();
	printAST(expr);
	printf("\n");
	return expr;
}

void free_token()
{
	TOKEN *t;
	while(1){
		t = token->next;
		free(token);
		
		if(t == NULL){
			break;
		}
		token = t;
	}
	token = NULL;
}

void free_node(NODE* node)
{
	if(node->token->type == NUM_I || node->token->type == NUM_D){
		free(node);
		return;
	}
	free_node(node->left);
	free_node(node->right);
	free(node);
	return;
}

void print_token(TOKEN* token)
{
	while(1) {
		if(token->type == END){
			break;
		}
		if(token->type != INITIAL){
			printf("TOKEN TYPE: ");
			switch(token->type){
			case IDENT:
				printf("ID   ");
				break;
			case NUM:
				printf("NM   ");
			case NUM_I:
				printf("NI   ");
				break;
			case NUM_D:
				printf("ND   ");
				break;
			case SYMBOL:
				printf("SM   ");
				break;
			case PLUS:
				printf("PLS  ");
				break;
			case MINUS:
				printf("MNS  ");
				break;
			case MULTI:
				printf("MUL  ");
				break;
			case DIV:
				printf("DIV  ");
				break;
			case LB:
				printf("LB   ");
				break;
			case RB:
				printf("RB   ");
				break;
			default:
				printf("UK   ");
			}
			printf("TOKEN: %s", token->token);
		}
		if(token->type == NUM_I) {
			printf(" VALUE: %ld", token->value_l);
		}
		if(token->type == NUM_D) {
			printf(" VALUE: %lf", token->value_d);
		}

		printf("\n");
		if(token->next == NULL){
			break;
		}
		token  = token->next;
	}
}

int main(int argc, char* argv[])
{
	char *cmd;
	TOKEN *o_token;
	NODE *expr;
	double result;
	using_history();
	read_history(".calc_history");

	while(1){
		token = (TOKEN*)malloc(sizeof(TOKEN));
		o_token = token;
		token->type = INITIAL;
		token->prev = NULL;
		token->next = NULL;
		
		cmd = readline(">> ");
		if(cmd == NULL){
			free(cmd);
			break;
		}
		add_history(cmd);
		
		lexer(cmd);
		//print_token(o_token);

		token = o_token;
		expr = parser();
		result = calc(expr);
		printf("Result-> %lf\n", result);
		token = o_token;

		free_node(expr);		
		free_token();
		free(cmd);
	}
	write_history(".calc_history");
	return EXIT_SUCCESS;
}