Demo: CaculationTest
前言
有想过自己写一个计算器么？输入一些数学表达式就能自己计算解析生成结果。
如果没有，可以现在开始想想，也许你会发现自己计算要不了几秒钟的表达式，让程序计算却没这么简单。
本文以简化版的计算器为例，采用了编译原理的token解析及分析的方式，旨在让初学者了解和感受编译原理的基本思维。
【如果有一定的基础，可以阅读此文：http://www.codePRoject.com/Articles/246374/A-Calculation-Engine-for-NET】
假定
为了便于理解，我们现在简化需求，数据类型只有整数，运算符只有加减乘除，没有括号。运行结果如图所示：
解析过程
逐个分析表达式字符串的每一个char，将其解析为一系列的token（记号）。然后根据token代表的不同含义进行相应的操作，直到计算出最终结果。
（本例中并没有全部解析完token，再遍历token，而是边解析边进行操作。这样做效率稍微高一点，但不能直接查看解析出来的全部token。）
这和我们阅读也比较接近：我们从左往右依次读取信息，读的过程中，我们会根据上下文即前后组成，形成一定的语义，如“其实不忍”，你可能会理解为”他实在不忍心“，或者理解为”他其实是不忍心的“，这得依照你对上下文的理解去选择了。
对照刚才的比喻，可以得出，token是语义的基本组成，或者说对字符组成的一种抽象。程序中将token抽象为以下数据结构：
enumTokenType
{
Add,Sub,
Mul,Div,
Int,
Start,End
}classToken
{publicTokenType Type;publicobjectValue;publicToken(TokenType type ,objectvalue =null)
{
Type=type;
Value=value;
}
}
Token和表达式
Token必须解析为表达式才会有意义。有了表达式，我们才能计算出最终结果。一个表达式，是能表示明确意义的一个或一组token。
在C#中，我们有一元表达式，二元表达式；表达式中有不同的运算，如加减法；在此例中，所有的表达式都可以计算出某个值，而且表达式之间可以相互计算形成新的表达式，如”表达式（1*2）+表达式(2*3)”。基于此，有Expression类，也并不复杂：
abstractclassExpression
{publicabstractintGetValue();
}classUnaryExpress : Expression
{int_value;publicUnaryExpress(intvalue)
{
_value=value;
}publicoverrideintGetValue()
{return_value;
}
}classBinaryExpression : Expression
{
TokenType _tokenType;int_left;int_right;publicBinaryExpression(TokenType tokenType, Expression left, Expression right)
{
_tokenType=tokenType;
_left=left.GetValue();
_right=right.GetValue();
}publicoverrideintGetValue()
{switch(_tokenType)
{caseTokenType.Add:return_left +_right;caseTokenType.Sub:return_left -_right;caseTokenType.Mul:return_left *_right;caseTokenType.Div:return_left /_right;default:thrownewException("unexceptional token!");
}
}
}
此例中，并没有真正意义上的“一元表达式”，仅将数字看作它而已。二元表达式的值计算相对复杂，但类别也不多。
算法优先级
如果不算括号，恐怕对我们来说，用自己的“原始方式”解析表达式，最大的麻烦就是解决算法优先级的问题。
为什么“1+2*3” 不解析为1+2再乘以3呢，如何才能将其正确解析为2*3再和1相加呢？
首先我们需要顺序分析每个token, 表达式的解析顺序决定了最后的运算顺序，看下原代码中比较重要的这3个方法：
//解析加减Expression ParseAddSub()
{//左操作数为优先级较高的运算符varl =ParseMulDiv();while(_token.Type == TokenType.Add || _token.Type ==TokenType.Sub)
{vart =_token.Type;
ParseToken();varr = ParseMulDiv();//解析右操作数l =newBinaryExpression(t, l, r);
}returnl;
}//解析乘除Expression ParseMulDiv()
{varl =ParseUnary();while(_token.Type == TokenType.Mul || _token.Type ==TokenType.Div)
{vart =_token.Type;
ParseToken();varr=ParseUnary();
l=newBinaryExpression(t, l, r);
}returnl;
}//解析一元表达式（目前只有单个整数）Expression ParseUnary()
{
Expression ret=null;if(_token.Type ==TokenType.Int)
{
ret=newUnaryExpress((int)_token.Value);
}//解析完int后，移到下一个token处，即+-*/ParseToken();returnret;
}
1*2+2*2，我们可以看作两个乘法表达式相加，所以，解析加法运算的左右操作符前，程序尝试读取其是否是乘法表达式。
如果是1+2*3呢，左操作符当乘法运算解析时，并没有匹配上，由最高优先级的一元表达式决定其值，返回1，所以左操作数就是1了，当解析到+时，程序尝 试解析右操作数，从优先级比加法高一级的乘除开始，往上搜索匹配。很明显，2*3命中了乘法表达式，计算出右操作数的结果后，再和1相加，结果就正确了。
练习
如果研究透了demo，可以尝试把括号，取模运算，一元表达式（正负号）。
扩展
在IL代码和LinqExpression API中，“表达式”，“二元表达式”，“赋值表达式”，“成员获取表达式（.运算）”等，都很常见，解析的表达后对应的操作也很多，新建实例，引用实 例，访问局部变量等，赋值等。有兴趣可以查看一下Dynamic Linq的原代码（后续章节中，我们会写一个简单易版的Dynamic Linq动态计算 IQueryable.Where(string)）。