专栏首页Coding迪斯尼使用普拉特分析法解析极为复杂的算术表达式

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

!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.token
    this.operator = props.operator
    this.right = props.expression
    var s = "(" + this.operator + this.right.getLiteral() + " )"
    this.tokenLiteral = s
  }
}

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

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

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

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

      return new PrefixExpression(props)
    }

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

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

上面代码完成后,我们在编辑框中输入前序表达式进行解析:

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

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

中序表达式

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

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

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

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

class MonkeyCompilerParser {
    constructor(lexer) {
    ...
    this.initPrecedencesMap()
    this.registerInfixMap()
    }

   initPrecedencesMap() {
      this.precedencesMap = {}
      this.precedencesMap[this.lexer.EQ] = this.EQUALS
      this.precedencesMap[this.lexer.NOT_EQ] = this.EQUALS
      this.precedencesMap[this.lexer.LT] = this.LESSGREATER
      this.precedencesMap[this.lexer.GT] = this.LESSGREATER
      this.precedencesMap[this.lexer.PLUS_SIGN] = this.SUM
      this.precedencesMap[this.lexer.MINUS_SIGN] = this.SUM
      this.precedencesMap[this.lexer.SLASH] = this.PRODUCT
      this.precedencesMap[this.lexer.ASTERISK] = this.PRODUCT
      this.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.parseInfixExpression
      this.infixParseFns[this.lexer.MINUS_SIGN] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.SLASH] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.ASTERISK] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.EQ] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.NOT_EQ] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.LT] = 
      this.parseInfixExpression
      this.infixParseFns[this.lexer.GT] = 
      this.parseInfixExpression
    }

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

parseInfixExpression(caller, left) {
      var props = {}
      props.leftExpression = left
      props.token = caller.curToken
      props.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”就被结合成一个整体,这就跟算术法则保持一致,也就是解析器会先处理”56”,再把所得结果与前面的表达式”4”做加法运算。

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

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

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

本文分享自微信公众号 - Coding迪斯尼(gh_c9f933e7765d),作者:陈屹

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 寿司开卖:实现寿司制作特效和音响特效

    本节我们将继续上一节完成若干个小功能。首先要完成的是,当客户动画在主页面出现时,它左上角会冒泡,显示它想购买何种寿司,此时玩家可以点击左下角面板中各种元素,组合...

    望月从良
  • 实现小球在弹射前的拉伸特效和动态障碍物特效

    当前我们实现小球弹射时,会先用鼠标点击小球,然后移动鼠标,当松开鼠标时,小球会弹射向鼠标松开的位置。我们按住小球的时间越长,小球弹射的力度就越大,但有一个问题是...

    望月从良
  • 利用web work实现多线程异步机制,打造页面单步调试IDE

    我们已经完成了整个编译器的开发,现在我们做一个能够单步调试的页面IDE,完成本章代码后,我们可以实现下面如图所示功能:

    望月从良
  • jQuery开发技巧

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    奋飛
  • 浅谈前端响应式设计(一)

    现实世界有很多是以响应式的方式运作的,例如我们会在收到他人的提问,然后做出响应,给出相应的回答。在开发过程中我也应用了大量的响应式设计,积累了一些经验,希望能抛...

    有赞coder
  • vue项目使用 富文本 封装

    我又来了,今天给大家分享一个富文本框的封装,写后台管理也离不开富文本框,我就做了封装,供大家参考,

    前端小白@阿强
  • element表单校验问题

    新增时,校验为空未通过,点击取消按钮。重新打开编辑,明明有值,显示校验未通过。

    崔笑颜
  • 基础篇章:关于 React Native 之 Modal 组件的讲解

    (友情提示:RN学习,从最基础的开始,大家不要嫌弃太基础,会的同学请自行略过,希望不要耽误已经会的同学的宝贵时间) Modal是模态视图,它的作用是可以用来覆盖...

    非著名程序员
  • TypeScript 函数中的 this 参数

    从 TypeScript 2.0 开始,在函数和方法中我们可以声明 this 的类型,实际使用起来也很简单,比如:

    阿宝哥
  • 如何理解JavaScript中的this

    JavaScript中的 this 对于初学者来说是个难点,对于老手也会困惑。之前有一个小伙伴一直问我this的相关问题,所以今天抽出点时间深入的带大家理解th...

    ZEHAN

扫码关注云+社区

领取腾讯云代金券