0x000 概述

近期重新開始學習計算機基礎方面的東西，比如計算機組成原理、網絡原理、編譯原理之類的東西，目前正好在學習編譯原理，開始對這一塊的東西感興趣，但是理論的學習有點枯燥無味，決定換種方式，那就是先實踐、遇到問題嘗試解決，用實踐推動理論。原本打算寫個中文JS解析的，但是好像有點難，先就找個簡單的來做吧，那就是解析一下四則運算，就有了這個項目，聲明：這是一個很簡單的項目，這是一個很簡單的項目，這是一個很簡單的項目。其中用到的詞法分析、語法分析、自動機都是用簡單的方式實現，畢竟比較菜。

0x001 效果

• 源碼地址：github

• 實現功能：

  • 任意順序的四則+-*/正整數運算
  • 支持()
  • 前端后端通用
  • 提供直接計算函數
  • 提供四則運算表達式轉逆波蘭AST函數
  • 提供語法分析函數(暫時只支持上下兩個字符判定)

• 效果演示：

0x002 實現

既然說很簡單，那不管用到的理論和實現的方式都一定要都很簡單，實現這個效果一共需要克服三個問題：

1. 如何實現優先級計算，比如*/()的優先級大于+-。
2. 如何分割字符串，比如如何識別數字、符號和錯誤字符，也就是詞素化。
3. 如何實現語法檢測，也就是讓表達式的規則滿足要求，比如+后面比如跟隨數字或者(（這里將-當作操作，而不是符號）。

0x003 解決問題1: 如何實現優先級運算

1. 暫時忽略優先級

如果沒有優先級問題，那實現一個計算十分的簡單，比如下面的代碼可以實現一個簡單的加減或者乘除計算（10以內，超過一位數會遇到問題2，這里先簡單一點，避過問題2）：

        let calc = (input) => {let calMap = {'+': (num1, num2) => num1 + num2,'-': (num1, num2) => num1 - num2,'*': (num1, num2) => num1 * num2,'/': (num1, num2) => num1 / num2,}input = [...input].reverse()while (input.length >= 2) {let num1 = +input.pop()let op = input.pop()let num2 = +input.pop()input.push(calMap[op](num1, num2))}return input[0]}expect(calc('1+2+3+4+5-1')).toEqual(14)expect(calc('1*2*3/3')).toEqual(2)
復制代碼

算法步驟:

• 將輸入打散成一個棧，因為是10以內的，所以每個數只有一位：

  input = [...input].reverse()
  復制代碼

• 每次取出三位，如果是正確的輸入，則取出的三位，第一位是數字，第二位是操作符，第三位是數字：

  let num1 = +input.pop()
  let op = input.pop()
  let num2 = +input.pop()
  復制代碼

• 根據操作符做運算后將結果推回棧中，又形成了這么一個流程，一直到最后棧中只剩下一個數，或者說每次都要取出3個數，所以如果棧深度<=2，那就是最后的結果了：

  while (input.length >= 2) {// ......input.push(calMap[op](num1, num2))
  }
  復制代碼

動畫演示：

2. 考慮優先級

但是現在需要考慮優先級，比如*/的優先級大于+-，()的運算符最高，那如何解決呢，其實都已經有解決方案了，我用的是后綴表達式，也叫逆波蘭式

• 后綴表達式： 所謂的后綴表達式，就是將操作符放在表達式的最后邊，比如1+1表示成11+。
• 中綴表達式： 所謂的中綴表達式，其實就是我們平常使用的寫法了，這里不做深入。
• 前綴表達式 所謂的后綴表達式，就是將操作符放在表達式的最前邊，比如1+1表示成+11，這里不做深入

逆波蘭式可以參考下列文章

• Wiki-逆波蘭表示法
• 知乎-什么是逆波蘭表達式

3. 逆波蘭式解決優先級問題

在逆波蘭式子中，1+1*2可以轉化為112*+ 代碼演示：

 let calc = (input) => {let calMap = {'+': (num1, num2) => num1 + num2,'-': (num1, num2) => num1 - num2,'*': (num1, num2) => num1 * num2,'/': (num1, num2) => num1 / num2,}input = [...input].reverse()let resultStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue}if (/[+\-*/]/.test(token)) {let num1 = +resultStack.pop()let num2 = +resultStack.pop()resultStack.push(calMap[token](num1, num2))continue}}return resultStack[0]
}
expect(calc('123*+')).toEqual(7)
復制代碼

轉化之后計算步驟如下：

1. 初始化一個棧

       let resultStack = []
   復制代碼

2. 每次從表達式中取出一位

   let token = input.pop()
   復制代碼

3. 如果是數字，則推入棧中

   if (/[0-9]/.test(token)) {resultStack.push(token)continue
   }
   復制代碼

4. 如果是操作符，則從棧中取出兩個數，做相應的運算，再將結果推入棧中

   if (/[+\-*/]/.test(token)) {let num1 = +resultStack.pop()let num2 = +resultStack.pop()resultStack.push(calMap[token](num1, num2))continue
   }
   復制代碼

5. 如果表達式不為空，進入步驟2，如果表達式空了，棧中的數就是最后的結果，計算完成

   while (input.length) {// ...
   }
   return resultStack[0]
   復制代碼

動畫演示：

轉化成逆波蘭式之后有兩個優點：

• 不關心運算符優先級
• 去除括號，比如(1+2)*(3+4)，可以轉化為12+34+*，按照逆波蘭式運算方法即可完成運算

4. 中綴轉后綴

這是問題1的最后一個小問題了，這個問題的實現過程如下：

let parse = (input) => {input = [...input].reverse()let resultStack = [], opStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue}if (/[+\-*/]/.test(token)) {opStack.push(token)continue}}return [...resultStack, ...opStack.reverse()].join('')}expect(parse(`1+2-3+4-5`)).toEqual('12+3-4+5-')
復制代碼

準備兩個棧，一個棧存放結果，一個棧存放操作符，最后將兩個棧拼接起來上面的實現可以將1+2-3+4-5轉化為12+3-4+5-，但是如果涉及到優先級，就無能為力了，例如

        expect(parse(`1+2*3`)).toEqual('123*+')
復制代碼

1+2*3的轉化結果應該是123*+，但其實轉化的結果卻是123+*，*/的優先級高于+，所以，應該做如下修改

 let parse = (input) => {input = [...input].reverse()let resultStack = [], opStack = []while (input.length) {let token = input.pop()if (/[0-9]/.test(token)) {resultStack.push(token)continue}
//                if (/[+\-*/]/.test(token)) {
//                    opStack.push(token)
//                    continue
//                }if (/[*/]/.test(token)) {while (opStack.length) {let preOp = opStack.pop()if (/[+\-]/.test(preOp)) {opStack.push(preOp)opStack.push(token)token = nullbreak} else {resultStack.push(preOp)continue}}token && opStack.push(token)continue}if (/[+\-]/.test(token)) {while (opStack.length) {resultStack.push(opStack.pop())}opStack.push(token)continue}}return [...resultStack, ...opStack.reverse()].join('')}expect(parse(`1+2`)).toEqual('12+')expect(parse(`1+2*3`)).toEqual('123*+')
復制代碼

1. 當操作符為*/的時候，取出棧頂元素，判斷棧中的元素的優先級低是否低于*/，如果是就直接將操作符推入opStack，然后退出，否則一直將棧中取出的元素推入resultStack。

if (/[+\-]/.test(preOp)) {opStack.push(preOp)// 這里用了棧來做判斷，所以判斷完還得還回去...opStack.push(token)token = nullbreak
}else {resultStack.push(preOp)continue
}
復制代碼

2. 還要注意棧空掉的情況，需要將操作符直接入棧。

    token && opStack.push(token)continue
復制代碼

3. 當操作符為+-的時候，因為已經是最低的優先級了，所以直接將所有的操作符出棧就行了

if (/[+\-]/.test(token)) {while (opStack.length) {resultStack.push(opStack.pop())}opStack.push(token)continue
}
復制代碼

到這里已經解決了+-*/的優先級問題，只剩下()的優先級問題了，他的優先級是最高的，所以這里做如下修改即可：

if (/[+\-]/.test(token)) {while (opStack.length) {let op=opStack.pop()if (/\(/.test(op)){opStack.push(op)break}resultStack.push(op)}opStack.push(token)continue
}
if (/\(/.test(token)) {opStack.push(token)continue
}
if (/\)/.test(token)) {let preOp = opStack.pop()while (preOp !== '('&&opStack.length) {resultStack.push(preOp)preOp = opStack.pop()}continue
}
復制代碼

1. 當操作符是+-的時候，不再無腦彈出，如果是(就不彈出了

while (opStack.length) {let op=opStack.pop()if (/\(/.test(op)){opStack.push(op)break}resultStack.push(op)}opStack.push(token)
復制代碼

2. 當操作符是(的時候，就推入opStack

if (/\(/.test(token)) {opStack.push(token)continue
}
復制代碼

3. 當操作符是)的時候，就持續彈出opStack到resultStack，直到遇到(，(不推入resultStack

if (/\)/.test(token)) {let preOp = opStack.pop()while (preOp !== '('&&opStack.length) {resultStack.push(preOp)preOp = opStack.pop()}continue
}
復制代碼

動畫示例：

如此，就完成了中綴轉后綴了，那么整個問題1就已經被解決了，通過calc(parse(input))就能完成中綴=>后綴=>計算的整個流程了。

0x004 解決問題2:分割字符串

雖然上面已經解決了中綴=>后綴=>計算的大問題，但是最基礎的問題還沒解決，那就是輸入問題，在上面問題1的解決過程中，輸入不過是簡單的切割，而且還局限在10以內。而接下來，要解決的就是這個輸入的問題，如何分割輸入，達到要求？

• 解決方式1：正則，雖然正則可以做到如下，做個簡單的demo還是可以的，但是對于之后的語法檢測之類的東西不太有利，所以不太好，我放棄了這種方法

  (1+22)*(333+4444)`.match(/([0-9]+)|([+\-*/])|(\()|(\))/g)
  // 輸出
  // (11)["(", "1", "+", "22", ")", "*", "(", "333", "+", "4444", ")"]
  復制代碼

• 解決方法2：逐個字符分析，其大概的流程是

  while(input.length){let token = input.pop()if(/[0-9]/.test(token)) // 進入數字分析if(/[+\-*/\(\)]/.test(token))// 進入符號分析
  }
  復制代碼

接下來試用解決方案2來解決這個問題：

1 定義節點結構

當我們分割的時候，并不單純保存值，而是將每個節點保存成一個相似的結構，這個結構可以使用對象表示：

{type:'',value:''
}
復制代碼

其中，type是節點類型，可以將四則運算中所有可能出現的類型歸納出來，我的歸納如下：

    TYPE_NUMBER: 'TYPE_NUMBER', // 數字TYPE_LEFT_BRACKET: 'TYPE_LEFT_BRACKET', // (TYPE_RIGHT_BRACKET: 'TYPE_RIGHT_BRACKET', // )TYPE_OPERATION_ADD: 'TYPE_OPERATION_ADD', // +TYPE_OPERATION_SUB: 'TYPE_OPERATION_SUB', // -TYPE_OPERATION_MUL: 'TYPE_OPERATION_MUL', // *TYPE_OPERATION_DIV: 'TYPE_OPERATION_DIV', // /
復制代碼

value則是對應的真實值，比如123、+、-、*、/。

2 數字處理

如果是數字，則繼續往下讀，直到不是數字為止，將這過程中所有的讀取結果放到value中，最后入隊。

if (token.match(/[0-9]/)) {let next = tokens.pop()while (next !== undefined) {if (!next.match(/[0-9]/)) breaktoken += nextnext = tokens.pop()}result.push({type: type.TYPE_NUMBER,value: +token})token = next
}
復制代碼

3 符號處理

先定義一個符號和類型對照表，如果不在表中，說明是異常輸入，拋出異常，如果取到了，說明是正常輸入，入隊即可。

const opMap = {'(': type.TYPE_LEFT_BRACKET,')': type.TYPE_RIGHT_BRACKET,'+': type.TYPE_OPERATION_ADD,'-': type.TYPE_OPERATION_SUB,'*': type.TYPE_OPERATION_MUL,'/': type.TYPE_OPERATION_DIV
}
let type = opMap[token]
if (!type) throw `error input: ${token}`
result.push({type,value: token,
})
復制代碼

4 總結

這樣就完成了輸入的處理，這時候，其他的函數也需要處理一下，應為輸入已經從字符串變成了tokenize之后的序列了，修改完成之后就是可以calc(parse(tokenize()))完成一整套騷操作了。

0x005 解決問題3：語法檢測

語法檢測要解決的問題其實就是判斷輸入的正確性，是否滿足四則運算的規則，這里用了類似狀機的思想，不過簡單到爆炸，并且只能做單步判定～～ 定義一個語法表，該表定義了一個節點后面可以出現的節點類型，比如，+后面只能出現數字或者(之類。

let syntax = {[type.TYPE_NUMBER]: [type.TYPE_OPERATION_ADD,type.TYPE_OPERATION_SUB,type.TYPE_OPERATION_MUL,type.TYPE_OPERATION_DIV,type.TYPE_RIGHT_BRACKET],[type.TYPE_OPERATION_ADD]: [type.TYPE_NUMBER,type.TYPE_LEFT_BRACKET],//...
}
復制代碼

這樣我們就可以簡單的使用下面的語法判定方法了：

 while (tokens.length) {// ...let next = tokens.pop()if (!syntax[token.type].includes(next.type)) throw `syntax error: ${token.value} -> ${next.value}`// ...}
復制代碼

對于()，這里使用的是引用計數，如果是(，則計數+1，如果是)，則計數-1，檢測到最后的時候判定一下計數就好了：

    // ...if (token.type === type.TYPE_LEFT_BRACKET) {bracketCount++}// ...if (next.type === type.TYPE_RIGHT_BRACKET) {bracketCount--}// ...if (bracketCount < 0) {throw `syntax error: toooooo much ) -> )`}// ...
復制代碼

0x006 總結

• 該文章存在一些問題：
  1. 我推導不出為啥要用逆波蘭式，只是知道有這么一個解決方案，拿過來用而已，而不是由問題推導出解決方案。
  2. 文字功底不夠，講的不夠 cool。
• 該實現也存在一些問題：
  1. 并非完全用編譯原理的思想去實現，而是自己摸解決方案，先實踐，后了解問題。
  2. 并沒有參考太多別人的實現，有點閉門造車的感覺。
• 思考：
  1. 對于()的處理或許可以使用遞歸的方式，進入()之后重新開始一個新的表達式解析
  2. 思考不夠全，單元測試覆蓋不夠，許多坑還不知道在哪兒

總之：文章到此為止，有很多不夠詳細的地方還請見諒，多多交流，共同成長。

0x007 資源

• 編譯原理課程
• 源碼
• 動畫制作軟件Principle