内容简介:今天要给我们的“计算器”加上乘、除和取模三种运算,并且加上对括号的优先级处理。如果不是采用递归方式解析表达式的话,可以参考下用递归方式解析的话,只要深刻理解了上一章的知识,这一章的都是小意思,那么我们开始。
今天要给我们的“计算器”加上乘、除和取模三种运算,并且加上对括号的优先级处理。
如果不是采用递归方式解析表达式的话,可以参考下 调度场算法 ,这是一个利用队列和堆栈来解决计算优先级的经典算法。
用递归方式解析的话,只要深刻理解了上一章的知识,这一章的都是小意思,那么我们开始。
产生式的优先级
首先我们列出乘除法的文法:
term -> term '*' num | term '/' num | num num -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
这里的 term
是项的意思,是指在加减法里运算符左右的两个项,先不要纠结具体是什么意思,一会就会用到了。
我们以几个例子来人肉分析一下,这个文法和加减法的文法怎么结合,才能获得正确的优先级:
expr(1+2*3) = num(1) '+' term(2*3) expr(1*2+3) = term(1*2) '+' num(3) expr(1*2+3*4) = term(1*2) '+' term(3*4)
而在上面乘除法的文法里可以看到,实际上 term
是可以推导为 num
的,所以上述例子又可以变成:
expr(1+2*3) = term(1) '+' term(2*3) expr(1*2+3) = term(1*2) '+' term(3) expr(1*2+3*4) = term(1*2) '+' term(3*4)
是不是写到这里就豁然开朗了,如果乘除法的优先级更高,则让乘除法的解析先进行,乘除法的结果当做加减法的项就可以了。在文法里的表现就是,优先级越高的产生式会越靠后,结果是这样:
expr -> expr '+' term | expr '-' term | term term -> term '*' num | term '/' num | num num -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
具体的验证大家自己试试就可以了,绝对可以按照正确的优先级进行解析。
前一章代码的隐患
文法已经准备好了,本来可以开始写递归逻辑了,但是我们得先解决前一章代码的隐患。先看看之前的代码:
int expr(const char *expStr) { 解析number,读取expStr下一个字符 while(expStr是加减号) { 解析加减号,读取expStr下一个字符 解析number,读取expStr下一个字符 } }
看上去逻辑是没什么问题的,但是这是因为 number
肯定是单个字符的,如果按照之前的代码继续实现本章的文法,就会得到这样的难题:
int expr(const char *expStr) { 解析term,该读取expStr后的第几个字符? while(expStr是加减号) { 解析加减号,读取expStr下一个字符 解析term,该读取expStr后的第几个字符? } }
所以将字符串指针后移的操作,应该交给解析了字符或者说消化掉字符的角色来做,那么我们要用指针的指针来先改进一下上一章的代码:
int number(const char **expStr) { int result = **expStr - '0'; (*expStr)++; return result; } int expr(const char **expStr) { int result = number(expStr); while (**expStr == '+' || **expStr == '-') { char op = **expStr; (*expStr)++; if (op == '+') { result += number(expStr); } else { result -= number(expStr); } } return result; }
实现乘除法和取余
大家有了文法,也掌握了消除左递归的方法,还知道怎么转换成递归代码,我感觉其实都不太需要把代码给大家贴出来了。:joy:
乘除法的实现思路和上一章加减法的思路完全一致,我们顺带把取余也加上就好了:
int term(const char **expStr) { int result = number(expStr); while (**expStr == '*' || **expStr == '/' || **expStr == '%') { char op = **expStr; (*expStr)++; if (op == '*') { result *= number(expStr); } else if (op == '/') { result /= number(expStr); } else { result %= number(expStr); } } return result; }
下一步就是把加减法里的 number
解析都换成 term
解析,换完之后的 expr
函数会长这样:
int expr(const char **expStr) { int result = term(expStr); while (**expStr == '+' || **expStr == '-') { char op = **expStr; (*expStr)++; if (op == '+') { result += term(expStr); } else { result -= term(expStr); } } return result; }
实验下,确认我们的表达式解析器可以按照正确的优先级计算加减乘除了。
加入括号的处理
括号的运算优先级是比乘除法还要高的,所以我们新增一个非终结符 factor
(因子),用来在文法中描述它:
expr -> expr '+' term | expr '-' term | term term -> term '*' factor | term '/' factor | factor factor -> number | '(' expr ')' number -> '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
嘿嘿,这次就真的不给大家贴代码了,相信这次大家应该可以熟练的搞定代码,毕竟已经是个成熟的程序猿了。
完整的代码存放在 SlimeExpressionC ,需要的同学可以自取,今天的入门课就到这里。
其它章节
(二)递归解析中怎么处理运算符优先级
(三)简单错误处理逻辑以及负数的解析
(四)用词法解析处理多位数字和空白符
(五)解析ID型词法和函数调用语法
(六)用函数表来优化函数解析的逻辑
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- JavaScript阴沟里翻船之运算符优先级
- C/C++三元运算符实际上是否具有与赋值运算符相同的优先级?
- 如何确定需求的优先级?
- RabbitMQ之优先级消息队列
- [译]HTTP/2的优先级
- Thymeleaf 模板布局和属性优先级
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
移动Web前端高效开发实战
iKcamp / 电子工业出版社 / 2017-9 / 89.00
移动互联网的兴起和快速普及,给前端开发人员带来了前所未有的新机遇。移动Web前端技术作为整个技术链条中重要的一环,却乱象丛生。《移动Web前端高效开发实战:HTML 5 + CSS 3 + JavaScript + Webpack + React Native + Vue.js + Node.js》是一本梳理移动前端和Native客户端技术体系的入门实战书。 《移动Web前端高效开发实战:HTML......一起来看看 《移动Web前端高效开发实战》 这本书的介绍吧!