认识

前言

本文介绍四则运算表达式编译解析的过程

9-1-1+2+4*8/2/2+4*(2-1) 编译、解析、运算 的过程如下:

1. 9-1-1+2+4*8/2/2+4*(2-1)分词

2. 基于分词,生成抽象语法树

3. 基于抽象语法树,获取计算结果

理论

---

一、优先级 Priority

• 不同的运算符之间是有运算规则的

• 加减的优先级一样,乘除的优先级一样

二、结合性 Associativity

• 同样优先级的运算符是从左到右计算还是从右往左计算叫做结合性

• 加减乘除等算术运算符是左结合的

• 结合性是跟左递归还是跟有递归有关的。左递归导致左结合,右递归导致右结合

三、文法规则

• 优先级是通过在语法推导中的层次来决定的,优先级越低的,越先尝试推导

• 通过文法的嵌套,实现对运算符优先级的支持

算法

---

进行四则运算时,根据运算结合性,我们通常是从左往右依次计算,如下所示:

• 语法规则: add: add | add + number

• 代码实现:

  function additive(){
      additive();
      number();
  }

但是,根据add: add | add + number从左往右计算会在代码实现的过程中没有结束条件,造成无限递归的情况,这种情况称为左递归,那么我们通过如下方式解决:

• 语法规则: add: number | number + add

• 代码实现:

  function additive(){
      number();
      additive();
  }

但是,add: number | number + add这种逻辑失去了结合性,导致运算结果错误。所以我们根据巴克范式对add: number | number + add再度改进:

• 语法规则: add: number (+ number)*

总结: 四则运算过程中,如果使用add: add | add + number左递归的形式,会出现无限循环;如果使用add: number | number + add右递归的形式,会出现结合性失效的问题,导致运算结果错误; 所以我们最终采用将左递归改为循环来实现四则运算