仿查询分析器的C#计算器——4.语法分析

仿查询分析器的C#计算器——4.语法分析2011-07-16 博客园 conexpress上一篇中介绍通过词法分析将表达式转换成TokenRecord对象列表。在第一篇中提到将表达式用树形结构表示，然后就可以很方便的从下级节点取值计算了。那么如何将列表分析成一棵树的结构呢？

还是以例子来说明，比如3*7+56/8-2*5，分析成TokenRecord列表就是

记号对象	对应表达式
TokenValue	3
TokenMultiply	*
TokenValue	7
TokenPlus	+
TokenValue	56
TokenDivide	/
TokenValue	8
TokenMinus	-
TokenValue	2
TokenMultiply	*
TokenValue	5

分析成树就是

根据实际的算术规则，运算符优先级高的要先计算，然后由低优先级的运算符去调用它的运算结果。表现在树视图上就是高优先级的节点是低优先级节点的下级，即优先级越高，其位置越靠近树叶。因为这里采用统一的对象，把所有元素都用TokenRecord表示，所以TokenValue也是有优先级的。而通过对树视图的分析，所有的TokenValue都是处在叶子的位置，则TokenValue的优先级最高。

分析到这里就要用代码实现了。这里需要用到TokenRecord中的优先级Priority属性，还要用到堆栈。和词法分析一样，也是需要用循环依次分析各个TokenRecord。拿上面的TokenRecord列表进行分析，粗体字代表当前分析的TokenRecord。分析的过程中有一个原则叫“高出低入原则”，需要解释一下。

“高出低入原则”是指：

1.栈顶TokenRecord的优先级高于当前TokenRecord的优先级，则将栈顶TokenRecord弹栈（高出）到临时变量。

1.1如果堆栈为空，将临时变量中的TokenRecord加入当前TokenRecord的ChildList中，然后将当前TokenRecord压栈（低入）。

1.2如果堆栈不为空，找出栈顶TokenRecord和当前TokenRecord中优先级高的一个（相同则按栈顶高算），将临时变量中的TokenRecord加入高优先级TokenRecord的ChildList中。再用高出低入原则处理栈顶和当前TokenRecord。