免費(fèi)學(xué)習(xí)推薦：javascript學(xué)習(xí)教程

前端中的AST抽象語法樹問題

• 四則運(yùn)算
• 正則表達(dá)式
• 詞法分析
• 語法分析
• 完整代碼

四則運(yùn)算

首先明確，此次的代碼都是基于LL的語法分析來實(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ùn)行打印結(jié)果：

值得一提的是這里用到了exec方法，exec() 方法用于檢索字符串中的正則表達(dá)式的匹配。
我們看一下它的語法：
RegExpObject.exec(string)

如果 exec() 找到了匹配的文本，則返回一個(gè)結(jié)果數(shù)組。否則，返回 null。此數(shù)組的第 0 個(gè)元素是與正則表達(dá)式相匹配的文本，第 1 個(gè)元素是與 RegExpObject 的第 1 個(gè)子表達(dá)式相匹配的文本（如果有的話），第 2 個(gè)元素是與 RegExpObject 的第 2 個(gè)子表達(dá)式相匹配的文本（如果有的話），以此類推。除了數(shù)組元素和 length 屬性之外，exec() 方法還返回兩個(gè)屬性。index 屬性聲明的是匹配文本的第一個(gè)字符的位置。input 屬性則存放的是被檢索的字符串 string。我們可以看得出，在調(diào)用非全局的 RegExp 對象的 exec() 方法時(shí)，返回的數(shù)組與調(diào)用方法 String.match() 返回的數(shù)組是相同的。

但是，當(dāng) RegExpObject 是一個(gè)全局正則表達(dá)式時(shí)，exec() 的行為就稍微復(fù)雜一些。它會(huì)在 RegExpObject 的 lastIndex 屬性指定的字符處開始檢索字符串 string。當(dāng) exec() 找到了與表達(dá)式相匹配的文本時(shí)，在匹配后，它將把 RegExpObject 的 lastIndex 屬性設(shè)置為匹配文本的最后一個(gè)字符的下一個(gè)位置。這就是說，您可以通過反復(fù)調(diào)用 exec() 方法來遍歷字符串中的所有匹配文本。當(dāng) exec() 再也找不到匹配的文本時(shí)，它將返回 null，并把 lastIndex 屬性重置為 0。

詞法分析

我們在這一部分對上面的代碼做優(yōu)化。
首先是剛才提到的:
當(dāng) RegExpObject 是一個(gè)全局正則表達(dá)式時(shí)，exec() 的行為就稍微復(fù)雜一些。它會(huì)在 RegExpObject 的 lastIndex 屬性指定的字符處開始檢索字符串 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>

如上，我們對regexp.lastIndex - lastIndex 和 result[0] 的長度進(jìn)行比較，判斷是否有字符串沒有匹配上。
將整個(gè)函數(shù)改成generator函數(shù)的形式，我們看下運(yùn)行的結(jié)果：

語法分析

首先編寫分塊的產(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來進(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)      }       //如果是乘號或者除號，則將三項(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é)果：

接下來看AdditiveExpression 本質(zhì)上和MultiplicativeExpresson沒有什么不同，差異點(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)         }          //如果是乘號或者除號，則將三項(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é)果：