首頁 > 文章 > web前端 > 談JS實作AST抽象語法樹問題

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

coldplay.xixi轉載: 2021-02-19 17:45:212398瀏覽

談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中文網其他相關文章！

JavaScript 正则表达式 String NULL 字符串 Length operator JS console regexp 对象 input

陳述：

本文轉載於：csdn.net。如有侵權，請聯絡admin@php.cn刪除

上一篇：使用nodejs實作一個簡單的網頁爬蟲功能（附程式碼）下一篇：使用nodejs實作一個簡單的網頁爬蟲功能（附程式碼）

看更多