站長(zhǎng)資訊網(wǎng)
免費(fèi)學(xué)習(xí)推薦：javascript學(xué)習(xí)教程
前端中的AST抽象語(yǔ)法樹(shù)問(wèn)題
- 四則運(yùn)算
- 正則表達(dá)式
- 詞法分析
- 語(yǔ)法分析
- 完整代碼
四則運(yùn)算
首先明確，此次的代碼都是基于LL的語(yǔ)法分析來(lái)實(shí)現(xiàn)的，實(shí)現(xiàn)的是四則混合運(yùn)算的功能，先看下定義：
TokenNumber：· 1 2 3 4 5 6 7 8 9 0 的組合
Operator:+ - * / 之一
WhiteSpace:<SP>
LineTerminator:<LF> <CR>
看下產(chǎn)生式：
正則表達(dá)式
我們首先實(shí)現(xiàn)正則表達(dá)式的匹配原則：
<script> var regexp = /([0-9.]+)|([ t]+)|([rn]+)|(*)|(/)|(+)|(-)/g var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"]; function tokenize(source) { var result = null; while(true) { result = regexp.exec(source); if(!result) break; for(var i = 1; i <= dictionary.length; i ++) { if(result[i]) console.log(dictionary[i - 1]); } console.log(result); } } tokenize("1024 + 10 * 25");</script>
此時(shí)我們看一下頁(yè)面的運(yùn)行打印結(jié)果：
值得一提的是這里用到了exec方法，exec() 方法用于檢索字符串中的正則表達(dá)式的匹配。
我們看一下它的語(yǔ)法：RegExpObject.exec(string)
如果 exec() 找到了匹配的文本，則返回一個(gè)結(jié)果數(shù)組。否則，返回 null。此數(shù)組的第 0 個(gè)元素是與正則表達(dá)式相匹配的文本，第 1 個(gè)元素是與 RegExpObject 的第 1 個(gè)子表達(dá)式相匹配的文本（如果有的話(huà)），第 2 個(gè)元素是與 RegExpObject 的第 2 個(gè)子表達(dá)式相匹配的文本（如果有的話(huà)），以此類(lèi)推。除了數(shù)組元素和 length 屬性之外，exec() 方法還返回兩個(gè)屬性。index 屬性聲明的是匹配文本的第一個(gè)字符的位置。input 屬性則存放的是被檢索的字符串 string。我們可以看得出，在調(diào)用非全局的 RegExp 對(duì)象的 exec() 方法時(shí)，返回的數(shù)組與調(diào)用方法 String.match() 返回的數(shù)組是相同的。
但是，當(dāng) RegExpObject 是一個(gè)全局正則表達(dá)式時(shí)，exec() 的行為就稍微復(fù)雜一些。它會(huì)在 RegExpObject 的 lastIndex 屬性指定的字符處開(kāi)始檢索字符串 string。當(dāng) exec() 找到了與表達(dá)式相匹配的文本時(shí)，在匹配后，它將把 RegExpObject 的 lastIndex 屬性設(shè)置為匹配文本的最后一個(gè)字符的下一個(gè)位置。這就是說(shuō)，您可以通過(guò)反復(fù)調(diào)用 exec() 方法來(lái)遍歷字符串中的所有匹配文本。當(dāng) exec() 再也找不到匹配的文本時(shí)，它將返回 null，并把 lastIndex 屬性重置為 0。
詞法分析
我們?cè)谶@一部分對(duì)上面的代碼做優(yōu)化。
首先是剛才提到的:當(dāng) RegExpObject 是一個(gè)全局正則表達(dá)式時(shí)，exec() 的行為就稍微復(fù)雜一些。它會(huì)在 RegExpObject 的 lastIndex 屬性指定的字符處開(kāi)始檢索字符串 string。當(dāng) exec() 找到了與表達(dá)式相匹配的文本時(shí)，在匹配后，它將把 RegExpObject 的 lastIndex 屬性設(shè)置為匹配文本的最后一個(gè)字符的下一個(gè)位置。
那么我們就要考慮到?jīng)]有匹配上字符的情況，做一個(gè)判斷處理：
<script> var regexp = /([0-9.]+)|([ t]+)|([rn]+)|(*)|(/)|(+)|(-)/g var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"]; function* tokenize(source) { var result = null; var lastIndex = 0; while(true) { lastIndex = regexp.lastIndex; result = regexp.exec(source); if(!result) break; if(regexp.lastIndex - lastIndex > result[0].length) break; let token = { type: null, value: null } for(var i = 1; i <= dictionary.length; i ++) { if(result[i]) token.type = dictionary[i - 1]; } token.value = result[0]; yield token } yield { type: 'EOF' } } for (let token of tokenize("1024 + 10 * 25")) { console.log(token) }</script>
如上，我們對(duì)regexp.lastIndex - lastIndex 和 result[0] 的長(zhǎng)度進(jìn)行比較，判斷是否有字符串沒(méi)有匹配上。
將整個(gè)函數(shù)改成generator函數(shù)的形式，我們看下運(yùn)行的結(jié)果：
語(yǔ)法分析
首先編寫(xiě)分塊的產(chǎn)生式，我們看一下總的代碼結(jié)構(gòu)：
<script> var regexp = /([0-9.]+)|([ t]+)|([rn]+)|(*)|(/)|(+)|(-)/g var dictionary = ["Number", "Whitespace", "LineTerminator", "*", "/", "+", "-"]; function* tokenize(source) { var result = null; var lastIndex = 0; while(true) { lastIndex = regexp.lastIndex; result = regexp.exec(source); if(!result) break; if(regexp.lastIndex - lastIndex > result[0].length) break; let token = { type: null, value: null } for(var i = 1; i <= dictionary.length; i ++) { if(result[i]) token.type = dictionary[i - 1]; } token.value = result[0]; yield token } yield { type: 'EOF' } } let source = []; for(let token of tokenize("10 * 25")) { if (token.type !== "Whitespace" && token.type !== "LineTerminator") source.push(token); } function Expression(tokens) { } function AdditiveExpression(source){ } function MultiplicativeExpresson(source) { console.log(source); } MultiplicativeExpresson("10 * 25")</script>
我們先從MultiplicativeExpresson來(lái)進(jìn)行研究，它分為四種情況：
function MultiplicativeExpresson(source) { //如果是數(shù)字則進(jìn)行封裝 if(source[0].type === "Number") { let node = { type: "MultiplicativeExpresson", children:[source[0]] } source[0] = node; return MultiplicativeExpresson(source) } //如果是乘號(hào)或者除號(hào)，則將三項(xiàng)出棧，進(jìn)行重組 if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "*") { let node = { type: "MultiplicativeExpresson", operator: "*", children: [] } node.children.push(source.shift()); node.children.push(source.shift()); node.children.push(source.shift()); source.unshift(node); return MultiplicativeExpresson(source) } if(source[0].type === "MultiplicativeExpresson" && source[1] && source[1].type === "/") { let node = { type: "MultiplicativeExpresson", operator: "*", children: [] } node.children.push(source.shift()); node.children.push(source.shift()); node.children.push(source.shift()); source.unshift(node); return MultiplicativeExpresson(source) } //遞歸結(jié)束的條件 if(source[0].type === "MultiplicativeExpresson") return source[0]; return MultiplicativeExpresson(source); }
我們看一下當(dāng)source為"10 * 25 / 2"時(shí)調(diào)用console.log(MultiplicativeExpresson(source))最后運(yùn)行的結(jié)果：
接下來(lái)看AdditiveExpression 本質(zhì)上和MultiplicativeExpresson沒(méi)有什么不同，差異點(diǎn)已經(jīng)標(biāo)注在代碼當(dāng)中了：
function AdditiveExpression(source){ if(source[0].type === "MultiplicativeExpresson") { let node = { type: "AdditiveExpression", children:[source[0]] } source[0] = node; return AdditiveExpression(source) } //如果是乘號(hào)或者除號(hào)，則將三項(xiàng)出棧，進(jìn)行重組 if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "+") { let node = { type: "AdditiveExpression", operator: "+", children: [] } node.children.push(source.shift()); node.children.push(source.shift()); //考慮到第三個(gè)數(shù)可能時(shí)Number 需要在這里再次調(diào)用一下 MultiplicativeExpresson 做處理 MultiplicativeExpresson(source); node.children.push(source.shift()); source.unshift(node); return AdditiveExpression(source) } if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "-") { let node = { type: "AdditiveExpression", operator: "-", children: [] } node.children.push(source.shift()); node.children.push(source.shift()); MultiplicativeExpresson(source); node.children.push(source.shift()); source.unshift(node); return AdditiveExpression(source) } //遞歸結(jié)束的條件 if(source[0].type === "AdditiveExpression") return source[0]; //第一次進(jìn)循環(huán) 調(diào)用 MultiplicativeExpresson(source); return AdditiveExpression(source); }
我們看一下當(dāng)source為"10 * 25 / 2"時(shí)調(diào)用console.log(AdditiveExpression(source))最后運(yùn)行的結(jié)果：
那么Expression的代碼邏輯就很好表達(dá)了：
function Expression(tokens) { if(source[0].type === "AdditiveExpression" && source[1] && source[1].type === "EOF") { let node = { type: "Expression", children: [source.shift(), source.shift()] } source.unshift(node); return node; } AdditiveExpression(source); return Expression(source); }
看下運(yùn)行后的結(jié)果：
