学习编译器制作是一件有趣而挑战性的事情。而今天，我们将聚焦于制作一个超小型编译器，来证明你只需要极简的代码量就能产生强大的编译器。
这篇文章将引领你完成一个基于JavaScript的超小型编译器，整个架构将极度精简，让你能够深入理解编译器的本质。
首先，就像所有编译器都做的一样，我们需要将代码分为三个阶段：解析（Parsing），转换（Transformation）和生成（Code Generation）。
代码解析是编译器读取我们编写的代码并将其转化成易于处理的嵌套的抽象语法树。转换则是基于这个语法树修改和处理中间输出的代码。最终，在代码生成阶段，编译器将重新创建一个新的代码，是原始代码的优化版本。
现在，让我们开始编写超小型编译器吧！
解析阶段
我们的编译器将以一个非常简单的语言为输入： `(add 2 (subtract 4 2))`
我们的第一步是将代码解析成一个token的数组。我们将以空格为分隔符，通过逐个检查字符并切割代码来实现这一步骤：
“`javascript
function lexer(input) {
var current = 0;
var tokens = [];
while (current < input.length) {
var char = input[current];
if (char === “(“) {
tokens.push({
type: “paren”,
value: “(“,
});
current++;
continue;
}
if (char === “)”) {
tokens.push({
type: “paren”,
value: “)”,
});
current++;
continue;
}
var WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
var NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
var value = “”;
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: “number”, value });
continue;
}
var LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
var value = “”;
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: “name”, value });
continue;
}
throw new TypeError(“I dont know what this character is: ” + char);
}
return tokens;
}
“`
现在，`lexer`函数会返回一个包含所有token的数组：`[{ type: “name”, value: “add” }, { type: “number”, value: “2” } …]`。
转换阶段
下一步是转换我们的抽象语法树。我们将当前处理的token的类型和值与期望的类型进行匹配，然后将其添加到语法树中。整个程序的抽象语法树可能会如下所示：
“`javascript
{
type: “Program”,
body: [{
type: “CallExpression”,
name: “add”,
params: [{
type: “NumberLiteral”,
value: “2”,
}, {
type: “CallExpression”,
name: “subtract”,
params: [{
type: “NumberLiteral”,
value: “4”,
}, {
type: “NumberLiteral”,
value: “2”,
}]
}]
}]
}
“`
以下是`parser`函数的实现：
“`javascript
function parser(tokens) {
var current = 0;
function walk() {
var token = tokens[current];
if (token.type === “number”) {
current++;
return {
type: “NumberLiteral”,
value: token.value,
};
}
if (token.type === “paren” && token.value === “(“) {
token = tokens[++current];
var node = {
type: “CallExpression”,
name: token.value,
params: [],
};
token = tokens[++current];
while (token.type !== “paren” || (token.type === “paren” && token.value !== “)”)) {
node.params.push(walk());
token = tokens[current];
}
current++;
return node;
}
throw new TypeError(token.type);
}
var ast = {
type: “Program”,
body: [],
};
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
“`
生成阶段
我们的转换步骤将产生一个嵌套的抽象语法树，但在现实中，我们需要将其还原成代码。所以我们需要编写代码生成器。以下是生成器的实现方式：
“`javascript
function codeGenerator(node) {
switch (node.type) {
case “Program”:
return node.body.map(codeGenerator).join(“\n”);
case “CallExpression”:
return (
codeGenerator(node.name) + “(” + node.params.map(codeGenerator).join(“, “) + “)”
);
case “NumberLiteral”:
return node.value;
case “name”:
return node.value;
default:
throw new TypeError(node.type);
}
}
“`
最后，让我们调用以上所有方法：
“`javascript
function compiler(input) {
var tokens = lexer(input);
var ast = parser(tokens);
var newCode = codeGenerator(ast);
return newCode;
}
compiler(`(add 2 (subtract 4 2))`);
“`
现在，你已经制作了一个超小型编译器，并可以在常规编译器的基础上深入了解编译原理和工作原理。
了解更多有趣的事情：https://blog.ds3783.com/