社群
學習
工具庫
AI工具
休閒
搜尋
繁体中文
首頁 web前端 js教程 談JS實作AST抽象語法樹問題

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

coldplay.xixi
coldplay.xixi
Feb 19, 2021 pm 05:45 PM
javascript

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

本網站聲明
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

顯示更多

熱門文章

Windows 11 KB5054979中的新功能以及如何解決更新問題
3 週前 By DDD
如何修復KB5055523無法在Windows 11中安裝？
2 週前 By DDD
Inzoi：如何申請學校和大學
3 週前 By DDD
如何修復KB5055518無法在Windows 10中安裝？
2 週前 By DDD
Roblox：Dead Rails - 如何召喚和擊敗Nikola Tesla
4 週前 By 尊渡假赌尊渡假赌尊渡假赌
顯示更多

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

顯示更多

熱門話題

gmail信箱登陸入口在哪裡
7821
15
Java教學
1647
14
CakePHP 教程
1402
52
Laravel 教程
1300
25
PHP教程
1238
29
顯示更多
Related knowledge
如何使用WebSocket和JavaScript實現線上語音辨識系統 如何使用WebSocket和JavaScript實現線上語音辨識系統 Dec 17, 2023 pm 02:54 PM

如何使用WebSocket和JavaScript實現線上語音辨識系統引言：隨著科技的不斷發展，語音辨識技術已成為了人工智慧領域的重要組成部分。而基於WebSocket和JavaScript實現的線上語音辨識系統，具備了低延遲、即時性和跨平台的特點，成為了廣泛應用的解決方案。本文將介紹如何使用WebSocket和JavaScript來實現線上語音辨識系

WebSocket與JavaScript：實現即時監控系統的關鍵技術 WebSocket與JavaScript：實現即時監控系統的關鍵技術 Dec 17, 2023 pm 05:30 PM

WebSocket與JavaScript：實現即時監控系統的關鍵技術引言：隨著互聯網技術的快速發展，即時監控系統在各個領域中得到了廣泛的應用。而實現即時監控的關鍵技術之一就是WebSocket與JavaScript的結合使用。本文將介紹WebSocket與JavaScript在即時監控系統中的應用，並給出程式碼範例，詳細解釋其實作原理。一、WebSocket技

如何利用JavaScript和WebSocket實現即時線上點餐系統 如何利用JavaScript和WebSocket實現即時線上點餐系統 Dec 17, 2023 pm 12:09 PM

如何利用JavaScript和WebSocket實現即時線上點餐系統介紹：隨著網路的普及和技術的進步，越來越多的餐廳開始提供線上點餐服務。為了實現即時線上點餐系統，我們可以利用JavaScript和WebSocket技術。 WebSocket是一種基於TCP協定的全雙工通訊協議，可實現客戶端與伺服器的即時雙向通訊。在即時線上點餐系統中，當使用者選擇菜餚並下訂單

如何使用WebSocket和JavaScript實現線上預約系統 如何使用WebSocket和JavaScript實現線上預約系統 Dec 17, 2023 am 09:39 AM

如何使用WebSocket和JavaScript實現線上預約系統在當今數位化的時代，越來越多的業務和服務都需要提供線上預約功能。而實現一個高效、即時的線上預約系統是至關重要的。本文將介紹如何使用WebSocket和JavaScript來實作一個線上預約系統，並提供具體的程式碼範例。一、什麼是WebSocketWebSocket是一種在單一TCP連線上進行全雙工

JavaScript與WebSocket：打造高效率的即時天氣預報系統 JavaScript與WebSocket：打造高效率的即時天氣預報系統 Dec 17, 2023 pm 05:13 PM

JavaScript和WebSocket：打造高效的即時天氣預報系統引言：如今，天氣預報的準確性對於日常生活以及決策制定具有重要意義。隨著技術的發展，我們可以透過即時獲取天氣數據來提供更準確可靠的天氣預報。在本文中，我們將學習如何使用JavaScript和WebSocket技術，來建立一個高效的即時天氣預報系統。本文將透過具體的程式碼範例來展示實現的過程。 We

簡易JavaScript教學：取得HTTP狀態碼的方法 簡易JavaScript教學：取得HTTP狀態碼的方法 Jan 05, 2024 pm 06:08 PM

JavaScript教學：如何取得HTTP狀態碼，需要具體程式碼範例前言：在Web開發中，經常會涉及到與伺服器進行資料互動的場景。在與伺服器進行通訊時，我們經常需要取得傳回的HTTP狀態碼來判斷操作是否成功，並根據不同的狀態碼來進行對應的處理。本篇文章將教你如何使用JavaScript來取得HTTP狀態碼，並提供一些實用的程式碼範例。使用XMLHttpRequest

javascript如何使用insertBefore javascript如何使用insertBefore Nov 24, 2023 am 11:56 AM

用法：在JavaScript中，insertBefore()方法用於在DOM樹中插入一個新的節點。這個方法需要兩個參數：要插入的新節點和參考節點（即新節點將要插入的位置的節點）。

JavaScript與WebSocket：打造高效率的即時影像處理系統 JavaScript與WebSocket：打造高效率的即時影像處理系統 Dec 17, 2023 am 08:41 AM

JavaScript是一種廣泛應用於Web開發的程式語言，而WebSocket則是一種用於即時通訊的網路協定。結合二者的強大功能，我們可以打造一個高效率的即時影像處理系統。本文將介紹如何利用JavaScript和WebSocket來實作這個系統，並提供具體的程式碼範例。首先，我們需要明確指出即時影像處理系統的需求和目標。假設我們有一個攝影機設備，可以擷取即時的影像數

See all articles