眾所周知，js做算術(shù)運(yùn)算是不精確的，0.1 + 0.2并不等于0.3。

0.1 + 0.2

/**
 * @desc 解決浮動(dòng)運(yùn)算問題，避免小數(shù)點(diǎn)后產(chǎn)生多位數(shù)和計(jì)算精度損失。
 * 問題示例：2.3 + 2.4 = 4.699999999999999
 *         1.0 - 0.9 = 0.09999999999999998
 *         0.3 * 3 = 0.8999999999999999
 *         0.3 / 0.1 = 2.9999999999999996
 */

/**
 * 把錯(cuò)誤的數(shù)據(jù)轉(zhuǎn)正
 * strip(0.09999999999999998)=0.1
 */
function strip(num, precision) {
  return +parseFloat(num.toPrecision(precision || 12))
}

/**
 * 把小數(shù)放大成整數(shù)
 * @param {*number} num 輸入數(shù)
 */
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重新定義了加減乘除，我們?cè)谧鲇?jì)算的時(shí)候需要調(diào)用這些方法，比如計(jì)算：(1+2*(3-1))/2，我們需要這么寫：

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

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

是不是覺得很麻煩，還要仔細(xì)檢查方法調(diào)用的順序，不小心就寫錯(cuò)了。
如果我們?cè)趯懘a的時(shí)候還是寫(1+2*(3-1))/2，代碼在執(zhí)行的時(shí)候，它被解釋成divide(plus(1, multiply(2, minus(3, 1))), 2)執(zhí)行就好了。
那么，讓我們做點(diǎn)好玩的事情，用js寫一個(gè)四則運(yùn)算的解釋器吧，用它把+-*/解釋成number-precision對(duì)應(yīng)的方法執(zhí)行。

詞法分析

我們只需要識(shí)別8種詞法單元（token）：加號(hào)、減號(hào)、乘號(hào)、除號(hào)、左括號(hào)、右括號(hào)、數(shù)字、變量，分別用字符表示為：+,-,*,/,(,),n,v。
我們使用正則來識(shí)別token，并采用最長(zhǎng)匹配原則。
首先，定義一個(gè)Grammar類，這個(gè)類很簡(jiǎn)單，它存儲(chǔ)了表示token的字符，和識(shí)別token的正則。

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

我們需要識(shí)別的8種token分別定義為：

/* 數(shù)字 */
new Grammar('n', /(?:[0-9]\.|[1-9][0-9]+\.|\.[0-9]|[0-9])[0-9]*/)
/* 變量 */
new Grammar('v', /[A-z_$][A-z0-9_$]*/)
/* 加號(hào) */
new Grammar('+', /\+/)
/* 減號(hào) */
new Grammar('-', /-/)
/* 乘號(hào) */
new Grammar('*', /\*/)
/* 除號(hào) */
new Grammar('/', /\//)
/* 左括號(hào) */
new Grammar('(', /\(/)
/* 右括號(hào) */
new Grammar(')', /\)/)

然后寫一個(gè)詞法分析器，它讀入字符串，輸出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)

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

    if (!type) throw new Error(`詞法錯(cuò)誤：'${str}' 包含無法識(shí)別的字符`)

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

    if (nextStr) {
      // 通過遞歸，識(shí)別下一個(gè)單詞
      this.analyze(nextStr)
    }

    return [...this.tokens]
  }
}

看看效果：

詞法分析

語法分析

詞法分析后，我們需要分析語法。
首先，我們需要給出上下文無關(guān)文法，來描述我們的語法規(guī)則：

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

其中每一行，我們稱之為一個(gè)產(chǎn)生式，產(chǎn)生式中->左邊的大寫字符是非終結(jié)符，上面的文法中有3個(gè)非終結(jié)符：E、P和S。非終結(jié)符可由產(chǎn)生式中->右邊的式子推導(dǎo)（擴(kuò)展）。產(chǎn)生式右邊的式子由非終結(jié)符和終結(jié)符組成，終結(jié)符就是詞法分析中得到的token。
S是文法的開始符號(hào)，從S開始，我們應(yīng)用文法中的規(guī)則，遞歸展開非終結(jié)符，直到只剩下終結(jié)符為止，最終生成四則運(yùn)算語法規(guī)則集合。
下面是根據(jù)規(guī)則完全展開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序列，如果能通過文法推導(dǎo)出來，那就是有效語法。我們可以使用非確定性下推自動(dòng)機(jī)（NPDA）來判斷輸入是否語法正確。

NPDA

狀態(tài)圖

如圖所示，NPDA使用棧存儲(chǔ)推導(dǎo)過程中的非終結(jié)符和終結(jié)符，并在4個(gè)狀態(tài)間轉(zhuǎn)移。圖中，每個(gè)圓圈代表一個(gè)狀態(tài)，箭頭指示了NPDA從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。引起狀態(tài)轉(zhuǎn)移的事件顯示在表示狀態(tài)轉(zhuǎn)移的橫線上方，狀態(tài)轉(zhuǎn)移時(shí)所采取的動(dòng)作顯示在橫線下方。
為了更直觀的看NPDA是如何工作，我們假設(shè)輸入是0.1+0.2，經(jīng)過詞法分析后得到token序列n+n。下面是NPDA的一個(gè)可能執(zhí)行：

從狀態(tài)圖中可以看到，NPDA每次轉(zhuǎn)移，要么是狀態(tài)變化，要么是棧變化，所以轉(zhuǎn)移實(shí)際上是從一個(gè)狀態(tài)+棧到另一個(gè)狀態(tài)+棧。為了方便，我們用配置表示一個(gè)狀態(tài)和一個(gè)棧的組合。

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
  }
}

配置中的棧，我們也定義一個(gè)類，方便操作：

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)
  }
}

有了配置之后，我們還需要一種規(guī)則類型，來告訴NPDA，配置間應(yīng)該如何轉(zhuǎn)移。一條規(guī)則由當(dāng)前配置、輸入符號(hào)和下一個(gè)配置組成。通過NPDA的當(dāng)前配置和讀取的符號(hào)，我們能找到它能應(yīng)用的規(guī)則，并應(yīng)用規(guī)則將NPDA轉(zhuǎn)移到下一個(gè)配置。規(guī)則類定義如下：

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
  }
}

一個(gè)NPDA里會(huì)有很多規(guī)則，我們可以把所有規(guī)則封裝到一個(gè)規(guī)則手冊(cè)里。

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并使用規(guī)則手冊(cè)不斷轉(zhuǎn)移，其中有一些規(guī)則不需要讀取token，我們稱這種規(guī)則為自由移動(dòng)，當(dāng)NPDA當(dāng)前配置能應(yīng)用自由移動(dòng)規(guī)則時(shí)，會(huì)立即應(yīng)用自由移動(dòng)規(guī)則轉(zhuǎn)移，之后再讀取下一個(gè)token。如果NPDA讀取token后發(fā)現(xiàn)無可用規(guī)則，則會(huì)被置為阻塞狀態(tài)，終止運(yùn)行。

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封裝一下，每次語法分析實(shí)例化一個(gè)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()
  }
}

運(yùn)行一下，看看效果：

語法分析

規(guī)約

僅僅識(shí)別一個(gè)句子是否語法正確是不夠的，我們還需要將四則運(yùn)算表達(dá)式最終規(guī)約成一個(gè)數(shù)。我們將借助抽象語法樹（AST）幫我們完成這個(gè)任務(wù)。AST只包含有用節(jié)點(diǎn)：+、-、*、/、n、v。每個(gè)節(jié)點(diǎn)，我們需要知道它的類型、優(yōu)先級(jí)和值。我們可以這樣定義節(jié)點(diǎn)：

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

四則運(yùn)算的AST比較簡(jiǎn)單，因?yàn)?code>+、-、*、/都是二目運(yùn)算符，所以我們可以用二叉樹定義四則運(yùn)算的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)
  }
}

在語法分析時(shí)，我們這樣構(gòu)建AST：

1. 初始狀態(tài)時(shí)，AST為空；
2. 讀取token時(shí)，我們用這個(gè)token實(shí)例化一個(gè)節(jié)點(diǎn)，并用這個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)實(shí)例化一棵新樹。將新樹合并到AST。

合并算法：

1. 當(dāng)AST為空時(shí)，使用新樹作為AST；
2. 當(dāng)新樹的優(yōu)先級(jí)（樹的優(yōu)先級(jí)即其根節(jié)點(diǎn)優(yōu)先級(jí)）大于AST優(yōu)先級(jí)時(shí)，將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
}

每種樹定義好規(guī)約方法，最后封裝如下：

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(`語法錯(cuò)誤：Unexpected token '${token.value}'`)
    }
  }

  reduce(env) {
    if (!this.isAccepted()) throw new Error('語法錯(cuò)誤')
    return this.ast.reduce(env)
  }
}

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

重新定義四則運(yùn)算

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(')', /\)/)
])

我們就可以這樣：

中文加法