基于JavaScript的小型Three-Pass编译器实现

lansheng228 发布于2019-08-19 17:06 / 1698人阅读

摘要：也因此，语法树生成过程异常简单，基本是和波兰表达式生成没区别了。这个没啥好讲的了，就是波兰表达式的生成略改而已，改动部分包括多了值栈和参数列表。其中立即量和参数这俩个分别是将数字和参数放入寄存器后压栈。其他的操作则是首先分别执行子节点。

前言

昨天完成了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"]);
    }
};

总结

这题真是相当简单，我待会儿去看看最后一题去，那题似乎和前两题不太一样。

服务器托管私有云基于javascript的webgis开发基于webrtc的电话回声消除的研究与实现基于webrtc的视频会议系统的设计与实现基于防火墙技术的校园网络安全设计与实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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