表达式的解析

　　解析和计算表达式的方式有很多种。在使用递归下降的解析器时，表达式被视为递归的数据结构—— 表达式由其本身来定义。假定表达式只能使用+、-、*、/和圆括号，那么所有的表达式可以用下面的规则来定义：

　　 表达式 à项 [+项] [–项]

　　 项à因数[*因数] [/因数]

　　 因数à变量、数字或者(表达式)

　　方括号里面表示可选元素，而箭头à表示箭头前面的元素由箭头后面的元素定义产生。实际上，该规则通常被称为表达式的生成规则。因此，对于项的定义可以这样表述：“项由因数乘以因数或者因数除以因数产生。”需要注意的是，运算符的优先级已经隐含在表达式的定义中。

　　下面举例说明表达式的解析过程。表达式

　　 10 + 5 * B

　　有两个项：10和5*B，第二项包括两个因数：5和B，分别是一个数字和一个变量。

　　下面看另外一个例子。表达式

　　 14 * (7 – C)

　　有两个因数：14和(7-C)，分别是一个数字和一个圆括号表达式。圆括号表达式包括两个项：一个数字和一个变量。

　　上述过程形成了递归下降解析器的基础。递归下降解析器是一组互相递归的方法，这些方法以一种链式方式实现生成规则。在每个适当的步骤上，解析器以代数学规定的正确顺序执行指定的操作。为了解释如何使用生成规则来解析表达式，采用下面的表达式来跟踪解析过程：

　　 9/3 – (100 + 56)

　　整个解析过程如下：

　　(1) 获得第一项9/3；

　　(2) 获得第一项的两个因数并完成除法运算，得到结果3；

　　(3) 获得第二项(100+56)。在这一步启动递归分析过程处理括号内的子表达式；

　　(4) 获得其中的两项并完成加法运算，得到结果156；

　　(5) 从第二项的递归计算过程中返回；

　　(6) 3减去156，答案是-153。

　　如果读者对于递归的理解有些困难，不要沮丧。递归是一个相当复杂的概念，需要慢慢来习惯。对于表达式的这种递归过程，请记住两个基本概念：第一，运算符的优先级隐含在生成规则的定义方式中；第二，这种递归解析和计算表达式的方式跟人们计算数学表达式的方式非常相似。

　　本章接下来将介绍两个解析器：第一个能够解析和计算仅由常量数据组成的double类型浮点表达式，该解析器说明递归下降解析方法的基本原理；第二个则增加了对变量的处理。