在github 上看到一个超级小的编译器实现，看了一下具体实现，大概了解了编译器的实现逻辑，这里分享给大家。
今天，我们将一起编写一个编译器。不过，这不是任何普通的编译器……这是一个超级超级小的编译器！这个编译器小到，如果你把所有注释都删掉，真正的代码只有大约200行。
我们即将将一些类似LISP的函数调用编译成一些类似C的函数调用。
如果你对这两种语言都不太熟悉，我会快速介绍一下。
假如我们有两个函数 add 和 subtract，它们的写法如下：
LISP C
2 + 2 (add 2 2) add(2, 2)
4 - 2 (subtract 4 2) subtract(4, 2)
2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))
很简单，对吧？
那很好，因为这正是我们要编译的内容。虽然这既不完全符合LISP也不完全符合C的语法，但它足以演示现代编译器的许多主要部分。
大多数编译器分为三个主要阶段：解析、转换和代码生成。
-
解析，即将原始代码转换成更抽象的代码表示形式。
-
转换，即对这种抽象表示进行操作，完成编译器想要完成的任何任务。
-
代码生成，即将转换后的代码表示转换成新的代码。
核心截断
解析
解析通常分为两个阶段：词法分析和句法分析。
-
词法分析，将原始代码分割成所谓的tokens，这一过程由一个称为 tokenizer（或lexer）的工具完成。
Tokens是描述语法的孤立部分的一系列小对象。他们可以是数字、标签、标点、操作符等。
-
句法分析，将 tokens 重新组织成一种表示语法各部分及其相互关系的形式。这种表示称为中间表示或抽象语法树（AST）。
抽象语法树（AST）是一个深度嵌套的对象，它以易于操作的方式表示代码，并提供大量信息。
对于如下语法：
(add 2 (subtract 4 2))
Tokens可能如下所示：
[
{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' },
]
而抽象语法树（AST）可能如下所示：
{
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',
}]
}]
}]
}
转换
编译器的下一个阶段是转换。这个阶段接着解析阶段，对AST进行修改。这可以是在相同的语言中对AST进行操作，也可以是将其转换成全新的语言。
来看看我们怎么转换一个AST。
你会注意到我们的AST中含有许多看起来非常相似的元素。这些带有类型属性的对象被称为AST节点。这些节点定义了树的一个独立部分。
我们可以有一个"NumberLiteral"节点：
{
type: 'NumberLiteral',
value: '2',
}
或者一个"CallExpression"节点：
{
type: 'CallExpression',
name: 'subtract',
params: [...这里嵌套其他节点...],
}
在转换AST时，我们可以通过添加/删除/替换属性来操作节点，可以添加新节点，删除节点，或者基于现有AST创建一个全新的AST。
由于我们的目标是转换成另一种语言，我们将专注于创建一个特定于目标语言的全新AST。
遍历
为了能遍历所有节点，我们需要能够穿梭于它们之间。这个遍历过程按照深度优先的方式访问AST中的每个节点。
因此，对于上述AST，我们的遍历过程是这样的：
-
- Program - 从AST的最顶层开始
-
- CallExpression (add) - 移至Program体的第一个元素
-
- NumberLiteral (2) - 移至CallExpression的参数的第一个元素
-
- CallExpression (subtract) - 移至CallExpression的参数的第二个元素
-
- NumberLiteral (4) - 移至CallExpression的参数的第一个元素
-
- NumberLiteral (2) - 移至CallExpression的参数的第二个元素
如果我们直接操作这个AST，而不是创建一个新的，我们可能会在这里引入许多抽象概念。但仅仅访问树中的每一个节点对于我们要完成的任务已经足够了。
我们使用“访问”一词是因为存在一种模式，用于表示对对象结构中元素的操作。
访问者
基本思想是，我们创建一个“访问者”对象，它包含了一些方法，这些方法会接受不同类型的节点。
当我们遍历AST时，我们会在“进入”匹配类型的节点时调用这些方法。
为了使这个机制有用，我们还会向这些方法传递节点和其父节点的引用。
然而，我们也可能在“离开”节点时进行操作。想象我们之前的树结构，以列表形式表示：
在遍历树时，我们会“进入”每个节点，而在遍历完成后“离开”。
我们的访问者最终会包含一些方法，既在“进入”时调用，也在“离开”时调用。
代码生成
编译器的最终阶段是代码生成。尽管有时编译器的这一阶段会与转换阶段重叠，但大多数情况下，代码生成只涉及将我们的AST转换回代码字符串。
代码生成器有几种不同的工作方式，有些编译器会重用之前的tokens，有些可能会创建代码的一个单独的表示形式，以便它们可以线性地输出节点，但据我所知，大多数编译器都会使用我们刚刚创建的同一个AST。
实际上，我们的代码生成器将知道如何“打印”AST中的所有不同节点类型，并将递归调用自身以打印嵌套节点，直到所有内容都被打印成一个长字符串的代码。
就是这样！这就是一个编译器的所有不同部分。
当然，并不是每个编译器都会像我这里描述的这样。编译器服务于多种不同的目的，它们可能需要比我这里详细介绍的更多步骤。
但现在，你应该对大多数编译器的大致框架有了一个高层次的理解。
现在我已经解释了这一切，你们准备好自己编写编译器了吗？
开个玩笑，我在这里就是为了帮助你的 :P
那么，让我们开始吧……
代码
实现
/**
* ============================================================================
* (/^▽^)/
* THE TOKENIZER!
* ============================================================================
*/
/**
* We're gonna start off with our first phase of parsing, lexical analysis, with
* the tokenizer.
*
* We're just going to take our string of code and break it down into an array
* of tokens.
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/
// We start by accepting an input string of code, and we're gonna set up two
// things...
function tokenizer(input) {
// A `current` variable for tracking our position in the code like a cursor.
let current = 0;
// And a `tokens` array for pushing our tokens to.
let tokens = [];
// We start by creating a `while` loop where we are setting up our `current`
// variable to be incremented as much as we want `inside` the loop.
//
// We do this because we may want to increment `current` many times within a
// single loop because our tokens can be any length.
while (current < input.length) {
let char = input[current];
if (char === '(') {
tokens.push({
type: 'paren',
value: '(',
});
current++;
continue;
}
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// Moving on, we're now going to check for whitespace. This is interesting
// because we care that whitespace exists to separate characters, but it
// isn't actually important for us to store as a token. We would only throw
// it out later.
//
// So here we're just going to test for existence and if it does exist we're
// going to just `continue` on.
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// The next type of token is a number. This is different than what we have
// seen before because a number could be any number of characters and we
// want to capture the entire sequence of characters as one token.
//
// (add 123 456)
// ^^^ ^^^
// Only two separate tokens
//
// So we start this off when we encounter the first number in a sequence.
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
let value = '';
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: 'number', value });
continue;
}
// We'll also add support for strings in our language which will be any
// text surrounded by double quotes (").
//
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
//
// We'll start by checking for the opening quote:
if (char === '"') {
let value = '';
// We'll skip the opening double quote in our token.
char = input[++current];
// Then we'll iterate through each character until we reach another
// double quote.
while (char !== '"') {
value += char;
char = input[++current];
}
// Skip the closing double quote.
char = input[++current];
tokens.push({ type: 'string', value });
continue;
}
// The last type of token will be a `name` token. This is a sequence of
// letters instead of numbers, that are the names of functions in our lisp
// syntax.
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: 'name', value });
continue;
}
// Finally if we have not matched a character by now, we're going to throw
// an error and completely exit.
throw new TypeError('I dont know what this character is: ' + char);
}
return tokens;
}
/**
* ============================================================================
* ヽ/❀o ل͜ o\ﾉ
* THE PARSER!!!
* ============================================================================
*/
/**
* For our parser we're going to take our array of tokens and turn it into an
* AST.
*
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
// Okay, so we define a `parser` function that accepts our array of `tokens`.
function parser(tokens) {
let current = 0;
// But this time we're going to use recursion instead of a `while` loop. So we
// define a `walk` function.
function walk() {
let token = tokens[current];
if (token.type === 'number') {
current++;
return {
type: 'NumberLiteral',
value: token.value,
};
}
// If we have a string we will do the same as number and create a
// `StringLiteral` node.
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// Next we're going to look for CallExpressions. We start this off when we
// encounter an open parenthesis.
if (
token.type === 'paren' &&
token.value === '('
) {
// We'll increment `current` to skip the parenthesis since we don't care
// about it in our AST.
token = tokens[++current];
// We create a base node with the type `CallExpression`, and we're going
// to set the name as the current token's value since the next token after
// the open parenthesis is the name of the function.
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// We increment `current` *again* to skip the name token.
token = tokens[++current];
// And now we want to loop through each token that will be the `params` of
// our `CallExpression` until we encounter a closing parenthesis.
//
// Now this is where recursion comes in. Instead of trying to parse a
// potentially infinitely nested set of nodes we're going to rely on
// recursion to resolve things.
//
// To explain this, let's take our Lisp code. You can see that the
// parameters of the `add` are a number and a nested `CallExpression` that
// includes its own numbers.
//
// (add 2 (subtract 4 2))
//
// You'll also notice that in our tokens array we have multiple closing
// parenthesis.
//
// [
// { type: 'paren', value: '(' },
// { type: 'name', value: 'add' },
// { type: 'number', value: '2' },
// { type: 'paren', value: '(' },
// { type: 'name', value: 'subtract' },
// { type: 'number', value: '4' },
// { type: 'number', value: '2' },
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// ]
//
// We're going to rely on the nested `walk` function to increment our
// `current` variable past any nested `CallExpression`.
// So we create a `while` loop that will continue until it encounters a
// token with a `type` of `'paren'` and a `value` of a closing
// parenthesis.
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// we'll call the `walk` function which will return a `node` and we'll
// push it into our `node.params`.
node.params.push(walk());
token = tokens[current];
}
// Finally we will increment `current` one last time to skip the closing
// parenthesis.
current++;
return node;
}
throw new TypeError(token.type);
}
// Now, we're going to create our AST which will have a root which is a
// `Program` node.
let ast = {
type: 'Program',
body: [],
};
// And we're going to kickstart our `walk` function, pushing nodes to our
// `ast.body` array.
//
// The reason we are doing this inside a loop is because our program can have
// `CallExpression` after one another instead of being nested.
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
/**
* ============================================================================
* ⌒(❀>◞౪◟<❀)⌒
* THE TRAVERSER!!!
* ============================================================================
*/
/**
* So now we have our AST, and we want to be able to visit different nodes with
* a visitor. We need to be able to call the methods on the visitor whenever we
* encounter a node with a matching type.
*
* traverse(ast, {
* Program: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
*
* CallExpression: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
*
* NumberLiteral: {
* enter(node, parent) {
* // ...
* },
* exit(node, parent) {
* // ...
* },
* },
* });
*/
// So we define a traverser function which accepts an AST and a
// visitor. Inside we're going to define two functions...
function traverser(ast, visitor) {
// A `traverseArray` function that will allow us to iterate over an array and
// call the next function that we will define: `traverseNode`.
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// `traverseNode` will accept a `node` and its `parent` node. So that it can
// pass both to our visitor methods.
function traverseNode(node, parent) {
// We start by testing for the existence of a method on the visitor with a
// matching `type`.
let methods = visitor[node.type];
// If there is an `enter` method for this node type we'll call it with the
// `node` and its `parent`.
if (methods && methods.enter) {
methods.enter(node, parent);
}
// Next we are going to split things up by the current node type.
switch (node.type) {
// We'll start with our top level `Program`. Since Program nodes have a
// property named body that has an array of nodes, we will call
// `traverseArray` to traverse down into them.
//
// (Remember that `traverseArray` will in turn call `traverseNode` so we
// are causing the tree to be traversed recursively)
case 'Program':
traverseArray(node.body, node);
break;
case 'CallExpression':
traverseArray(node.params, node);
break;
// In the cases of `NumberLiteral` and `StringLiteral` we don't have any
// child nodes to visit, so we'll just break.
case 'NumberLiteral':
case 'StringLiteral':
break;
default:
throw new TypeError(node.type);
}
// If there is an `exit` method for this node type we'll call it with the
// `node` and its `parent`.
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// Finally we kickstart the traverser by calling `traverseNode` with our ast
// with no `parent` because the top level of the AST doesn't have a parent.
traverseNode(ast, null);
}
/**
* ============================================================================
* ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽
* THE TRANSFORMER!!!
* ============================================================================
*/
/**
* Next up, the transformer. Our transformer is going to take the AST that we
* have built and pass it to our traverser function with a visitor and will
* create a new ast.
*
* ----------------------------------------------------------------------------
* Original AST | Transformed AST
* ----------------------------------------------------------------------------
* { | {
* type: 'Program', | type: 'Program',
* body: [{ | body: [{
* type: 'CallExpression', | type: 'ExpressionStatement',
* name: 'add', | expression: {
* params: [{ | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }, { | name: 'add'
* type: 'CallExpression', | },
* name: 'subtract', | arguments: [{
* params: [{ | type: 'NumberLiteral',
* type: 'NumberLiteral', | value: '2'
* value: '4' | }, {
* }, { | type: 'CallExpression',
* type: 'NumberLiteral', | callee: {
* value: '2' | type: 'Identifier',
* }] | name: 'subtract'
* }] | },
* }] | arguments: [{
* } | type: 'NumberLiteral',
* | value: '4'
* ---------------------------------- | }, {
* | type: 'NumberLiteral',
* | value: '2'
* | }]
* (sorry the other one is longer.) | }
* | }
* | }]
* | }
* ----------------------------------------------------------------------------
*/
// So we have our transformer function which will accept the lisp ast.
function transformer(ast) {
// We'll create a `newAst` which like our previous AST will have a program
// node.
let newAst = {
type: 'Program',
body: [],
};
// Next I'm going to cheat a little and create a bit of a hack. We're going to
// use a property named `context` on our parent nodes that we're going to push
// nodes to their parent's `context`. Normally you would have a better
// abstraction than this, but for our purposes this keeps things simple.
//
// Just take note that the context is a reference *from* the old ast *to* the
// new ast.
ast._context = newAst.body;
// We'll start by calling the traverser function with our ast and a visitor.
traverser(ast, {
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
CallExpression: {
enter(node, parent) {
// We start creating a new node `CallExpression` with a nested `Identifier`.
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
// Next we're going to define a new context on the original
// `CallExpression` node that will reference the `expression`'s arguments
// so that we can push arguments.
node._context = expression.arguments;
// Then we're going to check if the parent node is a `CallExpression`.
// If it is not...
if (parent.type !== 'CallExpression') {
// We're going to wrap our `CallExpression` node with an
// `ExpressionStatement`. We do this because the top level
// `CallExpression` in JavaScript are actually statements.
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
// Last, we push our (possibly wrapped) `CallExpression` to the `parent`'s
// `context`.
parent._context.push(expression);
},
}
});
return newAst;
}
/**
* ============================================================================
* ヾ（〃＾∇＾）ﾉ♪
* THE CODE GENERATOR!!!!
* ============================================================================
*/
/**
* Now let's move onto our last phase: The Code Generator.
*
* Our code generator is going to recursively call itself to print each node in
* the tree into one giant string.
*/
function codeGenerator(node) {
// We'll break things down by the `type` of the `node`.
switch (node.type) {
// If we have a `Program` node. We will map through each node in the `body`
// and run them through the code generator and join them with a newline.
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// For `ExpressionStatement` we'll call the code generator on the nested
// expression and we'll add a semicolon...
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...because we like to code the *correct* way)
);
// For `CallExpression` we will print the `callee`, add an open
// parenthesis, we'll map through each node in the `arguments` array and run
// them through the code generator, joining them with a comma, and then
// we'll add a closing parenthesis.
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
case 'Identifier':
return node.name;
case 'NumberLiteral':
return node.value;
case 'StringLiteral':
return '"' + node.value + '"';
default:
throw new TypeError(node.type);
}
}
/**
* ============================================================================
* (۶* ‘ヮ’)۶”
* !!!!!!!!THE COMPILER!!!!!!!!
* ============================================================================
*/
/**
* FINALLY! We'll create our `compiler` function. Here we will link together
* every part of the pipeline.
*
* 1. input => tokenizer => tokens
* 2. tokens => parser => ast
* 3. ast => transformer => newAst
* 4. newAst => generator => output
*/
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
// and simply return the output!
return output;
}
/**
* ============================================================================
* (๑˃̵ᴗ˂̵)و
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* ============================================================================
*/
// Now I'm just exporting everything...
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};
测试
const {
tokenizer,
parser,
transformer,
codeGenerator,
compiler,
} = require('./the-super-tiny-compiler');
const assert = require('assert');
const input = '(add 2 (subtract 4 2))';
const output = 'add(2, subtract(4, 2));';
const tokens = [
{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' }
];
const ast = {
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'
}]
}]
}]
};
const newAst = {
type: 'Program',
body: [{
type: 'ExpressionStatement',
expression: {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'add'
},
arguments: [{
type: 'NumberLiteral',
value: '2'
}, {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: 'subtract'
},
arguments: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}
}]
};
assert.deepStrictEqual(tokenizer(input), tokens, 'Tokenizer should turn `input` string into `tokens` array');
assert.deepStrictEqual(parser(tokens), ast, 'Parser should turn `tokens` array into `ast`');
assert.deepStrictEqual(transformer(ast), newAst, 'Transformer should turn `ast` into a `newAst`');
assert.deepStrictEqual(codeGenerator(newAst), output, 'Code Generator should turn `newAst` into `output` string');
assert.deepStrictEqual(compiler(input), output, 'Compiler should turn `input` into `output`');
console.log('All Passed!');