递归下降的表达式解析器

《递归下降的表达式解析器》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、37第2章递归下降的表达式解析器递归下降的表达式解析器如何编写一个程序，使之接收包含数字表达式的字符串(如(10-5)*3)作为输入，并通过计算得到正确的输出结果呢？也许只有少数的“大师级”程序员才能够做到这一点。除了这些人，多数熟练的程序员都不太清楚高级语言如何把算术表达式转化为计算机可执行指令。高级语言将算术表达式转化为计算机可执行指令的过程，被称为表达式解析(expressionparsing)。表达式解析过程将算术表达式转化为计算机可以识别的形式。它也是所有需要进行表达式转换的软件的核心，这些软件包括语言编译器和解释器、电子制表软件等等。虽然有些程序员对表达式解析的工作过

2、程感到神秘。但它实际上是一个定义明确的任务，有着一套相当优美的解决方案。这是因为该问题已经过了明确的定义，只需根据严格的代数规则进行。本章内容由浅入深，介绍了通常所说的递归下降解析器的含义，以及计算代数表达式的值所需的所有相关规则。在掌握了解析器的工作流程之后，根据自身的需求修改解析器、增强解析器功能就不再是一件难事。之所以将解析器选为本书的第一个例子，不仅仅是因为解析器本身就是一段非常有用的代码，而且它还充分体现了Java语言的强大功能和广泛应用范围。解析器被称为是“纯代码(purecode)”37第2章递归下降的表达式解析器的子系统，这是指它既不面向网络，也不依赖于GUI界面

3、，同时也不是一个Applet或者Servlet等。上述类型的代码多用C或者C++语言编写，但用Java编写却并不常见。Java是一股革命性力量，它从根本上改变编写Internet程序的方式，因此人们有时甚至忘记了Java并不仅仅局限于Internet环境。Java特征完备，几乎可用于所有的编程任务。本章介绍的解析器将证明这个观点。2.1表达式由于解析器处理的对象是表达式，因此有必要介绍表达式的组成。虽然表达式的类型多种多样，但本章只处理一种类型：数值表达式。数值表达式由下列元素组成：●数字●运算符+、–、/、*、^、%、=●圆括号●变量其中，^运算符表示求幂运算(不是Java中规

4、定的XOR运算)，＝是赋值运算符。这些元素按照代数学的规则组合成表达式。例如：10–8(100–5)*14/6a+b–c10^5a=10–b每个运算符的优先级如表2-1所列：表2-1运算符优先级最高优先级最低优先级+-(正负号)^*/%+-=优先级相等的运算符按照从左到右的顺序计算。本章介绍的解析器必须满足以下一些约束条件：第一，所有变量都是单个字母(从A到Z的26个变量)，字母不区分大小写(把a和A视为同一个变量)。第二，假定所有的数字都是double类型，可以方便地修改解析器从而处理其他类型的值。最后，为保证逻辑清晰和理解方便，解析器只进行基本的错误检查。37第2章递归下降的

5、表达式解析器2.2解析表达式没有对表达式解析进行全面思考的人，会认为这个问题非常简单，但实际上并非如此。为了更好理解这一点，计算下面的简单表达式：10–2*3众所周知，这个表达式的结果等于4。编写一个程序计算某个特定的表达式非常容易，但问题在于如何创建一个程序，来为任意的表达式给出正确的答案。首先考虑下面的运算法则：a=getfirstoperandwhile(operandspresent){op=getoperatorb=getsecondoperanda=aopb}该方法依次获得第一个操作数、运算符和第二个操作数以执行第一个操作；然后获得下一个运算符和操作数以执行下一个操作

6、，依此类推。然而，如果采用这种基本方式计算上面的表达式，那么10–2*3的结果将是24(也就是8*3)而不是4。这是因为上述过程忽略了运算符的优先级。像这样从左到右依次获取操作数和运算符的方法是行不通的，因为代数学规定乘法运算必须先于减法运算完成。也许有些初学者认为解决这个问题很容易，而且实际上在某些有限的条件下确实如此。但是当表达式中增加了圆括号、求幂运算、变量、一元运算符等元素之后，问题只会变得更为复杂。尽管编写处理表达式的代码有很多种方式，但是本章介绍的一种最容易由个人开发完成，称之为递归向下的解析器。在阅读本章的过程中，读者会明白这样命名的原因(其他一些解析器的编写方法使

7、用了一些复杂的表格，这些表格通常由另一些计算机程序生成。这些解析器有时也称为表格驱动(table-driven)的解析器)。2.3表达式的解析解析和计算表达式的方式有很多种。在使用递归下降的解析器时，表达式被视为递归的数据结构——表达式由其本身来定义。假定表达式只能使用+、-、*、/和圆括号，那么所有的表达式可以用下面的规则来定义：表达式à项[+项][–项]项à因数[*因数][/因数]因数à变量、数字或者(表达式)37第2章递归下降的表达式解析器方括号里面表示可选元素，而箭头à表