做了一个能够计算简单数学表达式值的小计算器，算不上是编译器，但用到了编译器的知识。最近在看一些编译器的东西，所以动手写这个最简单的计算器，既是对那些抽象的编译器知识有个形象的认识，也为后面添加复杂的东西－－语句打下基础。此计算器是以《编译原理与实践》中实现的tiny编译器为参考写的，tiny是一个值得去研究的编译器，可以说是麻雀虽小，五脏俱全。从词法分析到代码生成都有，并且代码非常清晰易懂。我觉得想要了解编译器，可以从tiny入手，去将它跑起来并分析。废话不多说，开始记录这个小计算器。

先说下需求：

1、只支持最简单的＋ －＊／  运算

2、支持括号嵌套

3、只支持正数

需求就这么简单的三条，可以将思路集中在与编译器相关的知识上面。比如可以计算（5+3）＊2这个表达式，得到值16。或者计算 7- 5*3得到值－3。

接下来说说实现的的思路，在此之前先扯一个我在大学里面学过的一个方法，是学数据结构的栈时，老师举了一个利用栈来计算简单数学表达式值的方法。其方法就是依次扫描这个表达式，根据操作符的优先级来决定其入栈的顺序，最后得到表达式的一个后缀表达式，最后利用这个后缀表达式来求值。

这里要介绍的方法与上面的方法有点类似，也是要先扫描一遍表达式，不过扫描完之后得到的不是一个后缀表达式，而是一棵语法树，然后对这棵语法树进行递归求解。下面就是表达式（5+3）＊2这个表达式对应的语法树。对这棵语法树进行后序遍历其实也能得到一个后缀表达式，所以说两种方法还是相通的。

                         ＊

                      /       \

                    +         2

                 /      \

               5        3

学过编译原理的都知道，要实现某种语言，就先要定义其语法。语法的作用是用来定义语言是什么样子的（废话），比如计算器的语法就定义了操作的优先级、结合性等。如果扫描过程中发现表达式不符合语法的定义，就认为表达式是非法的，比如 表达式“5+3-”就是非法的，因为减号后面没有被减数。下面放出语法：

expr -> term |  term+term | term-term                     

term -> factor | factor * factor | factor/factor

factor -> number | (expr)

number -> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)*

我觉得定义语法是一个比较有腩肚的事情，至少这个语法不是我造的，是从tiny编译器中拿过来的。这个语法看起来比较清晰，三条语法出现的先后顺序代表了计算的优先级，括号最高，乘除次之，加减最低。factor代表一个最小的计算因子，可以是数字或者一个括号括起来的表达式。term代表一个乘法或者除法表达式，exprt代表一个加法或者减法表达式，term和expr也可以直接是num或者（expr）

定义语法要考虑消除左递归的问题，比如如果将第一条语法expr -> term |  term+term | term-term 写成expr -> term | expr+term | expr-term，这样是能体现加减法具有左结合性，但是这条语法如果直接写成递归函数，就会有死循环的问题。tiny的这个语法消除了左递归，把加减法的左结合性问题丢给了expr对应的函数来处理。

下面开始上代码，先看下处理expr的函数

TreeNode *exp()
{
	TreeNode *node;
	TreeNode *lnode, *rnode;
	
	node = term();

	/*如果下一个符号是+ 或者-，那么就以操作符作为根节点
	两个操作数作为子节点*/
	while ((ADD == token) || (MINUS == token))
	{
		/*左节点*/
		lnode = node;
		
		/*操作符节点，即根节点*/
		node = newNode();
		node->attr.e = OpK;
		node->val.tt = token;
		node->child[0] = lnode;
		
		match(token);

		/*右节点*/
		rnode = term();

		node->child[1] = rnode;
	}
	
	return node;
}

下面是term函数的代码，与exp函数非常相似，不需要再详细说明。

TreeNode *term()
{
	TreeNode *node;
	TreeNode *lnode, *rnode;

	node = factor();

	/*将乘法或者除法操作符作为根节点，并得到左右节点*/
	while ((MUL == token) || (DIV == token))
	{
		lnode = node;
		node = newNode();
		node->attr.e = OpK;
		node->val.tt = token;
		node->child[0] = lnode;
		
		match(token);

		rnode = factor();

		node->child[1] = rnode;
	}
	
	return node;
}

接下来是factor函数，代表一个最小的计算因子。

TreeNode *factor()
{
	TreeNode *node;

	switch (token)
	{
		/*一个数字*/
		case NUM:	
			/*生成并返回一个节点，节点类型就是常数*/
			node = newNode();
			node->attr.e = ConstK;
			node->val.num = atoi(tval);
			match(NUM);
			break;
		/*左括号*/
		case LPAREN:
			match(LPAREN);
			/*调用exp来解析一个表达式*/
			node = exp();
			match(RPAREN);
			break;		
		default:
			printf("<Error>factor: Token cann't handled.\n");
			exit(1);
			break;
	}
	
	return node;
}

通过上面几个函数，可以返回一棵语法树，下面的calc函数通过这个语法树来递归地进行求值。

int calc(TreeNode *node)
{
	int val;
	int val1, val2;

	if (NULL == node)
	{
		printf("<Error>calc: syntax error.\n");
		exit(1);
	}

	/*根据节点的属性返回相应的值，目前节点有两种
	属性:数字或者操作符*/
	switch (node->attr.e)
	{
		/*数字属性节点直接返回值*/
		case ConstK:
			return node->val.num;
			break;
		/*操作符属性节点值需要先计算两个操作数的值，
			再根据操作符来计算最后的结果*/
		case OpK:
			val1 = calc(node->child[0]);
			val2 = calc(node->child[1]);
			switch (node->val.tt)
			{
				case ADD:
					val = val1 + val2;
					break;
				case MINUS:
					val = val1 - val2;
					break;
				case MUL:
					val = val1 * val2;
					break;
				case DIV:
					val = val1 / val2;
					break;
				default:
					printf("<Error>cal: Unknown operation.\n");
					exit(1);
					break;
			}
			break;
		default:
			printf("<Error>calc: Unknown expression type.\n");
			exit(1);
			break;
	}
	
	return val;
}

这个小计算器的主体代码介绍完了，其它的就剩下一些支撑函数，如getToken函数用来获取一个token，match函数用来判断获取出来token与当前语法要求的token是否一致，如果不一致，就说明出现了语法错误。

将代码进行编译：

gcc -fno-builtin mycomplier.c -o mycomplier

然后建立一个文件exprtest，里面的内容为要计算的表达式，如 3+(10-2) * 5 

保存exprtest文件后，输入mycomplier   exprtest，即会输出The result is 43.

好了，这个小计算器就总结完了。它还有很多数值方面的功能有待完善，比如支持负数和其它操作符。但正如开始所说，这里重点关注编译器方面的知识，我是个急性子，所以没太花时间去处理这些数值操作。后面会完善这个计算器，在其中加入处理语句的功能，让它更像是在编译一个语言。

完整代码下载路径编译器原理－－一个小计算器    

有什么问题欢迎发邮件交流学习：）

Email:    robin.long.219@gmail.com

编译器－－简单数学表达式计算器