阅读完本文，可以收获如下内容：
在日常前端开发中，经常使用ES6+语法，但碍于用户使用的浏览器各不相同，新语法在旧版本浏览器中不支持，此时我们通常会使用babel将其转换成支持度更为广泛的ES5语法，这种“将不识别的语言转换为可识别的语言”过程就叫「编译」，所使用的工具就是编译器。除了babel，常见的编译器还有gcc等。
如果直接就看babel的源码了解编译器怎么工作的，怕是很多人都会望而却步，好在babel的维护者之一 James Kyle 有一个最小编译器的开源项目 the-super-tiny-compiler[1]，截止目前超过21.5k stars。项目去掉注释大约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)) |
大多数编译器的过程可以分为三个阶段：解析（parsing）、转换（transformation）和代码生成（code generation）:
通常解析需要经历两个步骤：词法分析（Lexical Analysis）和语法分析（Syntatic Analysis）：
接下来我们以(add 2 (subtract 4 2))为例：
词法分析器输出的结果大致如下：
[
{ 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: ')' },
]想到得到这样的结果，就需要拆分输入，并进行匹配。
/**
* 词法分析器
* @param input 代码字符串
* @returns token列表
*/
function tokenizer(input) {
// 输入字符串处理的索引
let current = 0;
// token列表
let tokens = [];
// 遍历字符串，解析token
while (current < input.length) {
let char = input[current];
// 匹配左括号
if (char === '(') {
// type 为 'paren'，value 为左圆括号的对象
tokens.push({
type: 'paren',
value: '(',
});
// current 自增
current++;
// 结束本次循环，进入下一次循环
continue;
}
// 匹配右括号
if (char === ')') {
// type 为 'paren'，value 为右圆括号的对象
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
let WHITESPACE = /\s/;
// 正则匹配空白字符，跳过空白字符
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 匹配如下数字
// (add 123 456)
// ^^^ ^^^
let NUMBERS = /[0-9]/;
// 正则匹配数字
if (NUMBERS.test(char)) {
let value = '';
// 匹配连续数字，作为value
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// type 为 'number'，value 为数字字符串
tokens.push({
type: 'number',
value,
});
continue;
}
// 匹配如下字符串，以""包裹
// (concat "foo" "bar")
// ^^^ ^^^
if (char === '"') {
let value = '';
// 跳过左双引号
char = input[++current];
// 获取双引号之间的所有字符串
while (char !== '"') {
value += char;
char = input[++current];
}
// 跳过右双引号
char = input[++current];
// type 为 'string'，value 为字符串参数
tokens.push({
type: 'string',
value,
});
continue;
}
// 匹配函数名
// (add 2 4)
// ^^^
let LETTERS = /[a-z]/i;
// 只包含小写字母
if (LETTERS.test(char)) {
let value = '';
// 获取连续字符
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// type 为 'name'，value 为函数名
tokens.push({
type: 'name',
value,
});
continue;
}
// 无法识别的字符，抛出错误提示
throw new TypeError(`I dont know what this character is: ${char}`);
}
// 返回词法分析器token列表
return tokens;
}词法分析完成后，还需要经过语法分析器，将token列表转成如下的抽象语法树（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',
},
],
},
],
},
],
}语法分析器的实现逻辑如下：
/**
* 语法分析器
* @param {*} tokens token列表
* @returns 抽象语法树 AST
*/
function parser(tokens) {
// token列表索引
let current = 0;
// 采用递归的方式遍历token列表
function walk() {
// 获取当前 token
let token = tokens[current];
// 数字类token
if (token.type === 'number') {
current++;
// 生成 NumberLiteral 节点
return {
type: 'NumberLiteral',
value: token.value,
};
}
// 字符串类token
if (token.type === 'string') {
current++;
// 生成 StringLiteral 节点
return {
type: 'StringLiteral',
value: token.value,
};
}
// 函数名
if (token.type === 'paren' && token.value === '(') {
// 跳过左括号，获取下一个 token 作为函数名
token = tokens[++current];
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
token = tokens[++current];
// 以前面的词法分析结果为例，有两个右圆括号，表示有嵌套的函数
//
// [
// { 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: ')' } <<< 右圆括号
// ]
//
// 遇到嵌套的 `CallExpressions` 时，我们使用 `walk` 函数来增加 `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);
}
// AST的根节点
let ast = {
type: 'Program',
body: [],
};
// 填充ast.body
while (current < tokens.length) {
ast.body.push(walk());
}
// 返回AST
return ast;
}通过上面的例子可以看到，AST中有许多相似type类型的节点，这些节点包含若干其他属性，用于描述AST的其他信息。当转换AST的时候，我们可以直接添加、移动、替换原始AST上的这些节点（同种语言下的操作），也可以根据原始AST生成一个全新的AST（不同种语言）。
本编译器的目标是两种语言风格之间的转换，故需要生成一个全新的AST。
针对AST这类“树状”的结构，可以采用深度优先的方式遍历。以上面的AST为例，遍历过程如下：
对于本编译器而言，上述的节点类型已经足够，即「访问者」所需要提供的能力已经足够。
通过访问者模式，可以很好地分离行为和数据，实现解耦。在本编译器中，可以创建一个类似下面的“访问者”对象，它能够提供访问各种数据类型的方法。
var visitor = {
NumberLiteral() {},
CallExpression() {},
}当遍历AST的时，一旦匹配“进入”（enter）到特定类型的节点，就调用访问者提供的方法。同时为了保证访问者能够拿到当前节点信息，我们需要将当前节点和父节点传入。
var visitor = {
NumberLiteral(node, parent) {},
CallExpression(node, parent) {},
}但是也存在需要退出的情况，还是以上面的AST为例：
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral当深度遍历的时候，可能会进入叶子节点，此时我们就需要“退出”（exit）这个分支。当我们沿着树深度遍历时，每个节点会存在两种操作，一种是“进入”（enter），一种是“退出”（exit）。
-> Program (enter)
-> CallExpression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Call Expression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Number Literal (enter)
<- Number Literal (exit)
<- CallExpression (exit)
<- CallExpression (exit)
<- Program (exit)为了满足这样的操作，就需要继续改造访问者对象，最终大致如下：
const visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
},
CallExpression: {
enter(node, parent) {},
exit(node, parent) {},
},
};结合上述遍历器和访问者对象的描述，转换函数大致如下：
/**
* 遍历器
* @param {*} ast 语法抽象树
* @param {*} visitor 访问者对象
*/
function traverser(ast, visitor) {
// 遍历数组中的节点
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// 遍历节点，参数为当前节点及其父节点
function traverseNode(node, parent) {
// 获取访问者对象上对应的方法
let methods = visitor[node.type];
// 执行访问者的 enter 方法
if (methods && methods.enter) {
methods.enter(node, parent);
}
switch (node.type) {
// 根节点
case 'Program':
traverseArray(node.body, node);
break;
// 函数调用
case 'CallExpression':
traverseArray(node.params, node);
break;
// 数值和字符串，不用处理
case 'NumberLiteral':
case 'StringLiteral':
break;
// 无法识别的字符，抛出错误提示
default:
throw new TypeError(node.type);
}
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 开始遍历
traverseNode(ast, null);
}
/**
* 转换器
* @param {*} ast 抽象语法树
* @returns 新AST
*/
function transformer(ast) {
// 创建一个新 AST
let newAst = {
type: 'Program',
body: [],
};
// 通过 _context 引用，更新新旧节点
ast._context = newAst.body;
// 使用遍历器遍历原始 AST
traverser(ast, {
// 数字节点，直接原样插入新AST
NumberLiteral: {
enter(node, parent) {
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
// 字符串节点，直接原样插入新AST
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
// 函数调用
CallExpression: {
enter(node, parent) {
// 创建不同的AST节点
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
// 同样通过 _context 引用参数，供子节点使用
node._context = expression.arguments;
// 顶层函数调用本质上是一个语句，写成特殊节点 `ExpressionStatement`
if (parent.type !== 'CallExpression') {
expression = {
type: 'ExpressionStatement',
expression,
};
}
parent._context.push(expression);
},
},
});
return newAst;
}(add 2 (subtract 4 2))的 AST 经过该转换器之后，就转变成下面的新 AST ：
{
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',
},
],
},
],
},
},
],
};有时候这个阶段的工作会和转换阶段有重叠，但一般而言主要还是根据AST输出对应代码。
代码生成有几种不同的方式，有些编译器会复用之前的token，有些会创建对立的代码表示，以便于线性输出代码。
代码生成器需要知道如何“打印”AST中所有类型的节点，然后递归调用自身，直到遍历完AST，所有代码转换成字符串。
/**
* 代码生成器
* @param {*} node AST 中的 body 节点
* @returns 代码字符串
*/
function codeGenerator(node) {
// 判断节点类型
switch (node.type) {
// 根节点，递归 body 节点列表
case 'Program':
return node.body.map(codeGenerator).join('\n');
// 表达式，处理表达式内容，以分好结尾
case 'ExpressionStatement':
return `${codeGenerator(node.expression)};`;
// 函数调用，添加左右括号，参数用逗号隔开
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);
}
}上述流程就是编译器工作的三个基本步骤就是如下：
/**
* 编译器
* @param {*} input 代码字符串
* @returns 代码字符串
*/
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
return output;
}
babel是一个编译器，默认只用于转换js语法，而不会转换新语法提供的API，比如Promise、Generator等，此时我们就需要使用polyfill来兼容这些新语法，其工作原理大致如下：
(function (window) {
if (window.incompatibleFeature) {
return window.incompatibleFeature;
} else {
window.incompatibleFeature = function () {
// 兼容代码
};
}
})(window);表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素类的前提下定义作用于这些元素的新操作。本质是将行为与数据解耦，根据访问者不同，所展示的行为也不同。
编译器中使用的是“访问者对象”，下面以“访问者类”为例：
class Keyboard {
accept(computerPartVisitor) {
computerPartVisitor.visit(this);
}
}
class Monitor {
accept(computerPartVisitor) {
computerPartVisitor.visit(this);
}
}
class Mouse {
accept(computerPartVisitor) {
computerPartVisitor.visit(this);
}
}class Computer {
constructor(){
this.parts = [new Mouse(), new Keyboard(), new Monitor()];
}
accept(computerPartVisitor) {
for (let i = 0; i < this.parts.length; i++) {
this.parts[i].accept(computerPartVisitor);
}
computerPartVisitor.visit(this);
}
}class ComputerPartDisplayVisitor{
visit(device) {
console.log(`Displaying ${device.constructor.name}.`);
}
}const computer = new Computer();
computer.accept(new ComputerPartDisplayVisitor());
/**
* output:
* Displaying Mouse.
* Displaying Keyboard.
* Displaying Monitor.
* Displaying Computer.
*/https://github.com/jamiebuilds/the-super-tiny-compiler
有史以来最小的编译器源码解析[2]
https://developer.51cto.com/art/202106/668215.htm
访问者模式一篇就够了[3]
[1]the-super-tiny-compiler: https://github.com/jamiebuilds/the-super-tiny-compiler
[2]有史以来最小的编译器源码解析: https://segmentfault.com/a/1190000016402699
[3]访问者模式一篇就够了: https://www.jianshu.com/p/1f1049d0a0f4
本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/SLT7GuKmxdkKRxuHk9FZJA
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
