摘要:概述近期重新開(kāi)始學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)方面的東西,比如計(jì)算機(jī)組成原理網(wǎng)絡(luò)原理編譯原理之類的東西,目前正好在學(xué)習(xí)編譯原理,開(kāi)始對(duì)這一塊的東西感興趣,但是理論的學(xué)習(xí)有點(diǎn)枯燥無(wú)味,決定換種方式,那就是先實(shí)踐遇到問(wèn)題嘗試解決,用實(shí)踐推動(dòng)理論。
0x000 概述
近期重新開(kāi)始學(xué)習(xí)計(jì)算機(jī)基礎(chǔ)方面的東西,比如計(jì)算機(jī)組成原理、網(wǎng)絡(luò)原理、編譯原理之類的東西,目前正好在學(xué)習(xí)編譯原理,開(kāi)始對(duì)這一塊的東西感興趣,但是理論的學(xué)習(xí)有點(diǎn)枯燥無(wú)味,決定換種方式,那就是先實(shí)踐、遇到問(wèn)題嘗試解決,用實(shí)踐推動(dòng)理論。原本打算寫(xiě)個(gè)中文JS解析的,但是好像有點(diǎn)難,需要慢慢實(shí)現(xiàn),于是就找個(gè)簡(jiǎn)單的來(lái)做,那就是解析一下四則運(yùn)算,就有了這個(gè)項(xiàng)目,聲明:這是一個(gè)很簡(jiǎn)單的項(xiàng)目,這是一個(gè)很簡(jiǎn)單的項(xiàng)目,這是一個(gè)很簡(jiǎn)單的項(xiàng)目。其中用到的詞法分析、語(yǔ)法分析、自動(dòng)機(jī)都是用簡(jiǎn)單的方式實(shí)現(xiàn),畢竟比較菜。
0x001 效果源碼地址:github
實(shí)現(xiàn)功能:
任意順序的四則+-*/正整數(shù)運(yùn)算
支持()
前端后端通用
提供直接計(jì)算函數(shù)
提供四則運(yùn)算表達(dá)式轉(zhuǎn)逆波蘭AST函數(shù)
提供語(yǔ)法分析函數(shù)(暫時(shí)只支持上下兩個(gè)字符判定)
效果演示:
既然說(shuō)很簡(jiǎn)單,那不管用到的理論和實(shí)現(xiàn)的方式都一定要都很簡(jiǎn)單,實(shí)現(xiàn)這個(gè)效果一共需要克服三個(gè)問(wèn)題:
如何實(shí)現(xiàn)優(yōu)先級(jí)計(jì)算,比如*/()的優(yōu)先級(jí)大于+-。
如何分割字符串,比如如何識(shí)別數(shù)字、符號(hào)和錯(cuò)誤字符,也就是詞素化。
如何實(shí)現(xiàn)語(yǔ)法檢測(cè),也就是讓表達(dá)式的規(guī)則滿足要求,比如+后面比如跟隨數(shù)字或者((這里將-當(dāng)作操作,而不是符號(hào))。
0x003 解決問(wèn)題1: 如何實(shí)現(xiàn)優(yōu)先級(jí)運(yùn)算 1. 暫時(shí)忽略優(yōu)先級(jí)如果沒(méi)有優(yōu)先級(jí)問(wèn)題,那實(shí)現(xiàn)一個(gè)計(jì)算十分的簡(jiǎn)單,比如下面的代碼可以實(shí)現(xiàn)一個(gè)簡(jiǎn)單的加減或者乘除計(jì)算(10以內(nèi),超過(guò)一位數(shù)會(huì)遇到問(wèn)題2,這里先簡(jiǎn)單一點(diǎn),避過(guò)問(wèn)題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)
算法步驟:
將輸入打散成一個(gè)棧,因?yàn)槭?0以內(nèi)的,所以每個(gè)數(shù)只有一位:
input = [...input].reverse()
每次取出三位,如果是正確的輸入,則取出的三位,第一位是數(shù)字,第二位是操作符,第三位是數(shù)字:
let num1 = +input.pop() let op = input.pop() let num2 = +input.pop()
根據(jù)操作符做運(yùn)算后將結(jié)果推回棧中,又形成了這么一個(gè)流程,一直到最后棧中只剩下一個(gè)數(shù),或者說(shuō)每次都要取出3個(gè)數(shù),所以如果棧深度<=2,那就是最后的結(jié)果了:
while (input.length >= 2) { // ...... input.push(calMap[op](num1, num2)) }
動(dòng)畫(huà)演示:
2. 考慮優(yōu)先級(jí)但是現(xiàn)在需要考慮優(yōu)先級(jí),比如*/的優(yōu)先級(jí)大于+-,()的運(yùn)算符最高,那如何解決呢,其實(shí)都已經(jīng)有解決方案了,我用的是后綴表達(dá)式,也叫逆波蘭式
后綴表達(dá)式:
所謂的后綴表達(dá)式,就是將操作符放在表達(dá)式的最后邊,比如1+1表示成11+。
中綴表達(dá)式:
所謂的中綴表達(dá)式,其實(shí)就是我們平常使用的寫(xiě)法了,這里不做深入。
前綴表達(dá)式
所謂的后綴表達(dá)式,就是將操作符放在表達(dá)式的最前邊,比如1+1表示成+11,這里不做深入
逆波蘭式可以參考下列文章
Wiki-逆波蘭表示法
知乎-什么是逆波蘭表達(dá)式
3. 逆波蘭式解決優(yōu)先級(jí)問(wèn)題在逆波蘭式子中,1+1*2可以轉(zhuǎn)化為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)
轉(zhuǎn)化之后計(jì)算步驟如下:
初始化一個(gè)棧
let resultStack = []
每次從表達(dá)式中取出一位
let token = input.pop()
如果是數(shù)字,則推入棧中
if (/[0-9]/.test(token)) { resultStack.push(token) continue }
如果是操作符,則從棧中取出兩個(gè)數(shù),做相應(yīng)的運(yùn)算,再將結(jié)果推入棧中
if (/[+-*/]/.test(token)) { let num1 = +resultStack.pop() let num2 = +resultStack.pop() resultStack.push(calMap[token](num1, num2)) continue }
如果表達(dá)式不為空,進(jìn)入步驟2,如果表達(dá)式空了,棧中的數(shù)就是最后的結(jié)果,計(jì)算完成
while (input.length) { // ... } return resultStack[0]
動(dòng)畫(huà)演示:
轉(zhuǎn)化成逆波蘭式之后有兩個(gè)優(yōu)點(diǎn):
不關(guān)心運(yùn)算符優(yōu)先級(jí)
去除括號(hào),比如(1+2)*(3+4),可以轉(zhuǎn)化為12+34+*,按照逆波蘭式運(yùn)算方法即可完成運(yùn)算
4. 中綴轉(zhuǎn)后綴這是問(wèn)題1的最后一個(gè)小問(wèn)題了,這個(gè)問(wèn)題的實(shí)現(xiàn)過(guò)程如下:
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-")
準(zhǔn)備兩個(gè)棧,一個(gè)棧存放結(jié)果,一個(gè)棧存放操作符,最后將兩個(gè)棧拼接起來(lái)上面的實(shí)現(xiàn)可以將1+2-3+4-5轉(zhuǎn)化為12+3-4+5-,但是如果涉及到優(yōu)先級(jí),就無(wú)能為力了,例如
expect(parse(`1+2*3`)).toEqual("123*+")
1+2*3的轉(zhuǎn)化結(jié)果應(yīng)該是123*+,但其實(shí)轉(zhuǎn)化的結(jié)果卻是123+*,*/的優(yōu)先級(jí)高于+,所以,應(yīng)該做如下修改
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 = null break } 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*+")
當(dāng)操作符為*/的時(shí)候,取出棧頂元素,判斷棧中的元素的優(yōu)先級(jí)低是否低于*/,如果是就直接將操作符推入opStack,然后退出,否則一直將棧中取出的元素推入resultStack。
if (/[+-]/.test(preOp)) { opStack.push(preOp)// 這里用了棧來(lái)做判斷,所以判斷完還得還回去... opStack.push(token) token = null break }else { resultStack.push(preOp) continue }
還要注意??盏舻那闆r,需要將操作符直接入棧。
token && opStack.push(token) continue
當(dāng)操作符為+-的時(shí)候,因?yàn)橐呀?jīng)是最低的優(yōu)先級(jí)了,所以直接將所有的操作符出棧就行了
if (/[+-]/.test(token)) { while (opStack.length) { resultStack.push(opStack.pop()) } opStack.push(token) continue }
到這里已經(jīng)解決了+-*/的優(yōu)先級(jí)問(wèn)題,只剩下()的優(yōu)先級(jí)問(wèn)題了,他的優(yōu)先級(jí)是最高的,所以這里做如下修改即可:
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 }
當(dāng)操作符是+-的時(shí)候,不再無(wú)腦彈出,如果是(就不彈出了
while (opStack.length) { let op=opStack.pop() if (/(/.test(op)){ opStack.push(op) break } resultStack.push(op) } opStack.push(token)
當(dāng)操作符是(的時(shí)候,就推入opStack
if (/(/.test(token)) { opStack.push(token) continue }
當(dāng)操作符是)的時(shí)候,就持續(xù)彈出opStack到resultStack,直到遇到(,(不推入resultStack
if (/)/.test(token)) { let preOp = opStack.pop() while (preOp !== "("&&opStack.length) { resultStack.push(preOp) preOp = opStack.pop() } continue }
完整代碼:
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)) { while (opStack.length) { let preOp = opStack.pop() if (/[+-]/.test(preOp)) { opStack.push(preOp) opStack.push(token) token = null break } else { resultStack.push(preOp) continue } } token && 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 } } return [...resultStack, ...opStack.reverse()].join("")
動(dòng)畫(huà)示例:
如此,就完成了中綴轉(zhuǎn)后綴了,那么整個(gè)問(wèn)題1就已經(jīng)被解決了,通過(guò)calc(parse(input))就能完成中綴=>后綴=>計(jì)算的整個(gè)流程了。
雖然上面已經(jīng)解決了中綴=>后綴=>計(jì)算的大問(wèn)題,但是最基礎(chǔ)的問(wèn)題還沒(méi)解決,那就是輸入問(wèn)題,在上面問(wèn)題1的解決過(guò)程中,輸入不過(guò)是簡(jiǎn)單的切割,而且還局限在10以內(nèi)。而接下來(lái),要解決的就是這個(gè)輸入的問(wèn)題,如何分割輸入,達(dá)到要求?
解決方式1:正則,雖然正則可以做到如下,做個(gè)簡(jiǎn)單的demo還是可以的,但是對(duì)于之后的語(yǔ)法檢測(cè)之類的東西不太有利,所以不太好,我放棄了這種方法
(1+22)*(333+4444)`.match(/([0-9]+)|([+-*/])|(()|())/g) // 輸出 // (11)?["(", "1", "+", "22", ")", "*", "(", "333", "+", "4444", ")"]
解決方法2:逐個(gè)字符分析,其大概的流程是
while(input.length){ let token = input.pop() if(/[0-9]/.test(token)) // 進(jìn)入數(shù)字分析 if(/[+-*/()]/.test(token))// 進(jìn)入符號(hào)分析 }
接下來(lái)試用解決方案2來(lái)解決這個(gè)問(wèn)題:
1 定義節(jié)點(diǎn)結(jié)構(gòu)當(dāng)我們分割的時(shí)候,并不單純保存值,而是將每個(gè)節(jié)點(diǎn)保存成一個(gè)相似的結(jié)構(gòu),這個(gè)結(jié)構(gòu)可以使用對(duì)象表示:
{ type:"", value:"" }
其中,type是節(jié)點(diǎn)類型,可以將四則運(yùn)算中所有可能出現(xiàn)的類型歸納出來(lái),我的歸納如下:
TYPE_NUMBER: "TYPE_NUMBER", // 數(shù)字 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則是對(duì)應(yīng)的真實(shí)值,比如123、+、-、*、/。
2 數(shù)字處理如果是數(shù)字,則繼續(xù)往下讀,直到不是數(shù)字為止,將這過(guò)程中所有的讀取結(jié)果放到value中,最后入隊(duì)。
if (token.match(/[0-9]/)) { let next = tokens.pop() while (next !== undefined) { if (!next.match(/[0-9]/)) break token += next next = tokens.pop() } result.push({ type: type.TYPE_NUMBER, value: +token }) token = next }3 符號(hào)處理
先定義一個(gè)符號(hào)和類型對(duì)照表,如果不在表中,說(shuō)明是異常輸入,拋出異常,如果取到了,說(shuō)明是正常輸入,入隊(duì)即可。
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 總結(jié)
這樣就完成了輸入的處理,這時(shí)候,其他的函數(shù)也需要處理一下,應(yīng)為輸入已經(jīng)從字符串變成了tokenize之后的序列了,修改完成之后就是可以calc(parse(tokenize()))完成一整套騷操作了。
0x005 解決問(wèn)題3:語(yǔ)法檢測(cè)語(yǔ)法檢測(cè)要解決的問(wèn)題其實(shí)就是判斷輸入的正確性,是否滿足四則運(yùn)算的規(guī)則,這里用了類似狀機(jī)的思想,不過(guò)簡(jiǎn)單到爆炸,并且只能做單步判定~~
定義一個(gè)語(yǔ)法表,該表定義了一個(gè)節(jié)點(diǎn)后面可以出現(xiàn)的節(jié)點(diǎn)類型,比如,+后面只能出現(xiàn)數(shù)字或者(之類。
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 ], [type.TYPE_OPERATION_SUB]: [ type.TYPE_NUMBER, type.TYPE_LEFT_BRACKET ], [type.TYPE_OPERATION_MUL]: [ type.TYPE_NUMBER, type.TYPE_LEFT_BRACKET ], [type.TYPE_OPERATION_DIV]: [ type.TYPE_NUMBER, type.TYPE_LEFT_BRACKET ], [type.TYPE_LEFT_BRACKET]: [ type.TYPE_NUMBER, type.TYPE_LEFT_BRACKET ], [type.TYPE_RIGHT_BRACKET]: [ type.TYPE_OPERATION_ADD, type.TYPE_OPERATION_SUB, type.TYPE_OPERATION_MUL, type.TYPE_OPERATION_DIV, type.TYPE_RIGHT_BRACKET ] }
這樣我們就可以簡(jiǎn)單的使用下面的語(yǔ)法判定方法了:
while (tokens.length) { // ... let next = tokens.pop() if (!syntax[token.type].includes(next.type)) throw `syntax error: ${token.value} -> ${next.value}` // ... }
對(duì)于(),這里使用的是引用計(jì)數(shù),如果是(,則計(jì)數(shù)+1,如果是),則計(jì)數(shù)-1,檢測(cè)到最后的時(shí)候判定一下計(jì)數(shù)就好了:
// ... 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 總結(jié)
該文章存在一些問(wèn)題:
我推導(dǎo)不出為啥要用逆波蘭式,只是知道有這么一個(gè)解決方案,拿過(guò)來(lái)用而已,而不是由問(wèn)題推導(dǎo)出解決方案。
文字功底不夠,講的不夠 cool。
該實(shí)現(xiàn)也存在一些問(wèn)題:
并非完全用編譯原理的思想去實(shí)現(xiàn),而是自己摸解決方案,先實(shí)踐,后了解問(wèn)題。
并沒(méi)有參考太多別人的實(shí)現(xiàn),有點(diǎn)閉門(mén)造車的感覺(jué)。
思考:
對(duì)于()的處理或許可以使用遞歸的方式,進(jìn)入()之后重新開(kāi)始一個(gè)新的表達(dá)式解析
思考不夠全,單元測(cè)試覆蓋不夠,許多坑還不知道在哪兒
總之:文章到此為止,有很多不夠詳細(xì)的地方還請(qǐng)見(jiàn)諒,多多交流,共同成長(zhǎng)。
0x007 資源編譯原理課程
源碼
動(dòng)畫(huà)制作軟件Principle
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/100634.html
摘要:四則運(yùn)算編譯器,雖然說(shuō)功能很簡(jiǎn)單,只能編譯四則運(yùn)算表達(dá)式。再?gòu)?fù)雜的編譯器再簡(jiǎn)單的編譯器,功能上是差不多的,只是復(fù)雜的編譯器實(shí)現(xiàn)上會(huì)更困難。每一章都是理論與實(shí)踐結(jié)合的經(jīng)典,從計(jì)算機(jī)硬件知識(shí)到軟件體系,再到編譯原理和操作系統(tǒng)。 四則運(yùn)算編譯器,雖然說(shuō)功能很簡(jiǎn)單,只能編譯四則運(yùn)算表達(dá)式。但是編譯原理前端部分幾乎都有涉及,詞法分析,語(yǔ)法分析,還有代碼生成。 再?gòu)?fù)雜的編譯器、再簡(jiǎn)單的編譯器,功能...
摘要:前言在學(xué)習(xí)前端的時(shí)候,我總是能聽(tīng)到很多高級(jí)詞匯,比如今天會(huì)聊到的函數(shù)式編程高階函數(shù)。接下來(lái)我們看看,高階函數(shù)有可能會(huì)遇到的問(wèn)題,又如何去解決。 前言 在學(xué)習(xí)前端的時(shí)候,我總是能聽(tīng)到很多高級(jí)詞匯,比如今天會(huì)聊到的 函數(shù)式編程(Functional Programming) & 高階函數(shù) (Higher-order function) 。但是當(dāng)你真正的理解什么是 函數(shù)式編程 & 高階函數(shù) ...
摘要:表示調(diào)用棧在下一將要執(zhí)行的任務(wù)。兩方性能解藥我們一般有兩種方案突破上文提到的瓶頸將耗時(shí)高成本高易阻塞的長(zhǎng)任務(wù)切片,分成子任務(wù),并異步執(zhí)行這樣一來(lái),這些子任務(wù)會(huì)在不同的周期執(zhí)行,進(jìn)而主線程就可以在子任務(wù)間隙當(dāng)中執(zhí)行更新操作。 showImg(https://segmentfault.com/img/remote/1460000016008111); 性能一直以來(lái)是前端開(kāi)發(fā)中非常重要的話題...
閱讀 728·2021-11-25 09:43
閱讀 3000·2021-11-24 10:20
閱讀 1063·2021-10-27 14:18
閱讀 1122·2021-09-08 09:36
閱讀 3444·2021-07-29 14:49
閱讀 1828·2019-08-30 14:07
閱讀 2978·2019-08-29 16:52
閱讀 3093·2019-08-29 13:12