JavaScript 的移位-归约解析器，用于代数表达式

• 下载源代码 - 33.91 KB

引言

如有需要，请参考我上一篇博文 使用解释器模式解析代数表达式。上一篇博文更侧重于使用解释器模式来处理一些有趣的事情，并作为一次很好的练习，其中可能会涉及其他设计模式的使用。然而，从解析的角度来看，它在很大程度上是临时的。我对此领域有兴趣，但没有时间深入研究。这些年来，我和我的妻子把孩子们抚养到了可以自理的年龄，我终于有了一些时间来阅读《龙书》的前半部分。

这个项目实现了与上一个项目相同的功能，但实现方式却大相径庭。此外，最初的实现存在一些不足/错误。最明显的是幂运算符的左结合性。这里的移入-移出分析器使用了一个优先级表，该表编码了运算符是左结合还是右结合。幂运算符应该是右结合的。

最显著的区别是，这个新项目在实际编译器中，其代码行数不足 400 行，尽管它只是一个非常精简的编译器。这证明了 JavaScript 的表现力。我之所以选择用 JavaScript 来实现，是因为它是一个非常实用的语言，它是浏览器的通用语言，而 HTML 5 的功能让我能够轻松地在一个很酷的图形计算器项目中演示这个编译器。

我想尽量简化对这个程序的解释，因为我无法做得像《龙书》那样好。解释将从对解释器模式的简要描述开始，并将其与程序的输出联系起来。接着介绍用于生成此输出的移入-移出算法。最后，对一些可能是新颖的 JavaScript 代码进行简要解释。

解释器模式

解释器模式用于使用一组对象来表示语法中的可能表达式。例如，对于代数表达式 4 + 4，可以使用一个 **Add** 表达式对象来表示该表达式。**Add** 表达式对象将包含对两个操作数的引用，以及评估表达式并基于这两个操作数返回值的能力。

不纠缠于文字，你可以看到如何使用表达式对象来表示各种代数表达式。此外，表达式本身可以根据定义的运算顺序作为其他表达式的操作数。考虑到这一点，代数表达式通常可以表示为表达式对象的二叉树，并通过遍历来评估。

当涉及到表示变量表达式时，情况会变得有些棘手，因为变量表达式的评估会根据变量的当前值而变化。解释器模式通过定义一个上下文类来解决这个问题，该类提供当前在被评估的表达式中可能出现的变量的值。这个上下文对象从树的根节点传递下来，通过连续的操作数评估，无论它是否在给定层级中使用。这样，上下文就可以在树的任何地方按需提供。

对于本项目而言，上述树的根节点就是解析的最终输出。一旦获得根表达式对象，就会对其进行连续评估，从而生成代数表达式的图形。

移入-移出分析（Shift-Reduce Parsing）

如果你听说过 LR 解析，那么你应该知道 LR 解析是一种移入-移出分析。移入-移出是一种通用术语，适用于任何使用堆栈、具有移入操作以及某种形式的归约的解析方法。实现完整的 LR 解析是一项艰巨的任务。我最初的目的是做到这一点，直到我了解到 运算符优先级解析。我希望编写一个很好的解析器的语法符合运算符优先级语法，因此适合更简单的解析技术而不是 LR。我认为运算符优先级解析是手持计算器中标准的移入-移出解析方法。

要使一个语法符合运算符优先级语法，它的产生式右侧不能有两个连续的非终结符，也不能有任何空产生式。大致来说，本项目使用的语法如下：

E -> E + E | E - E | E * E | E / E | E ^ E | (E) | ~E | FUNC E | NUMBER | VARIABLE

上述语法是模糊的。消除语法歧义有多种方法，以便为要使用的解析算法做好准备，包括引入级别来强制执行优先级关系。运算符优先级解析本身并不消除语法的歧义，而是使用优先级表来指导解析的连续步骤。它不仅有助于建立优先级，还可以编码具有相同优先级的运算符的结合性规则，并指示错误。

需要提的一点是“~”一元运算符的存在。这是为了将其与二元减法运算区分开，而不必为解析器编写特殊情况代码。我发现书中解决此问题的方法是让扫描器在将负号“-”符号提供给解析器之前将其转换为“~”。这消除了解析器中的特殊情况处理，但导致扫描器中出现一个不好看的 if 语句。

通常，移入-移出分析器的输出会是另一种以后缀表示法表示的表达式，该表达式易于通过另一个堆栈进行评估。在本例中，我如上所述采用了解释器模式。因此，归约步骤是关于将项绑定为操作数到表达式实例。最终，通过这种方式构建了一个树，解析器的输出就是树的根节点。

上述解释是有限的。我很乐意回答您关于解析背后的理论及其工作原理的任何问题，但要全面详细地解释它将是一项艰巨的任务。所以，我将尽我所能来填补可能存在的不足。

JavaScript

这里使用的大部分 JavaScript 都相当标准，除了书中 Douglas Crockford 的著作《 JavaScript: The Good Parts》中所称的**模块模式**（Module Pattern）的一种惯用法。他的总体观点是，JavaScript 是一种出色的原型语言，应该以这种方式使用，而不是试图将其强行改造成面向对象的语言。**模块模式**可算作是按照 JavaScript 的预期方式来使用 JavaScript。在此模式中，定义一个函数，并在其中定义局部变量。在这段代码中，我使用了“_”约定来表示它们在某种意义上是私有的。接下来，函数定义一个对象，并为该对象分配属性和方法，这些属性和方法可以访问刚刚定义的局部变量。然后返回该对象。由于 JavaScript 中的词法作用域，当返回对象的函数被调用时，它们将记住定义它们的词法环境，并能够访问这些局部变量。这通常被称为闭包。

var scanner = function () {
    var _expressionTypes = [];
    
    var result = {};

    result.add_expressionType = function (expressionType) {
        _expressionTypes.push(expressionType);
    }
    ...
    return result;
}

要在更广泛的上下文中理解闭包，请查看静态（词法作用域）与动态作用域。动态作用域通常基于运行时函数调用顺序确定的当前激活记录堆栈，而静态作用域则基于程序的词法结构。上面在 scanner 函数定义中定义的 add_expressionType 函数可以访问 _expressionTypes 变量，因为它在 **静态** 作用域中。即使在 scanner 函数调用完成后，这种关系也得以维持。可以说，这种关系是通过一个称为闭包的实体来维持的，它是实现词法作用域的一种方式。在更广泛的上下文中理解闭包，有助于更容易地理解和将它们归档到你的知识库中。许多关于闭包的文章似乎都回避了基本原理，并将它们描述得好像某种魔法生物。它们存在已久，Java 和 C# 使用闭包或类似闭包的结构也并非新鲜事。

代码

这个项目的组织结构很简单。有一个 default.html 文件和两个文件夹，这两个文件夹需要与 default.html 放在同一个目录下。一个文件夹包含脚本，另一个文件夹包含样式。包含分析器脚本的文件是 compiler.js。在任何符合 HTML 5 标准的浏览器中打开 default.html 文件，它应该都能正常工作。请记住，IE 9 不符合 HTML 5 标准。我确信，通过一个恰当的 if 语句，我可以在 IE 9 中使其工作，但此时我已决定按照标准进行编码，而不考虑 IE 的兼容性。它确实能在所有其他符合 HTML 5 标准的现代浏览器中正常工作。我的观点是，如果你想让网络正常工作，就不应该使用 IE。

我做这个项目的目的是为了享受乐趣，也为了享受分享。考虑到这一点，我不喜欢编写处理错误的。因此，请确保在点击 **Plot** 按钮之前，填写所有 3 个表单字段，并使其包含有意义的内容。

历史

• 2011 年 9 月 26 日：初始版本