基于JavaScript的小型Three-Pass編譯器實(shí)現(xiàn)

lansheng228 發(fā)布于2019-08-19 17:06 / 1886人閱讀

摘要：也因此，語(yǔ)法樹(shù)生成過(guò)程異常簡(jiǎn)單，基本是和波蘭表達(dá)式生成沒(méi)區(qū)別了。這個(gè)沒(méi)啥好講的了，就是波蘭表達(dá)式的生成略改而已，改動(dòng)部分包括多了值棧和參數(shù)列表。其中立即量和參數(shù)這倆個(gè)分別是將數(shù)字和參數(shù)放入寄存器后壓棧。其他的操作則是首先分別執(zhí)行子節(jié)點(diǎn)。

前言

昨天完成了codewars上的1級(jí)題簡(jiǎn)單解釋器實(shí)現(xiàn)，今天突發(fā)奇想上去看看總共有多少1級(jí)題，然后發(fā)現(xiàn)總共也只有三題。而且，這三題都是編譯器解釋器相關(guān)的，所以干脆都做了了事。
昨天做的是簡(jiǎn)單解釋器，還有兩題分別是編譯器以及一個(gè)以類型為重點(diǎn)的不完整的類lisp解釋器。其中編譯器這題和之前做的解釋器很像，所以就從編譯器開(kāi)始吧：
題目地址：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

與前文中解釋器的差別

首先這題的復(fù)雜度比之前要低的多，所以幾十分鐘就完成了。之前題目中的語(yǔ)言還算是結(jié)構(gòu)完整，而這題里的輸入都不能算是一個(gè)語(yǔ)言，只能說(shuō)是帶參數(shù)的表達(dá)式而已。
沒(méi)有參數(shù)，沒(méi)有全局變量。相比算術(shù)表達(dá)式只多了參數(shù)而已。也因此，語(yǔ)法樹(shù)生成過(guò)程異常簡(jiǎn)單，基本是和波蘭表達(dá)式生成沒(méi)區(qū)別了。

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

Pass1

這個(gè)沒(méi)啥好講的了，就是波蘭表達(dá)式的生成略改而已，改動(dòng)部分包括多了值棧和參數(shù)列表。
另外就是對(duì)參數(shù)和立即量做了區(qū)分，這一點(diǎn)做的比前一篇要好。前一篇里面參數(shù)與立即量部分不分家?guī)?lái)了不少麻煩。

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的目的是把立即量運(yùn)算優(yōu)化掉。實(shí)現(xiàn)方式是遞歸掃描。
如果當(dāng)前節(jié)點(diǎn)是參數(shù)或立即量則直接返回當(dāng)前節(jié)點(diǎn)。
否則依次對(duì)當(dāng)前節(jié)點(diǎn)的兩個(gè)參數(shù)調(diào)用pass2。這步過(guò)后，a和b應(yīng)該都是參數(shù)或立即量。
如果a和b都是立即量，那么直接計(jì)算當(dāng)前節(jié)點(diǎn)的結(jié)果。然后用計(jì)算出的結(jié)果構(gòu)建一個(gè)新的立即量最后返回。
反之則直接返回當(dāng)前節(jié)點(diǎn)。

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"壓棧結(jié)束的。
其中立即量和參數(shù)這倆個(gè)分別是將數(shù)字和參數(shù)放入寄存器后壓棧。
其他的操作則是首先分別執(zhí)行ab子節(jié)點(diǎn)。執(zhí)行完畢后棧頂?shù)囊欢胤謩e是b,a個(gè)操作的結(jié)果。通過(guò)"PO","SW","PO"取出后執(zhí)行算術(shù)操作，最后壓棧就完成了。

需要注意的是這種方式生成的匯編代碼有大量冗余，主要是無(wú)用的["PU", "PO"]以及["PU", "IM/AR", "PU", "PO" "SW", "PO"]。
前者可以完全刪去，后者可以優(yōu)化為["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"]);
    }
};

總結(jié)

這題真是相當(dāng)簡(jiǎn)單，我待會(huì)兒去看看最后一題去，那題似乎和前兩題不太一樣。

云服務(wù)器 GPU云服務(wù)器基于javascript的webgis開(kāi)發(fā) 基于webrtc的電話回聲消除的研究與實(shí)現(xiàn) 基于webrtc的視頻會(huì)議系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 基于防火墻技術(shù)的校園網(wǎng)絡(luò)安全設(shè)計(jì)與實(shí)現(xiàn)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/78191.html