談JS實作AST抽象語法樹問題-js教程-PHP中文網

談JS實作AST抽象語法樹問題

免費學習推薦：javascript學習教學

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

四則運算
正規表示式
詞法分析
語法分析
完整程式碼

四則運算

首先明確，此次的程式碼都是基於LL的語法分析來實現的，實現的是四則混合運算的功能，先看下定義：
TokenNumber：
· 1 2 3 4 5 6 7 8 9 0 的組合
Operator:
- * / 之一
WhiteSpace:
<sp></sp>
LineTerminator:
<lf></lf> <cr></cr>

#看下產生式：
談JS實作AST抽象語法樹問題

##正規表示式

我們先實作正規表示式的符合原則：

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/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>

登入後複製

此時我們看一下頁面的執行列印結果：

談JS實作AST抽象語法樹問題值得一提的是這裡用到了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]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/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: &#39;EOF&#39;
        }
    }

    for (let token of tokenize("1024 + 10 * 25")) {
        console.log(token)
    }</script>

登入後複製

如上，我們對

regexp.lastIndex - lastIndex 和 result[0] 的長度比較，判斷是否有字串沒有符合。 將整個函數改成generator函數的形式，我們看下運行的結果：

談JS實作AST抽象語法樹問題

#語法分析

先寫分塊的產生式，我們來看看總的程式碼結構：

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/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: &#39;EOF&#39;
        }
    }

    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))最後執行的結果：
談JS實作AST抽象語法樹問題 # 接下來看
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))最后运行的结果：
談JS實作AST抽象語法樹問題
那么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);
 }

登入後複製

看下运行后的结果：
談JS實作AST抽象語法樹問題
以上就是所有的js解析抽象语法树的代码。

完整代码

<script>
    var regexp = /([0-9\.]+)|([ \t]+)|([\r\n]+)|(\*)|(\/)|(\+)|(\-)/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: &#39;EOF&#39;
        }
    }

    let source = [];

    for(let token of tokenize("10 * 25 / 2")) {
        if (token.type !== "Whitespace" && token.type !== "LineTerminator")
            source.push(token);
    }

    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);
    }

    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);
    }

    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);
    }

    console.log(Expression(source))</script>

登入後複製

相关免费学习推荐：javascript（视频）

以上是談JS實作AST抽象語法樹問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！