用递归下降分析编写一个用于判断数学表达式是否正确的语法分析.doc

使用递归下降算法分析数学表达式 安全编程 2011-01-07 23:43:50 阅读27 评论0 字号：大中小 订阅 国内很多编译原理的教材都过于重视理论学习而缺少实践上的指导。本来想通过介绍一个经典的算法问题--数学表达式问题，来举例说明编译原理中一种文法分析算法的实践。在我们学习的编译原理中有个专题叫做语法分析（文法分析）。文法分析就是以一种固定的文法格式来解析形式语言。在我们的编译原理的教材中都必定包含两种文法分析的算法，一个是LL算法，另外一个就是LR算法。LL算法也叫自顶向下的分析算法，相对简单，适合于手工编码，而LR算法是自底向上的分析算法，很复杂，一般我们都通过使用工具yacc来生成其相关代码。本文以LL（1）算法中最简单的一种形式递归下降算法来分析常规算法问题中的数学表达式问题。同时，本文也介绍手工构造EBNF文法的分析器代码普遍方法。希望本文的实践能对大家实现自己的语法分析器带来帮助。 数学表达式问题 在学习算法的时候，四则混合运算的表达式处理是个很经典的算法问题。比如这里有个数学表达式“122＋2＊（11-1）／（3-（2-0））”。我们需要根据这个字符串的描述计算出其结果。Input:122 + 2 * (11-1) /( 3-(2-0) )Output:142 四则混合运算中还需要考虑到括号、乘除号与加减号的优先运算问题，通常的解决办法就是使用堆栈。这种常规的算法和LL算法有异曲同工之处，两种算法其实是一样的。 传统数学表达式处理算法简介 这个传统算法其实不知不觉地使用LL（1）算法的精髓。它就是主要依靠栈式的数据结构分别保存数和符号，然后根据运算符号的优先级别进行数学计算，并将结果保存在栈里面。传统算法中使用了两个栈。一个是保存数值，暂时就叫值栈。另一个是保存符号的，叫符号栈。我们规定一个记号＃，来表示栈底。下面我们就来看看如何计算一个简单的表达式：11+2-8*(5-3) 符号栈和值栈的变化是根据输入串来进行的，基本上栈的操作可以简单用下面几句话来说。Start：1．　如果当前输入串中得到的是数字，则直接压入值栈，然后转到Start。2．　如果当前输入串中得到的是符号，那么对符号进行判断：1）如果符号是＇＋＇或者＇-＇，则依次弹出符号栈的符号，计算栈中数值，直到弹出的符号不是＊，／，＋，-；2）如果符号是＇＊＇或者＇／＇，则压入符号栈；3）如果符号是＇（＇，则直接压＇（＇入符号栈；4）如果符号是＇）＇，则依照符号栈的顺序弹出符号，计算栈中数值，把结果压入值栈，直到符号栈顶是＇（＇，最后再弹出＇（＇　。最后转到Start。3．　如果当前输入串得到的是EOF（字符串结束符号），则计算栈中数值，知道符号栈没有符号。 语法分析数学表达式 或者可能你以前运用过自己的办法来解决过这个程序问题，不过下面我们将通过编译原理建立的一套文法分析理论，来十分精彩地解决这个算法问题。首先是建立数学表达式的文法EBNF。EBNF文法可以更灵活地表示BNF，是BNF范式文法的一种扩展。下面是计算表达式的文法。 Expression - Term { Addop Term }Addop - + | -Term - Factor { Mulop Factor }Mulop - * | /Factor - ID | NUM | ( Expression ) 我们来看看如何根据这个EBNF文法实现一个递归下降的分析程序。大致上来说要分那么几步来实现。（注意：下面的几个步骤不光是针对本节的数学表达式问题，而是包含所有通常的递归下降文法分析器的实现） 语法分析实现 1．Step　建立词法分析 因为词法分析是语法分析的前提，那么我们在实现递归下降算法的时候，同样应该把词法分析的实现考虑进去。本文要处理只是个数学表达式的问题，那么通过上面的文法，可以看到需要识别的词法无非就是2个ID，NUM和4个运算符号‘＋＇、‘-’、＇＊＇、‘／＇以及2个括号‘（’、‘）’。本文没有对词法分析的自动机原理进行讲解，这部分内容应该在编译原理中讲得比较透彻。所谓自动机，就是按一定步骤识别每个字符的算法。可以用下面的几个图来表示ID和NUM的识别自动机（识别步骤或算法）基本算法就是，如果输入的字符是digit（＇0＇-＇9＇），那么进入check循环，如果输入还是digit，那么再跳回循环查看，如果输入是 other（不是 ＇0＇-＇9＇），那么就直接accept，接收这个串为NUM类型的TOKEN。同NUM一样，当输入的是letter，那么进入ID的有限自动机。只是在进入check循环后，有两种可能都继续留在循环，那就是digit和letter（＇a＇-＇Z＇）。当输入既不是digit，也不是 le