基于JavaScript的小型Three-Pass編譯器實現

lansheng228 發布于2019-08-19 17:06 / 1892人閱讀

摘要：也因此，語法樹生成過程異常簡單，基本是和波蘭表達式生成沒區別了。這個沒啥好講的了，就是波蘭表達式的生成略改而已，改動部分包括多了值棧和參數列表。其中立即量和參數這倆個分別是將數字和參數放入寄存器后壓棧。其他的操作則是首先分別執行子節點。

前言

昨天完成了codewars上的1級題簡單解釋器實現，今天突發奇想上去看看總共有多少1級題，然后發現總共也只有三題。而且，這三題都是編譯器解釋器相關的，所以干脆都做了了事。
昨天做的是簡單解釋器，還有兩題分別是編譯器以及一個以類型為重點的不完整的類lisp解釋器。其中編譯器這題和之前做的解釋器很像，所以就從編譯器開始吧：
題目地址：http://www.codewars.com/kata/tiny-three-pass-compiler/train/javascript
github地址：https://github.com/woodensail/SimpleInteractiveInterpreter/blob/master/tiny-three-pass-compiler.js
前文地址：http://segmentfault.com/a/1190000004047915
本文地址：http://segmentfault.com/a/1190000004049048

與前文中解釋器的差別

首先這題的復雜度比之前要低的多，所以幾十分鐘就完成了。之前題目中的語言還算是結構完整，而這題里的輸入都不能算是一個語言，只能說是帶參數的表達式而已。
沒有參數，沒有全局變量。相比算術表達式只多了參數而已。也因此，語法樹生成過程異常簡單，基本是和波蘭表達式生成沒區別了。

這題比之前多出的部分則是語義分析和匯編代碼生成。
語義分析部分需要將常量運算優化掉，縮短代碼長度。
匯編代碼生成部分取代了前一題的執行部分。而是生成并返回匯編代碼即可。

Pass1

這個沒啥好講的了，就是波蘭表達式的生成略改而已，改動部分包括多了值棧和參數列表。
另外就是對參數和立即量做了區分，這一點做的比前一篇要好。前一篇里面參數與立即量部分不分家帶來了不少麻煩。

Compiler.prototype.pass1 = function (program) {
    var tokens = this.tokenize(program), index = tokens.indexOf("]"), args = {}, next, dataStack = [];
    operatorStack = [];
    for (var i = 1; i < index; i++) {
        args[tokens[i]] = i - 1;
    }
    tokens = tokens.slice(index + 1);
    tokens.unshift("(");
    tokens.push(")");
    while ((next = tokens.pop()) !== void 0) {
        if (operators[next]) {
            while (true) {
                if (!operatorStack.length) {
                    operatorStack.push(next);
                    break;
                } else if (operatorStack[operatorStack.length - 1] === ")") {
                    operatorStack.push(next);
                    break;
                } else if (operators[operatorStack[operatorStack.length - 1]] >= operators[next]) {
                    operatorStack.push(next);
                    break;
                } else {
                    dataStack.push({op: operatorStack.pop(), a: dataStack.pop(), b: dataStack.pop()});
                }
            }
        } else if (next === "(") {
            while ((next = operatorStack.pop()) !== ")") {
                if (next === void 0) {
                    break
                }
                dataStack.push({op: next, a: dataStack.pop(), b: dataStack.pop()});
            }
        } else if (next === ")") {
            operatorStack.push(next);
        } else {
            if (args[next] !== void 0) {
                dataStack.push({op: "arg", n: args[next]});
            } else {
                dataStack.push({op: "imm", n: Number(next)});
            }
        }
    }
    return dataStack[0];
};

Pass2

pass2的目的是把立即量運算優化掉。實現方式是遞歸掃描。
如果當前節點是參數或立即量則直接返回當前節點。
否則依次對當前節點的兩個參數調用pass2。這步過后，a和b應該都是參數或立即量。
如果a和b都是立即量，那么直接計算當前節點的結果。然后用計算出的結果構建一個新的立即量最后返回。
反之則直接返回當前節點。

Compiler.prototype.pass2 = function (ast) {
    if ((ast.op === "arg") || (ast.op === "imm")) {
        return ast;
    }
    ast.a = this.pass2(ast.a);
    ast.b = this.pass2(ast.b);
    if ((ast.a.op === "imm") && (ast.b.op === "imm")) {
        return {op: "imm", n: this.execOp(ast.op, ast.a.n, ast.b.n)}
    } else {
        return ast;
    }
};

Pass3

首先所有操作都是以"PU"壓棧結束的。
其中立即量和參數這倆個分別是將數字和參數放入寄存器后壓棧。
其他的操作則是首先分別執行ab子節點。執行完畢后棧頂的一二元素分別是b,a個操作的結果。通過"PO","SW","PO"取出后執行算術操作，最后壓棧就完成了。

需要注意的是這種方式生成的匯編代碼有大量冗余，主要是無用的["PU", "PO"]以及["PU", "IM/AR", "PU", "PO" "SW", "PO"]。
前者可以完全刪去，后者可以優化為["SW" , "IM/AR", "SW"]。

Compiler.prototype.pass3 = function (ast) {
    switch (ast.op) {
        case "imm":
            return ["IM " + ast.n, "PU"];
        case "arg":
            return ["AR " + ast.n, "PU"];
        case "+":
            return this.pass3(ast.a).concat(this.pass3(ast.b)).concat(["PO", "SW", "PO", "AD", "PU"]);
        case "-":
            return this.pass3(ast.a).concat(this.pass3(ast.b)).concat(["PO", "SW", "PO", "SU", "PU"]);
        case "*":
            return this.pass3(ast.a).concat(this.pass3(ast.b)).concat(["PO", "SW", "PO", "MU", "PU"]);
        case "/":
            return this.pass3(ast.a).concat(this.pass3(ast.b)).concat(["PO", "SW", "PO", "DI", "PU"]);
    }
};

總結

這題真是相當簡單，我待會兒去看看最后一題去，那題似乎和前兩題不太一樣。

GPU云服務器云服務器基于javascript的webgis開發基于webrtc的電話回聲消除的研究與實現基于webrtc的視頻會議系統的設計與實現基于防火墻技術的校園網絡安全設計與實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/78191.html

前端每周清單半年盤點之 WebAssembly 篇

摘要：前端每周清單專注前端領域內容，以對外文資料的搜集為主，幫助開發者了解一周前端熱點分為新聞熱點開發教程工程實踐深度閱讀開源項目巔峰人生等欄目。利用降低三倍加載速度自推出之后，很多開發者都開始嘗試在小型項目中實踐，不過尚缺大型真實案例比較。前端每周清單專注前端領域內容，以對外文資料的搜集為主，幫助開發者了解一周前端熱點；分為新聞熱點、開發教程、工程實踐、深度閱讀、開源項目、巔峰人生等欄目...

Alan 2019-08-22 11:07 評論0 收藏0
DevOps 基于Walle的小型持續集成實戰（六）基于Walle發布前端React,Angular

摘要：本章用于講解如何在下構建和運行前端應用。項目配置服務名稱鏡像版本映射容器端口到本地端口數據卷映射本地文件到容器映射文件到容器的目錄并覆蓋文件映射文件夾到容器的文件夾覆蓋容器啟動后默認執行的命令。環境準備參考文檔本章用于講解如何在walle下構建和運行前端應用。主要包含React,Angular應用，以Nginx+Docker運行（Vue方式不講，大家自行研究）新建項目項目中心 >...

tuomao 2019-06-28 17:21 評論0 收藏0
DevOps 基于Walle的小型持續集成實戰（二）設計

摘要：以便對整個持續集成印象加深。配置完各環境發布腳本后，則可以使用構建發起進行觸發環境準備。并會在遠程環境上存放多次發布的版本，用于回退和切換服務停用。進行等操作，停止原本運行的服務切換啟用。該文章用于建立一個小型的基于Walle的持續集成工具。解決java,react,angular項目的編譯發布。以便對整個持續集成印象加深。官方網站：https://walle-web.io/ 適用...

zr_hebo 2019-06-28 17:22 評論0 收藏0
15個有趣的JavaScript與CSS庫

摘要：而調試器具有對模型控制器以及視圖的實時管理權限。項目地址是一個輕量級純寫的文本工具提示庫。它支持種不同國家的貨幣格式，以及超過種不同語言的本地化設置。項目地址是一個根據規范構建的輕量級框架。它壓縮后僅有，同時它沒有預先設定的元素和內置動畫。在十一月份的前端技術列表中，我們整合了一些令人感到驚嘆的 GitHub 項目，其中包含了新的 CSS 框架、node.js包管理器，以及用于實現圖...

chemzqm 2019-08-30 13:15 評論0 收藏0
15個有趣的JavaScript與CSS庫

摘要：而調試器具有對模型控制器以及視圖的實時管理權限。項目地址是一個輕量級純寫的文本工具提示庫。它支持種不同國家的貨幣格式，以及超過種不同語言的本地化設置。項目地址是一個根據規范構建的輕量級框架。它壓縮后僅有，同時它沒有預先設定的元素和內置動畫。在十一月份的前端技術列表中，我們整合了一些令人感到驚嘆的 GitHub 項目，其中包含了新的 CSS 框架、node.js包管理器，以及用于實現圖...

wangjuntytl 2019-08-22 11:02 評論0 收藏0