使用普拉特分析法解析极为复杂的算术表达式

2023-10-10 20:10

本文主要是介绍使用普拉特分析法解析极为复杂的算术表达式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

!3*-5+(add(6,7)/foobar);

上面是一个很复杂的表达式,它的解析涉及到操作符优先级,例如乘法比加法优先级高,但括号优先级又比乘法优先级高,于此同时,在解析时,编译器需要把-和5结合解读成”-5”后才能参与运算,并且编译器要知道,add(6,7)是一个函数调用,它需要执行add(6,7),获得函数运行后返回值才能继续参与算术表达式的运算。

算术表达式解析时要考虑的因素之多,使得它成为了编译原理中有关语法解析这部分的重点和难点,理解了算术表达式的解析算法,不但能执编译原理牛耳,而且解析算法的设计和实现充分展示了计算机科学中“分而治之”和“递归”的精妙核心原则。

编译原理一大难点在于,它蕴含很多抽象的概念,而很多复杂算法的设计和实现有赖于对这些抽象概念的理解和把握,一方面概念的抽象性已经让人头大,再加上算法的复杂性,这就使得编译原理难上加难,让人望而却步。好在普拉特解析法有别与传统的编译原理语法解析算法,它简单,精致,易理解,我们看看普拉特解析法是如何巧妙的解决上面复杂算术表达式的解析的。

前序表达式的解析

在上面复杂的算术表达式中,有这样的组成部分:
!3 和 -5
这种成分的特点是,有一个操作符放在数字的前面,在运算整个算术式子时,需要先执行上面这些运算后,所得结果才能参与到整个算术式的运算中,我们把这种算术式成为前序表达式。我们看看普拉特解析法是如何解析上面的式子的,原理我们先不分析,先直接从代码实现开始。在MonkeyCompilerParser.js中,添加下面代码:

class PrefixExpression extends Expression {constructor(props) {super(props)this.token = props.tokenthis.operator = props.operatorthis.right = props.expressionvar s = "(" + this.operator + this.right.getLiteral() + " )"this.tokenLiteral = s}
}

上面代码定义的类就用来表示前序表达式,其中的operator就是表达式中的操作符,this.right对应的就是操作符后面的成分。接着我们在解析表中增加对前序表达式的解析函数:

class MonkeyCompilerParser {constructor(lexer) {....this.prefixParseFns[this.lexer.BANG_SIGN] = this.parsePrefixExpressionthis.prefixParseFns[this.lexer.MINUS_SIGN] =this.parsePrefixExpression....}....    
}

this.lexer.BANG_SIGN 对应的就是表达式中的符号”!”,它表示做取反操作,this.lexer.MINUS_SIGN 对应表达式中的”-“,它表示做取负操作。上面代码表示,一旦语法解析器解析到符号”!”和”-“时,解析器便调用parsePrefixExpression函数进行处理,我们看看它的实现:

parsePrefixExpression(caller) {var props = {}props.token = caller.curTokenprops.operator = caller.curToken.getLiteral()caller.nextToken()props.expression = caller.parseExpression(caller.PREFIX)return new PrefixExpression(props)}

解析函数在执行时,先记录前序操作符,也就是caller.curToken,这个变量对应的token其实就是符号”!”或者”-“。然后调用nextToken()把读取下一个token,在前序操作符后面跟着的是一个算术表达式,所以直接调用parseExpression进行解析就可以,当前我们把算术表达式简化为数字字符串或变量字符串,所以现在我们的解析器只支持”!”或”-“后面跟着一个数组或变量。

在这里我们需要注意到一个定义上的循环重复。前序表达式是算术表达式的一部分,也就是后者包含了前者。然后前序表达式在去掉前序操作符后,接着的确是一个算术表达式,也就是说前序表达式包含了算术表达式,这就形成一个概念定义上的反复包含,我包含你与此同时你又包含我,这种成分的互相包含性是编译原理理解起来的难点所在。

上面代码完成后,我们在编辑框中输入前序表达式进行解析:
这里写图片描述

点击下方的parsing按钮后,在控制台里可以看到解析结果:

这里写图片描述

于是,添加上面代码后,语法解析去就能接受并理解前序表达式。

中序表达式

前序表达式的操作符在操作数的前面,对应的中序表达式意味着操作符在操作数的中间,例如:

3+52*3;
3*!foobar
4+5*6

上面的式子中,操作符两边各有一个操作数,第三个表达式,操作符”*”右边甚至还包含了一个前序表达式。在解析中序表达式时,还得注意运算符的优先级,例如第4个表达式需要先做乘法再做加法,也就是说后半部分”5*6”需要当做一个整体看待。

我们先在代码中定义符号的优先级和配置中序表达式的解析函数表:

class MonkeyCompilerParser {constructor(lexer) {...this.initPrecedencesMap()this.registerInfixMap()}initPrecedencesMap() {this.precedencesMap = {}this.precedencesMap[this.lexer.EQ] = this.EQUALSthis.precedencesMap[this.lexer.NOT_EQ] = this.EQUALSthis.precedencesMap[this.lexer.LT] = this.LESSGREATERthis.precedencesMap[this.lexer.GT] = this.LESSGREATERthis.precedencesMap[this.lexer.PLUS_SIGN] = this.SUMthis.precedencesMap[this.lexer.MINUS_SIGN] = this.SUMthis.precedencesMap[this.lexer.SLASH] = this.PRODUCTthis.precedencesMap[this.lexer.ASTERISK] = this.PRODUCTthis.precedencesMap[this.lexer.LEFT_PARENT] = this.CALL}
peekPrecedence() {var p = this.precedencesMap[this.peekToken.getType()]if (p != undefined) {return p}return this.LOWEST}curPrecedence() {var p = this.precedencesMap[this.curToken.getType()]if (p != undefined) {return p}return this.LOWEST}registerInfixMap() {this.infixParseFns = {}this.infixParseFns[this.lexer.PLUS_SIGN] = this.parseInfixExpressionthis.infixParseFns[this.lexer.MINUS_SIGN] = this.parseInfixExpressionthis.infixParseFns[this.lexer.SLASH] = this.parseInfixExpressionthis.infixParseFns[this.lexer.ASTERISK] = this.parseInfixExpressionthis.infixParseFns[this.lexer.EQ] = this.parseInfixExpressionthis.infixParseFns[this.lexer.NOT_EQ] = this.parseInfixExpressionthis.infixParseFns[this.lexer.LT] = this.parseInfixExpressionthis.infixParseFns[this.lexer.GT] = this.parseInfixExpression}

函数initPrecedenceMap用来把操作符的优先级设置到一个哈希表中,当解析器读取到不同的操作符时,它就根据当前读到的操作符到表里面查找对应的优先级,根据不同优先级采取不同操作。像前序分析一样,在解析中序表达式时,我们也配置一个解析调用表,当解读到中序操作符时,例如读取到符号“*, + , -, !=, <, >”时,解析器拿着这些符号到解析表infixParseFns去获取一个解析函数,然后直接执行。我们再看看这个函数的实现:

parseInfixExpression(caller, left) {var props = {}props.leftExpression = leftprops.token = caller.curTokenprops.operator = caller.curToken.getLiteral()var precedence = caller.curPrecedence()caller.nextToken()props.rightExpression = caller.parseExpression(precedence)return new InfixExpression(props)}

上面的函数调用时,需要传入一个参数叫left,可以猜测,这个left就是操作符左边部分,而right对应的就是右边部分,对于表达式”2+3”,上面代码中的leftExpression对应的就是表达式”2”,代码中的rightExpression对应加号后面的表达式”3”。

接着我们看看解析流程的改变:

parseExpression(precedence) {var prefix = this.prefixParseFns[this.curToken.getType()]if (prefix === null) {console.log("no parsing function found for token " + this.curToken.getLiteral())return null}var leftExp = prefix(this)if (this.peekTokenIs(this.lexer.SEMICOLON) != true &&precedence < this.peekPrecedence()) {var infix = this.infixParseFns[this.peekToken.getType()]if (infix === null) {return leftExp}this.nextToken()leftExp = infix(this, leftExp)}return leftExp}

parseExpression被调用来解析解析表达式时,它先从前序解析表中,用当前读取的token查找一个解析函数来解析表达式的前半部分,此时符号的优先级开始发挥作用,例如表达式”4+5*6”,在解析时,”4”会先解析,解析后对应的就是leftExp,由于4后面跟着+而不是分号,因此会进入if部分,此时当前的token对应的就是符号”+”,于是在中序解析表中,用符号”+”找到一个解析函数,也就是函数parseInfixExpression,然后执行它,并且把加号左边的表达式”4”当做参数传入,在parseInfixExpression中,它先在符号优先级表中查找加号的优先级,并把优先级当做参数,再次调用parseExpression来解析加号后面的表达式。

在执行parseExpression时,它会把乘号左边的5解析成一个表达式,也就对应变量leftExp。此时5后面跟着的不是分号而是乘号,代码调用peekPrecedence()在操作符优先级表中查找乘号的优先级,然后跟传进来的加号优先级比较,乘号的优先级肯定比加号优先级大,于是进入if部分,接着从中序表达式解析表中找到解析函数parseInfixExpression,执行它后,把乘号后面的数字6解析成一个表达式。注意到,此时代码在调用parseInfixExpression时,把leftExp当做参数传入,而leftExp对应的是表达式5,于是表达式”5”加上符号”*”以及表达式”6”就被结合成一个整体,这就跟算术法则保持一致,也就是解析器会先处理”5*6”,再把所得结果与前面的表达式”4”做加法运算。

当完成上面代码后,在编辑框中输入以下内容:

这里写图片描述

点击解析后,在控制台中输出结果如下:

这里写图片描述

我们看到,在解析结果中,”5*6”确实是组合成一个整体来被解读的。本文只讲解了代码的设计和运行逻辑,他们的理解需要结合调试演示才好深入理解,请点击下面的链接观看讲解视频:

更详细的讲解和代码调试演示过程,请点击链接

下一节我们将深入探讨普拉特解析法的算法原理,并证明为什么普拉特解析法是行之有效的语法解析算法。

更多技术信息,包括操作系统,编译器,面试算法,机器学习,人工智能,请关照我的公众号:
这里写图片描述

这篇关于使用普拉特分析法解析极为复杂的算术表达式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/182798

相关文章

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

Python验证码识别方式(使用pytesseract库)

《Python验证码识别方式(使用pytesseract库)》:本文主要介绍Python验证码识别方式(使用pytesseract库),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全... 目录1、安装Tesseract-OCR2、在python中使用3、本地图片识别4、结合playwrigh

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

使用vscode搭建pywebview集成vue项目实践

《使用vscode搭建pywebview集成vue项目实践》:本文主要介绍使用vscode搭建pywebview集成vue项目实践,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录环境准备项目源码下载项目说明调试与生成可执行文件核心代码说明总结本节我们使用pythonpywebv

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》:本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

SpringCloud中的@FeignClient注解使用详解

《SpringCloud中的@FeignClient注解使用详解》在SpringCloud中使用Feign进行服务间的调用时,通常会使用@FeignClient注解来标记Feign客户端接口,这篇文章... 在Spring Cloud中使用Feign进行服务间的调用时,通常会使用@FeignClient注解