站長資訊網
免費學習推薦：javascript學習教程
前端中的AST抽象語法樹問題
- 四則運算
- 正則表達式
- 詞法分析
- 語法分析
- 完整代碼
四則運算
首先明確，此次的代碼都是基于LL的語法分析來實現的，實現的是四則混合運算的功能，先看下定義：
TokenNumber：· 1 2 3 4 5 6 7 8 9 0 的組合
Operator:+ - * / 之一
WhiteSpace:<SP>
LineTerminator:<LF> <CR>
看下產生式：
正則表達式
我們首先實現正則表達式的匹配原則：
<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>
此時我們看一下頁面的運行打印結果：
值得一提的是這里用到了exec方法，exec() 方法用于檢索字符串中的正則表達式的匹配。
我們看一下它的語法：RegExpObject.exec(string)
如果 exec() 找到了匹配的文本，則返回一個結果數組。否則，返回 null。此數組的第 0 個元素是與正則表達式相匹配的文本，第 1 個元素是與 RegExpObject 的第 1 個子表達式相匹配的文本（如果有的話），第 2 個元素是與 RegExpObject 的第 2 個子表達式相匹配的文本（如果有的話），以此類推。除了數組元素和 length 屬性之外，exec() 方法還返回兩個屬性。index 屬性聲明的是匹配文本的第一個字符的位置。input 屬性則存放的是被檢索的字符串 string。我們可以看得出，在調用非全局的 RegExp 對象的 exec() 方法時，返回的數組與調用方法 String.match() 返回的數組是相同的。
但是，當 RegExpObject 是一個全局正則表達式時，exec() 的行為就稍微復雜一些。它會在 RegExpObject 的 lastIndex 屬性指定的字符處開始檢索字符串 string。當 exec() 找到了與表達式相匹配的文本時，在匹配后，它將把 RegExpObject 的 lastIndex 屬性設置為匹配文本的最后一個字符的下一個位置。這就是說，您可以通過反復調用 exec() 方法來遍歷字符串中的所有匹配文本。當 exec() 再也找不到匹配的文本時，它將返回 null，并把 lastIndex 屬性重置為 0。
詞法分析
我們在這一部分對上面的代碼做優化。
首先是剛才提到的:當 RegExpObject 是一個全局正則表達式時，exec() 的行為就稍微復雜一些。它會在 RegExpObject 的 lastIndex 屬性指定的字符處開始檢索字符串 string。當 exec() 找到了與表達式相匹配的文本時，在匹配后，它將把 RegExpObject 的 lastIndex 屬性設置為匹配文本的最后一個字符的下一個位置。
那么我們就要考慮到沒有匹配上字符的情況，做一個判斷處理：
<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>
如上，我們對regexp.lastIndex - lastIndex 和 result[0] 的長度進行比較，判斷是否有字符串沒有匹配上。
將整個函數改成generator函數的形式，我們看下運行的結果：
語法分析
首先編寫分塊的產生式，我們看一下總的代碼結構：
<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來進行研究，它分為四種情況：
function MultiplicativeExpresson(source) { //如果是數字則進行封裝 if(source[0].type === "Number") { let node = { type: "MultiplicativeExpresson", children:[source[0]] } source[0] = 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) } 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") return source[0]; return MultiplicativeExpresson(source); }
我們看一下當source為"10 * 25 / 2"時調用console.log(MultiplicativeExpresson(source))最后運行的結果：
接下來看AdditiveExpression 本質上和MultiplicativeExpresson沒有什么不同，差異點已經標注在代碼當中了：
function AdditiveExpression(source){ if(source[0].type === "MultiplicativeExpresson") { let node = { type: "AdditiveExpression", children:[source[0]] } source[0] = 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()); //考慮到第三個數可能時Number 需要在這里再次調用一下 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) } //遞歸結束的條件 if(source[0].type === "AdditiveExpression") return source[0]; //第一次進循環 調用 MultiplicativeExpresson(source); return AdditiveExpression(source); }
我們看一下當source為"10 * 25 / 2"時調用console.log(AdditiveExpression(source))最后運行的結果：
那么Expression的代碼邏輯就很好表達了：
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); }
看下運行后的結果：
