如何用 JavaScript 编写一个简单的解释器

• 下载源代码 - 2.9 KB

编写解释器和编译器

编写解释器或编译器是编程中最具教育意义的任务之一，因为您可以熟悉代码解释和评估过程的细节。您可以更深入地了解幕后发生的事情，并对语言设计背后的决策有所了解。

本文将通过展示如何为我们可以在计算器应用程序中使用的简单语言编写解释器，对该过程进行基本概述。

本文假设您具有中级编程经验和基本的 JavaScript 知识。

一些背景信息

解释器、编译器和转译器的区别

在本文中，我们将创建一个_解释器_，而不是_编译器_。我们的程序将把一些代码作为输入并立即执行它。

如果我们正在编写编译器，我们Instead 会将源语言中的输入代码转换为某种低级目标语言中的代码，例如 MSIL、汇编语言，甚至机器代码。

转译器类似于编译器，不同之处在于源语言和目标语言的抽象级别大致相同。在客户端 Web 编程世界中，一个典型的例子是 CoffeeScript，它转译成 JavaScript。

传统的语言代码解释过程

大多数编译器将通过多步过程解释代码，该过程涉及包括词法分析、预处理、解析、优化，最后是代码生成，或者，对于解释器，则是评估。

在本文中，我们将只关注词法分析、解析和评估。

词法分析

词法分析器接受一个字符串作为输入，并输出一个标记列表。例如，如果我们有这样的代码……

(12 + 4) / 6

……词法分析器会将其分成单个部分，称为标记，并输出一个可能看起来像这样的列表

[
  ["operator", "("],
  ["number", 12],
  ["operator", "+"],
  ["number", 4],
  ["operator", ")"],
  ["operator", "/"],
  ["number", 6]
]

这个过程通常相对简单。一个对字符串操作有点经验的人可以很快地构建一个词法分析器。

解析

解析器将词法分析器生成的标记列表作为输入，根据一些语法规则进行解析，并输出一个表示语法结构的解析树。

{
  operation: "/",
  left: {
    operation: "+",
    left: 12,
    right: 4
  }
  right: 6
}

这往往是过程中最困难的部分。

评估版

评估器接受解析器生成的解析树并对其进行评估。评估器通常递归地遍历解析树。给定上面的语法树，评估器可能首先评估顶级`/`操作的左操作数，然后是右操作数，然后返回除法结果。

评估左操作数将语法树简化为

{
  operation: "/",
  left: 16,
  right: 6
} 

这反过来将评估为最终结果

2.6666666666666665

AEL：计算器语言

在我们开始编写解释器之前，我们需要了解我们将要解释的语言，我刚刚创建了它，并将其称为 AEL，是算术表达式语言的缩写。

该语言以一系列算术表达式编写，由数字和算术运算符 `+` (加法)、`-` (减法和取反)、`*` (乘法)、`/` (除法)、`%` (取模)、`^` (幂运算) 以及用于分组的括号 `()` 组成。

解释器将评估每个表达式并按它们出现的顺序打印每个表达式的结果。例如，给定以下输入……

3
2 ^ 8
(12 % 7) * (3 + 2)
19 / -9 

……解释器将输出

3
256
25
-2.111111111111111

AEL 还允许您使用 `=` 运算符定义变量赋值。左侧将是某个标识符，右侧将是算术表达式。带有赋值的语句没有返回值，因此解释器不会打印相应的行。

例如

hoursPerDay = 24
minutesPerHour = 60
minutesPerDay = minutesPerHour * hoursPerDay
minutesPerDay
minutesPerDay * 60

输出

1440
86400

AEL 将有两个预定义变量：`pi` 和 `e`，它们分别对应于值 `3.141592653589793` 和 `2.718281828459045`。

最后，AEL 将允许您定义函数。函数赋值也使用 `=` 运算符，但左侧参数必须是后跟括号的标识符，括号中包含零个或多个用逗号分隔的参数名称。定义后，可以通过编写标识符名称后跟包含零个或多个用逗号分隔的算术表达式的括号来调用函数。

例如

toDegrees(radians) = radians * 180 / pi
toDegrees(2 * pi)

cylinderVolume(r, h) = pi * r ^ 2 * h
cylinderVolume(2, 4)

输出

360
50.26548245743669

现在我们知道这门语言是什么样的了，我们可以开始编写解释器了。

供参考，我已将 AEL 解释器的实现放在网上。

第一步：词法分析器

词法分析器接受文本输入并返回一个标记列表。因此，我们的 `lex` 函数的骨架应该看起来像这样

var lex = function (input) {
  var tokens = [];
  //some magic goes here
  return tokens;
};

我们有几种不同类型的标记。有运算符，由字符集 `+-*/^%=(),` 定义；有由数字组成的数字；有空白符，我们的词法分析器会忽略它；还有标识符，它们将被定义为不包含运算符、数字或空白符的任何字符串。

var isOperator = function (c) { return /[+\-*\/\^%=(),]/.test(c); },
  isDigit = function (c) { return /[0-9]/.test(c); },
  isWhiteSpace = function (c) { return /\s/.test(c); },
  isIdentifier = function (c) 
   { return typeof c === "string" && !isOperator(c) && !isDigit(c) && !isWhiteSpace(c); };

我们将创建一个简单的循环来扫描输入文本。我们将有一个变量 `c` 对应当前字符，创建一个名为 `advance` 的函数，用于在输入中向前移动一个字符并返回下一个字符，以及一个名为 `addToken` 的函数，用于将标记添加到标记列表中。

var tokens = [], c, i = 0;
var advance = function () { return c = input[++i]; };
var addToken = function (type, value) {
  tokens.push({
    type: type,
    value: value
 });
};
while (i < input.length) {
  c = input[i];
  //...
}

如果 `c` 是空白符，我们只需忽略它并继续。如果 `c` 是运算符，则将运算符标记添加到列表中并继续。

if (isWhiteSpace(c)) advance();
else if (isOperator(c)) {
  addToken(c);
  advance();
}

为简单起见，我们将数字定义为一系列数字，可选地后跟小数点和另一系列数字。

else if (isDigit(c)) {
  var num = c;
  while (isDigit(advance())) num += c;
  if (c === ".") {
    do num += c; while (isDigit(advance()));
  }
  num = parseFloat(num);
  if (!isFinite(num)) throw "Number is too large or too small for a 64-bit double.";
  addToken("number", num);
}

所有其他字符都是标识符。

else if (isIdentifier(c)) {
  var idn = c;
  while (isIdentifier(advance())) idn += c;
  addToken("identifier", idn);
}

而且，以防万一出现奇怪的东西

else throw "Unrecognized token."; 

扫描输入完成后，我们将添加一个标记来表示结束。然后我们就完成了。

addToken("(end)");
return tokens;

第二步：解析器

编写解析器有很多不同的策略。最常见的一种是编写 Backus-Naur 语法并使用 递归下降。在本文中，我们将使用一种不那么常见的策略，称为 运算符优先级解析，使用 Douglas Crockford 的 自顶向下运算符优先级 文章中描述的技术。

运算符优先级解析始于以下过程

• 将每个操作符标记与一个左绑定力和一个操作函数相关联。
• 如果运算符操作其左侧的标记（例如 `+`），则将其与左指称函数（以下简称 `led`）相关联。如果运算符不操作其左侧的标记（例如一元 `-`），则将其与 `null` 指称函数（以下简称 `nud`）相关联。标识符和数字也与 `nud` 函数相关联。

完成此操作后，它就可以开始生成解析树了。为了展示其工作原理，我将使用下面的算术表达式作为示例。

12 + 4 / 6

解析器函数通过执行第一个标记 (`12`) 的 `nud` 开始，该函数返回其自身。

{ type: "number", value: 12 }

这成为我们传递给下一个标记（`+`）的 `led` 的左侧，它将递归调用解析器函数来解析剩余的标记。

{
  type: "+",
  left: { type: "number", value: 12 },
  right: //parse remaining tokens
}

我们通过调用剩余标记（`4`）中第一个标记的 `nud` 来重新开始，它将返回自身。

{ type: "number", value: 4 }

这成为我们传递给下一个标记 (/) 的 led 的左侧，它将递归调用解析器函数来解析剩余的标记。

{
  type: "+",
  left: { type: "number", value: 12 },
  right: {
    type: "/"
    left: { type: "number", value: 4 },
    right: //parse remaining tokens
  }
}

我们调用剩余标记（`6`）中第一个标记的 `nud`，它将返回自身。这是标记列表的末尾，因此解析树已完成。

{
  type: "+",
  left: { type: "number", value: 12 },
  right: {
    type: "/"
    left: { type: "number", value: 4 },
    right: { type: "number", value: 6 }
  }
}

如果我们现在切换 `+` 和 `/`，我们将看到绑定力是如何发挥作用的。`/` 具有比 `+` 更高的绑定力，因此它将更紧密地绑定到它周围的操作数。

12 / 4 + 6

我们像以前一样开始

{
  type: "/",
  left: { type: "number", value: 12 },
  right: //parse remaining tokens
}

但这次，在我们调用 `4` 的 `nud` 之后，我们将提前看一个标记，发现 `+` 的优先级低于 `/`。这意味着我们将 `4` 放到右侧，然后将整个当前树传递给 `+` 的 led，这使我们得到这个解析树

{
  type: "+",
  left: {
    type: "/",
    left: { type: "number", value: 12 },
    right: { type: "number", value: 4 }
  },
  right: { type: "number", value: 6 },
}

现在我们对解析过程有了一些了解，我们可以开始编写解析器了。解析器接受词法分析器产生的标记，并返回一个解析树，因此我们的 `parse` 函数的骨架将如下所示

var parse = function (tokens) {
 var parseTree = [];
 //some magic
 return parseTree;
};

我们需要一个符号表来将符号与绑定力、nud 或 led 关联起来，并且我们需要一个函数来将标记与相应的符号关联起来。

var symbols = {},
symbol = function (id, nud, lbp, led) {
  var sym = symbols[id] || {};
  symbols[id] = {
    lbp: sym.lbp || lbp,
    nud: sym.nud || nud,
    led: sym.led || led
  };
};

var interpretToken = function (token) {
  var sym = Object.create(symbols[token.type]);
  sym.type = token.type;
  sym.value = token.value;
  return sym;
};

我们需要某种方式来查看当前标记，以及一种前进到下一个标记的方式。

var i = 0, token = function () { return interpretToken(tokens[i]); };
var advance = function () { i++; return token(); };

现在我们可以编写一个表达式函数，它将根据上述描述的方式生成表达式的解析树

var expression = function (rbp) {
  var left, t = token();
  advance();
  if (!t.nud) throw "Unexpected token: " + t.type;
  left = t.nud(t);
  while (rbp < token().lbp) {
    t = token();
    advance();
    if (!t.led) throw "Unexpected token: " + t.type;
  left = t.led(left);
 }
 return left;
};

现在我们可以创建中缀和前缀函数，我们将能够用它们来定义运算符

var infix = function (id, lbp, rbp, led) {
  rbp = rbp || lbp;
  symbol(id, null, lbp, led || function (left) {
    return {
      type: id,
      left: left,
      right: expression(rbp)
    };
  });
},
prefix = function (id, rbp) {
  symbol(id, function () {
    return {
      type: id,
      right: expression(rbp)
    };
  });
};

现在我们可以声明式地定义所有的算术运算符。请注意，幂运算符（`^`）的右绑定力小于其左绑定力。这是因为幂运算是右结合的。

prefix("-", 7);
infix("^", 6, 5);
infix("*", 4);
infix("/", 4);
infix("%", 4);
infix("+", 3);
infix("-", 3);

有些运算符只是作为分隔或结束标记而存在。它们不是前缀或中缀，因此将它们添加到符号表中就足够了。

symbol(",");
symbol(")");
symbol("(end)");

括号 `nud` 只返回其内部内容，而数字 `nud` 只返回其自身。

symbol("(", function () {
  value = expression(2);
  if (token().type !== ")") throw "Expected closing parenthesis ')'";
  advance();
  return value;
});
symbol("number", function (number) {
    return number;
});

标识符 `nud` 和 `=` 运算符的 `nud` 更复杂，因为它们具有依赖于上下文的行为。

symbol("identifier", function (name) {
  if (token().type === "(") {
    var args = [];
    if (tokens[i + 1].type === ")") advance();
    else {
      do {
        advance();
        args.push(expression(2));
      } while (token().type === ",");
      if (token().type !== ")") throw "Expected closing parenthesis ')'";
    }
    advance();
    return {
      type: "call",
      args: args,
      name: name.value
    };
  }
  return name;
});
infix("=", 1, 2, function (left) {
    if (left.type === "call") {
      for (var i = 0; i < left.args.length; i++) {
        if (left.args[i].type !== "identifier") throw "Invalid argument name";
      }
      return {
        type: "function",
        name: left.name,
        args: left.args,
        value: expression(2)
      };
    } else if (left.type === "identifier") {
      return {
        type: "assign",
        name: left.value,
        value: expression(2)
      };
    }
    else throw "Invalid lvalue";
});

现在所有的困难都解决了，我们可以进行最后的收尾工作。

var parseTree = [];
while (token().type !== "(end)") {
  parseTree.push(expression(0));
}
return parseTree;

第三步：评估器

评估器接受解析器生成的解析树，评估每个项，并产生评估后的输出。我们的评估器函数的骨架将如下所示

var evaluate = function (parseTree) {
  var parseNode = function (node) {
  //magic goes here
  };
  var output = "";
  for (var i = 0; i < parseTree.length; i++) {
    var value = parseNode(parseTree[i]);
    if (typeof value !== "undefined") output += value + "\n";
  }
  return output;
};

定义运算符以及所有预定义变量和函数的行为非常简单

var operators = {
    "+": function(a, b) {
        return a + b;
    },
    "-": function(a, b) {
        if (typeof b === "undefined") return -a;
        return a - b;
    },
    "*": function(a, b) {
        return a * b;
    },
    "/": function(a, b) {
        return a / b;
    },
    "%": function(a, b) {
        return a % b;
    },
    "^": function(a, b) {
        return Math.pow(a, b);
    }
};

var variables = {
    pi: Math.PI,
    e: Math.E
};

var functions = {
    sin: Math.sin,
    cos: Math.cos,
    tan: Math.cos,
    asin: Math.asin,
    acos: Math.acos,
    atan: Math.atan,
    abs: Math.abs,
    round: Math.round,
    ceil: Math.ceil,
    floor: Math.floor,
    log: Math.log,
    exp: Math.exp,
    sqrt: Math.sqrt,
    max: Math.max,
    min: Math.min,
    random: Math.random
};
var args = {};

现在我们可以把评估器的核心代码放进去，然后我们就完成了。`parseNode` 函数递归遍历并评估解析树。

var parseNode = function (node) {
  if (node.type === "number") return node.value;
  else if (operators[node.type]) {
    if (node.left) return operators[node.type](parseNode(node.left), parseNode(node.right));
    return operators[node.type](parseNode(node.right));
  }
  else if (node.type === "identifier") {
    var value = args.hasOwnProperty(node.value) ? args[node.value] : variables[node.value];
    if (typeof value === "undefined") throw node.value + " is undefined";
    return value;
  }
  else if (node.type === "assign") {
    variables[node.name] = parseNode(node.value);
  }
  else if (node.type === "call") {
    for (var i = 0; i < node.args.length; i++) node.args[i] = parseNode(node.args[i]);
    return functions[node.name].apply(null, node.args);
  }
  else if (node.type === "function") {
    functions[node.name] = function () {
      for (var i = 0; i < node.args.length; i++) {
        args[node.args[i].value] = arguments[i];
      }
      var ret = parseNode(node.value);
      args = {};
      return ret;
    };
  }
};

整合

现在我们可以将所有内容打包，并将这三部分组合成一个单独的 `calculate` 函数。

var calculate = function (input) {
  try {
    var tokens = lex(input);
    var parseTree = parse(tokens);
    var output = evaluate(parseTree);
    return output;
  } catch (e) {
    return e;
  }
};

接下来做什么

您可以向语言中添加许多东西，使其更有用，或者只是看看它们是如何工作的。有些添加会相当容易，有些则可能非常困难。

简单的事情

• 尝试添加您自己的预定义函数。
• 调整绑定力数字，看看这如何改变表达式的评估方式。
• 允许数字字面量使用科学记数法，或者允许使用二进制或十六进制数字字面量。

中等难度

• 允许操作更多类型的数据，例如字符串、布尔值和数组。
• 允许函数有多个语句并有条件地返回值。
• 用编译器或转译器替换评估器，该编译器或转译器接受解析树并输出另一种语言的代码。
• 制作一个包管理器，允许您从其他文件导入代码。

更难的事情

• 实施优化以允许更快地执行计算。
• 使函数成为第一类公民并允许闭包。
• 使所有数据都延迟评估。

如果您知道如何做其中一些事情，您就可以开始为自己的领域特定语言制作解释器和编译器了。

就这些了，各位！

如果本文有错误，或者您觉得代码或代码解释有任何可以更容易理解的地方，请告诉我，我会相应地进行更新。

历史

• 2014年10月30日：初始版本