重新定义加法

众所周知，js做算术运算是不精确的，0.1 + 0.2并不等于0.3。

0.1 + 0.2
因为公司业务的原因，我们常需要将宝石的价格、重量和尺寸进行单位换算。由于js的算术运算不精确，常导致计算后产生.99999这样的数。为了解决这个问题，我们引入了一个第三方库number-precision。number-precision是个小的库。它的主要思想是将小数转换为整数后再计算。因为我们业务中只用到四则运算，且数字都不会很大，用这个库足以覆盖所有场景，所以我选择了它。number-precision主要代码如下：

/**
 * @desc 解决浮动运算问题，避免小数点后产生多位数和计算精度损失。
 * 问题示例：2.3 + 2.4 = 4.699999999999999
 *         1.0 - 0.9 = 0.09999999999999998
 *         0.3 * 3 = 0.8999999999999999
 *         0.3 / 0.1 = 2.9999999999999996
 */

/**
 * 把错误的数据转正
 * strip(0.09999999999999998)=0.1
 */
function strip(num, precision) {
  return +parseFloat(num.toPrecision(precision || 12))
}

/**
 * 把小数放大成整数
 * @param {*number} num 输入数
 */
function float2Fixed(num) {
  return Number(num.toString().replace('.', ''))
}

/**
 * Return digits length of a number
 * @param {*number} num Input number
 */
function digitLength(num) {
  const decimal = num.toString().split('.')[1] || ''
  return decimal.length
}

/**
 * 精确乘法
 */
function multiply(num1, num2) {
  const num1Changed = float2Fixed(num1)
  const num2Changed = float2Fixed(num2)
  const baseNum = digitLength(num1) + digitLength(num2)
  const leftValue = num1Changed * num2Changed

  return leftValue / Math.pow(10, baseNum)
}

/**
 * 精确加法
 */
function plus(num1, num2) {
  const baseNum = Math.pow(10, Math.max(digitLength(num1), digitLength(num2)))
  return (multiply(num1, baseNum) + multiply(num2, baseNum)) / baseNum
}

/**
 * 精确减法
 */
function minus(num1, num2) {
  const baseNum = Math.pow(10, Math.max(digitLength(num1), digitLength(num2)))
  return (multiply(num1, baseNum) - multiply(num2, baseNum)) / baseNum
}

/**
 * 精确除法
 */
function divide(num1, num2) {
  const num1Changed = float2Fixed(num1)
  const num2Changed = float2Fixed(num2)
  return multiply(
    (num1Changed / num2Changed),
    strip(Math.pow(10, digitLength(num2) - digitLength(num1)))
  )
}

number-precision重新定义了加减乘除，我们在做计算的时候需要调用这些方法，比如计算：(1+2*(3-1))/2，我们需要这么写：

const {
  plus,
  minus,
  multiply,
  divide
} = require('number-precision')

const result = divide(plus(1, multiply(2, minus(3, 1))), 2)

是不是觉得很麻烦，还要仔细检查方法调用的顺序，不小心就写错了。
如果我们在写代码的时候还是写(1+2*(3-1))/2，代码在执行的时候，它被解释成divide(plus(1, multiply(2, minus(3, 1))), 2)执行就好了。
那么，让我们做点好玩的事情，用js写一个四则运算的解释器吧，用它把+-*/解释成number-precision对应的方法执行。

词法分析

我们只需要识别8种词法单元（token）：加号、减号、乘号、除号、左括号、右括号、数字、变量，分别用字符表示为：+,-,*,/,(,),n,v。
我们使用正则来识别token，并采用最长匹配原则。
首先，定义一个Grammar类，这个类很简单，它存储了表示token的字符，和识别token的正则。

class Grammar {
  constructor(token, pattern) {
    this.token = token
    this.pattern = pattern
  }
}

我们需要识别的8种token分别定义为：

/* 数字 */
new Grammar('n', /(?:[0-9]\.|[1-9][0-9]+\.|\.[0-9]|[0-9])[0-9]*/)
/* 变量 */
new Grammar('v', /[A-z_$][A-z0-9_$]*/)
/* 加号 */
new Grammar('+', /\+/)
/* 减号 */
new Grammar('-', /-/)
/* 乘号 */
new Grammar('*', /\*/)
/* 除号 */
new Grammar('/', /\//)
/* 左括号 */
new Grammar('(', /\(/)
/* 右括号 */
new Grammar(')', /\)/)

然后写一个词法分析器，它读入字符串，输出token序列。

class LexicalAnalyzer {
  constructor(grammars) {
    this.grammars = grammars
    this.tokens = []
  }

  parse(str) {
    this.tokens.length = 0
    return this.analyze(str)
  }

  analyze(str) {
    // 忽略空白字符
    str = str.trim()
    let value = ''
    let type = ''
    for (const grammar of this.grammars) {
      const rst = grammar.pattern.exec(str)

      // 找出最长匹配
      if (rst && rst.index === 0 && rst[0].length > value.length) {
        value = rst[0]
        type = grammar.token
      }
    }

    if (!type) throw new Error(`词法错误：'${str}' 包含无法识别的字符`)

    this.tokens.push({
      type,
      value,
    })
    const nextStr = str.replace(value, '')

    if (nextStr) {
      // 通过递归，识别下一个单词
      this.analyze(nextStr)
    }

    return [...this.tokens]
  }
}

看看效果：

词法分析

语法分析

词法分析后，我们需要分析语法。
首先，我们需要给出上下文无关文法，来描述我们的语法规则：

E -> n
E -> v
E -> P
P -> (S)
S -> E
S -> E + S
S -> E - S
S -> E * S
S -> E / S

其中每一行，我们称之为一个产生式，产生式中->左边的大写字符是非终结符，上面的文法中有3个非终结符：E、P和S。非终结符可由产生式中->右边的式子推导（扩展）。产生式右边的式子由非终结符和终结符组成，终结符就是词法分析中得到的token。
S是文法的开始符号，从S开始，我们应用文法中的规则，递归展开非终结符，直到只剩下终结符为止，最终生成四则运算语法规则集合。
下面是根据规则完全展开S的方式之一：

 S
  -> E * S              // 展开`S`
  -> P * S              // 展开`E`
  -> (S) * S            // 展开`P`
  -> (E - S) * S        // 展开`S`
  -> (n - S) * S        // 展开`E`
  -> (n - E) * S        // 展开`S`
  -> (n - n) * S        // 展开`E`
  -> (n - n) * E        // 展开`S`
  -> (n - n) * n        // 展开`E`

这表明(n-n)*n在语法上有效。
也就是说，用词法分析得到的token序列，如果能通过文法推导出来，那就是有效语法。我们可以使用非确定性下推自动机（NPDA）来判断输入是否语法正确。

NPDA

状态图

如图所示，NPDA使用栈存储推导过程中的非终结符和终结符，并在4个状态间转移。图中，每个圆圈代表一个状态，箭头指示了NPDA从一个状态转移到另一个状态。引起状态转移的事件显示在表示状态转移的横线上方，状态转移时所采取的动作显示在横线下方。
为了更直观的看NPDA是如何工作，我们假设输入是0.1+0.2，经过词法分析后得到token序列n+n。下面是NPDA的一个可能执行：

状态	是否接受	栈的内容	剩余输入	动作
1	否		n+n	应用规则①，S入栈，转移到状态2
2	否	S	n+n	应用规则②，S出栈，E+S入栈
2	否	E+S	n+n	应用规则②，E出栈，n入栈
2	否	n+S	n+n	应用规则③，读取n，n出栈
2	否	+S	+n	应用规则③，读取+，+出栈
2	否	S	n	应用规则②，S出栈，E入栈
2	否	E	n	应用规则②，E出栈，n入栈
2	否	n	n	应用规则③，读取n， n出栈
2	否			应用规则④，转移到状态3
3	是

从状态图中可以看到，NPDA每次转移，要么是状态变化，要么是栈变化，所以转移实际上是从一个状态+栈到另一个状态+栈。为了方便，我们用配置表示一个状态和一个栈的组合。

const STUCK = Symbol('stuck')

class Configuration {
  constructor(state, stack) {
    this.state = state
    this.stack = stack
  }

  isStuck() {
    return this.state === STUCK
  }

  stuck() {
    this.state = STUCK
    return this
  }
}

配置中的栈，我们也定义一个类，方便操作：

class Stack {
  constructor(...items) {
    this.items = items
  }

  getTop() {
    return this.items[0]
  }

  getItems() {
    return [...this.items]
  }

  pop() {
    return this.items.shift()
  }

  push(...items) {
    return this.items.unshift(...items)
  }
}

有了配置之后，我们还需要一种规则类型，来告诉NPDA，配置间应该如何转移。一条规则由当前配置、输入符号和下一个配置组成。通过NPDA的当前配置和读取的符号，我们能找到它能应用的规则，并应用规则将NPDA转移到下一个配置。规则类定义如下：

class PDARule {
  constructor(state, character, popCharacter, nextState, pushCharacters) {
    this.state = state
    this.character = character
    this.popCharacter = popCharacter
    this.nextState = nextState
    this.pushCharacters = pushCharacters
  }

  appliesTo(configuration, character) {
    return configuration.stack.getTop() === this.popCharacter &&
      configuration.state === this.state &&
      character === this.character
  }

  follow(configuration) {
    return new Configuration(this.nextState, this.nextStack(configuration))
  }

  nextStack(configuration) {
    const stack = new Stack(...configuration.stack.getItems())

    stack.pop()
    stack.push(...this.pushCharacters)

    return stack
  }
}

一个NPDA里会有很多规则，我们可以把所有规则封装到一个规则手册里。

class NPDABook {
  constructor(rules) {
    this.rules = rules
  }

  nextConfigurations(configuration, character) {
    const rules = this.findRules(configuration, character)

    return rules.map(rule => rule.follow(configuration))
  }

  findRules(configuration, character) {
    return this.rules.filter(v => v.appliesTo(configuration, character))
  }

  appliesTo(configuration, character) {
    return this.rules.some(v => v.appliesTo(configuration, character))
  }

  followFreeMoves(configurations) {
    return configurations.flatMap(configuration => {
      if (this.appliesTo(configuration, null)) {
        return this.followFreeMoves(this.nextConfigurations(configuration, null))
      }

      return configuration
    })
  }
}

NPDA读取token并使用规则手册不断转移，其中有一些规则不需要读取token，我们称这种规则为自由移动，当NPDA当前配置能应用自由移动规则时，会立即应用自由移动规则转移，之后再读取下一个token。如果NPDA读取token后发现无可用规则，则会被置为阻塞状态，终止运行。

class NPDA {
  constructor(configurations, acceptedStates, ruleBook) {
    this.acceptedStates = acceptedStates
    this.ruleBook = ruleBook
    this.configurations = ruleBook.followFreeMoves(configurations)
  }

  isAccepted() {
    return this.configurations.some(
      configuration => this.acceptedStates.some(v => v === configuration.state)
    )
  }

  readToken(token) {
    const {
      configurations,
      ruleBook,
    } = this
    const character = token.type

    this.configurations = configurations.flatMap(configuration => {
      if (ruleBook.appliesTo(configuration, character)) {
        return ruleBook.followFreeMoves(
          ruleBook.nextConfigurations(configuration, character)
        )
      }

      return configuration.stuck()
    })
  }

  readTokens(tokens) {
    for (const token of tokens) {
      this.readToken(token)
      if (this.configurations.every(v => v.isStuck())) break;
    }
  }
}

最后，把NPDA封装一下，每次语法分析实例化一个NPDA。

class NPDADesign {
  constructor(startState, bottomChar, acceptedStates, rulebook) {
    this.startState = startState
    this.bottomChar = bottomChar
    this.acceptedStates = acceptedStates
    this.rulebook = rulebook
  }

  isAccepted(tokens) {
    const npda = new NPDA(
      [new Configuration(this.startState, new Stack(this.bottomChar))],
      this.acceptedStates,
      this.rulebook
    )

    npda.readTokens(tokens)
    return npda.isAccepted()
  }
}

运行一下，看看效果：

语法分析

规约

仅仅识别一个句子是否语法正确是不够的，我们还需要将四则运算表达式最终规约成一个数。我们将借助抽象语法树（AST）帮我们完成这个任务。AST只包含有用节点：+、-、*、/、n、v。每个节点，我们需要知道它的类型、优先级和值。我们可以这样定义节点：

class Node {
  constructor(token, precedence, value) {
    this.token = token
    this.precedence = precedence
    this.value = value
  }
}

四则运算的AST比较简单，因为+、-、*、/都是二目运算符，所以我们可以用二叉树定义四则运算的AST。

const stringify = () => {
  const lines = []
  const vLine = []

  function replaceChar(str, index, char) {
    return str.substring(0, index) +
    char +
    str.substring(index + 1, str.length)
  }

  return function appendLine(tree, padding = '|—— ', prePadding = '') {
    if (!tree) return ''
    lines.push(`${padding}${tree.token}`)
    if (prePadding) {
      vLine.push([prePadding.length, '|'])
    } else {
      vLine.pop()
    }
    let leftPadding = `${new Array(padding.length + 1).join(' ')}|—— `
    let rightPadding = `${new Array(padding.length + 1).join(' ')} —— `

    vLine.forEach(([index, char]) => {
      leftPadding = replaceChar(leftPadding, index, char)
      rightPadding = replaceChar(rightPadding, index, char)
    })

    appendLine(tree.leftChild, leftPadding, padding)
    appendLine(tree.rightChild, rightPadding)
    return lines.join('\n')
  }
}

class Tree {
  constructor(root) {
    this.root = root
    this.leftChild = null
    this.rightChild = null
  }

  get precedence() {
    return this.root.precedence
  }

  get token() {
    return this.root.value
  }

  toString() {
    return stringify()(this)
  }
}

在语法分析时，我们这样构建AST：

1. 初始状态时，AST为空；
2. 读取token时，我们用这个token实例化一个节点，并用这个节点作为根节点实例化一棵新树。将新树合并到AST。

合并算法：

1. 当AST为空时，使用新树作为AST；
2. 当新树的优先级（树的优先级即其根节点优先级）大于AST优先级时，将AST的右子树替换成AST的右子树与新树合并后的树；
3. 否则，将AST作为新树的左子树，并使用新树作为新的AST。

代码如下：

function compose(oldTree, newTree) {
  if (!oldTree) return newTree

  if (newTree.precedence > oldTree.precedence) {
    oldTree.rightChild = compose(oldTree.rightChild, newTree)
    return oldTree
  }

  newTree.leftChild = oldTree
  return newTree
}

每种树定义好规约方法，最后封装如下：

class Num extends Tree {
  constructor(value, precedence) {
    super(new Node('n', 3 + precedence, value))
  }

  reduce() {
    return this.root.value
  }
}

class Variable extends Tree {
  constructor(value, precedence) {
    super(new Node('v', 3 + precedence, value))
  }

  reduce(env) {
    if (!env || !Object.prototype.hasOwnProperty.call(env, this.root.value)) {
      throw new Error(`Uncaught ReferenceError: ${this.root.value} is not defined`)
    }

    return env[this.root.value]
  }
}

class Plus extends Tree {
  constructor(value, precedence) {
    super(new Node('+', 1 + precedence, value))
  }

  reduce(env) {
    return plus(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Minus extends Tree {
  constructor(value, precedence) {
    super(new Node('-', 1 + precedence, value))
  }

  reduce(env) {
    return minus(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Multiply extends Tree {
  constructor(value, precedence) {
    super(new Node('*', 2 + precedence, value))
  }

  reduce(env) {
    return multiply(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

class Divide extends Tree {
  constructor(value, precedence) {
    super(new Node('/', 2 + precedence, value))
  }

  reduce(env) {
    return divide(this.leftChild.reduce(env), this.rightChild.reduce(env))
  }
}

function parser() {
  let tree
  let precedence = 0
  return function (token) {
    switch (token.type) {
      case '+':
        tree = compose(tree, new Plus(token.value, precedence))
        break
      case '-':
        tree = compose(tree, new Minus(token.value, precedence))
        break
      case '*':
        tree = compose(tree, new Multiply(token.value, precedence))
        break
      case '/':
        tree = compose(tree, new Divide(token.value, precedence))
        break
      case 'n':
        tree = compose(tree, new Num(token.value, precedence))
        break
      case 'v':
        tree = compose(tree, new Variable(token.value, precedence))
        break
      case '(':
        precedence += 3
        break
      case ')':
        precedence -= 3
        break
      default:
        break
    }

    return tree
  }
}

最后，把parser插入到NPDA，修改后如下：

class NPDADesign {
  constructor(startState, bottomChar, acceptedStates, rulebook, parser) {
    this.startState = startState
    this.bottomChar = bottomChar
    this.acceptedStates = acceptedStates
    this.rulebook = rulebook
    this.parser = parser
  }

  reduce(tokens, env) {
    const npda = new NPDA(
      [new Configuration(this.startState, new Stack(this.bottomChar))],
      this.acceptedStates,
      this.rulebook,
      this.parser()
    )

    npda.readTokens(tokens)

    return npda.reduce(env)
  }
}

class NPDA {
  constructor(configurations, acceptedStates, ruleBook, parser) {
    this.acceptedStates = acceptedStates
    this.ruleBook = ruleBook
    this.configurations = ruleBook.followFreeMoves(configurations)
    this.parser = parser
    this.ast = null
  }

  isAccepted() {
    return this.configurations.some(
      configuration => this.acceptedStates.some(v => v === configuration.state)
    )
  }

  readToken(token) {
    const {
      configurations,
      ruleBook,
    } = this
    const character = token.type

    if (configurations.some(configuration => ruleBook.appliesTo(configuration, character))) {
      this.ast = this.parser(token)
    }

    this.configurations = configurations.flatMap(configuration => {
      if (ruleBook.appliesTo(configuration, character)) {
        return ruleBook.followFreeMoves(
          ruleBook.nextConfigurations(configuration, character)
        )
      }

      return configuration.stuck()
    })
  }

  readTokens(tokens) {
    for (const token of tokens) {
      this.readToken(token)
      if (this.configurations.every(v => v.isStuck())) throw new Error(`语法错误：Unexpected token '${token.value}'`)
    }
  }

  reduce(env) {
    if (!this.isAccepted()) throw new Error('语法错误')
    return this.ast.reduce(env)
  }
}

完成了，看看工作得怎样：

重新定义四则运算
至此，我们完成了重新定义四则运算的工作，终于0.1+0.2=0.3了。我们甚至可以写中文做四则运算，只需要将词法分析稍改一下：

const lexicalAnalyzer = new LexicalAnalyzer([
    new Grammar('n', /(?:[0-9]\.|[1-9][0-9]+\.|\.[0-9]|[0-9])[0-9]*/),
    new Grammar('v', /[A-z_$][A-z0-9_$]*/),
    new Grammar('+', /加/),
    new Grammar('-', /减/),
    new Grammar('*', /乘/),
    new Grammar('/', /除/),
    new Grammar('(', /\(/),
    new Grammar(')', /\)/)
])

我们就可以这样：

中文加法