乐趣区

关于javascript:算符优先算法

jiezi

通常，操作符的优先级越高，地位就越低。例如在 3 +4 5 这个表达式中，* 的优先级高于 +, 那么 就是 + 节点的子节点。但如果 3 + 4 增加了()，即：(3+4)*5，两个符号的优先级就颠倒回来。

如果咱们用 nearyley（一种应用类 BNF 语法表白的 parser 生成器）表白，就有如下代码，能够看到每一种不同优先级的运算符，对应了一条语法规定。当不同优先级的运算符减少，咱们要写的语法规定也会相应减少：

expression -> additive {% d => d[0] %}
additive -> 
          additive "+" multiple {% d => d[0] + d[2] %}
        | additive "-" multiple {% d => d[0] - d[2] %}
        | multiple {% d => d[0] %}
multiple -> 
          multiple "*" factor {% d => d[0] * d[2] %}
        | multiple "/" factor {% d => d[0] / d[2] %}
        | factor {% d => d[0] %}

factor -> "(" additive ")" {% d => d[1] %}
        | %number {% d => Number(d[0]) %}

这样新增一个运算符，就会给咱们的 parser 实现带来肯定的老本，那么有没有一种通用的形式解决咱们的运算符优先级呢？算符优先算法就是为了这个目标而生的。

上面是算符优先算法的代码，为了不便学习，这里咱们 lexer 和 parser，写的尽可能的简略，所以咱们的 parser 不容许符号之间有空格，且只反对解析个位数数(即反对 3 +4，不反对 33+4)：

class BinaryExpr{constructor(left, op, right){
    this.left = left
    this.op = op
    this.right = right
  }
}

class OpPrecedenceParser{constructor(lexer, precedenceMap){
    this.lexer = lexer
    this.precedenceMap = precedenceMap
  }
  expression(){let right = this.factor()
    let next;
    while(next = this.nextOperator()){right = this.doShift(right)
    }
    return right
  }
  
  doShift(left){const op = this.lexer.read()
    let right = this.factor()
    let next;
    while((next = this.nextOperator()) && this.rightIsExpr(op, next)){right = this.doShift(right)
    }
    return new BinaryExpr(left, op, right)
  }
  nextOperator(){const op = this.lexer.nextToken()
    if(this.precedenceMap.get(op)) return op
    return null
  }
  factor(){if(this.lexer.nextToken() === "("){this.token()
      const exp = this.expression()
      this.token()
      return exp
    } else {return this.lexer.read()
    }
  }
  token(){return this.lexer.read()
  }
  rightIsExpr(op1, op2){return this.precedenceMap.get(op1) < this.precedenceMap.get(op2)
  }
}

class Lexer{constructor(content){
    this.currentIndex = 0
    this.content = content || ""
    this.tokens = []}
  peek(index){return this.content[this.currentIndex + index]
  }
  nextToken(){if(this.content[this.currentIndex])
    return this.peek(0)
  }
  read(){return this.content[this.currentIndex++]
  }
}

function parse(expr){const precedenceMap = new Map()
  precedenceMap.set("+", 2)
  precedenceMap.set("-", 2)
  precedenceMap.set("*", 3)
  precedenceMap.set("/", 3)  
  const lexer = new Lexer(expr)
  const parser = new OpPrecedenceParser(lexer, precedenceMap)
  const tree = parser.expression()
  return tree
  console.log(ast)
}
const ast = parse("3+4*5")
console.log(ast)

上述代码的打印后果是：

BinaryExpr {
  left: '3',
  op: '+',
  right: BinaryExpr {left: '4', op: '*', right: '5'}
}

咱们扭转一下入参为：(3+4)*5，打印后果为：

BinaryExpr {left: BinaryExpr { left: '3', op: '+', right: '4'},
  op: '*',
  right: '5'
}

能够看到后果是合乎咱们预期的，优先级低的操作符更凑近根节点。那如果咱们须要减少新的符号呢？只需这样做:

precedenceMap.set("<", 1)
precedenceMap.set(">", 1)

当咱们执行 parse(3+4>5) 时，失去的后果为：

BinaryExpr {left: BinaryExpr { left: '3', op: '+', right: '4'},
  op: '>',
  right: '5'
}

当初咱们领略了算符优先算法的弱小，减少符号只须要往规定 map 外面减少规定及优先级即可。让咱们剖析一下算符优先算法。OpPrecedenceParser 中 expression 和 factor 办法比拟容易了解，只是依据咱们的文法做自顶向下的匹配。外围在于 doShift 函数：

  doShift(left){const op = this.lexer.read()
    let right = this.factor()
    let next;
    while((next = this.nextOperator()) && this.rightIsExpr(op, next)){right = this.doShift(right)
    }
    return new BinaryExpr(left, op, right)
  }

假如有 NUMBER1+NUMBER2*NUMBER3 这样的表达式，doshift 函数向后读取，拿到符号 ，而后将 + 和 进行比拟，如果后面的符号优先级更高，则结构出 Expr，并返回。如果前面的符号优先级更高，则对右侧的表达式做 doShift。

能够看出，算符优先算法对于 parse 表达式，真的是一件利器，当咱们应用 LL 算法做 parser 时，无妨在表达式解析上，应用算符优先算法。

参考：

  • 《编程语言实现模式》
  • 《两周自制脚本语言》
退出移动版