编译原理入门课:(二)递归解析中怎么处理运算符优先级

栏目: 服务器 · 编程工具 · 发布时间: 4年前

内容简介:今天要给我们的“计算器”加上乘、除和取模三种运算,并且加上对括号的优先级处理。如果不是采用递归方式解析表达式的话,可以参考下用递归方式解析的话,只要深刻理解了上一章的知识,这一章的都是小意思,那么我们开始。

今天要给我们的“计算器”加上乘、除和取模三种运算,并且加上对括号的优先级处理。

如果不是采用递归方式解析表达式的话,可以参考下 调度场算法 ,这是一个利用队列和堆栈来解决计算优先级的经典算法。

用递归方式解析的话,只要深刻理解了上一章的知识,这一章的都是小意思,那么我们开始。

产生式的优先级

首先我们列出乘除法的文法:

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型词法和函数调用语法

(六)用函数表来优化函数解析的逻辑


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

现代前端技术解析

现代前端技术解析

张成文 / 电子工业出版社 / 2017-4-1 / 79.00元

这是一本以现代前端技术思想与理论为主要内容的书。前端技术发展迅速,涉及的技术点很多,我们往往需要阅读很多书籍才能理解前端技术的知识体系。《现代前端技术解析》在前端知识体系上做了很好的总结和梳理,涵盖了现代前端技术绝大部分的知识内容,起到一个启蒙作用,能帮助读者快速把握前端技术的整个脉络,培养更完善的体系化思维,掌握更多灵活的前端代码架构方法,使读者获得成为高级前端工程师或架构师所必须具备的思维和能......一起来看看 《现代前端技术解析》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试