前言
编译器在各种场合下都会有应用，从webpack到babel，到框架外部比方vue，都或多或少的应用到了编译，所以这次理解一下编译器的最根底的实现。
指标
这次就把一个lisp-like函数调用形式转换成JavaScript的形式。
两种语言的函数调用形式比照如下：
| LISP | JavaScript | |
|---|---|---|
| 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)) |
前者大略能够形容为括号示意函数调用，参数之间用空格隔开。
咱们这里假如咱们的源代码是这样的
(add 100 (substract 3 2))也就是100 + (3 - 2)，那么开始吧。
思路
个别的编译器分为以下几步：
- Parsing - 将源代码文本解析成更为形象的表达方式，通常是AST（Abstract Syntax Tree） - 形象语法树。
- Transformation - 能够通过具体须要去变更，解决原始的AST。
- Code Generation - 从AST生成代码。
接下来就一步步开始。
Parsing
这一步次要是对于源代码的解析，个别可再细分成2步：
- Lexical Analysis（词法剖析）- 将源代码以单词为维度分成许多独立的片段。
- Syntactic Analysis（语法分析）- 把独立的代码片段以树形构造串联起来，生成AST。
Lexical Analysis
这一步通常会用tokenizer表白，传入源代码，返回tokens - 我称之为单词数组。
对于咱们的例子来说, 拆分后大略会示意成上面的样子：
[ { type: 'paren', value: '(' }, { type: 'name', value: 'add' }, { type: 'number', value: '100' }, { type: 'paren', value: '(' }, { type: 'name', value: 'substract' }, { type: 'number', value: '3' }, { type: 'number', value: '2' }, { type: 'paren', value: ')' }, { type: 'paren', value: ')' }]这一步能够了解为以单个单词为维度拆分了一句句子，类比到中文就比方
我去餐厅吃饭就能够被拆分为
我，去，餐厅，吃饭这种以词性辨别的单词合集。
晓得了其意义之后就是代码实现了，具体如下：
function tokenizer(input) { // 单词数组 const tokens = [] // 设定一个指针 let current = 0 // 从0开始遍历源代码 while (current < input.length) { let char = input[current] // 如果是空格则跳过 const spaceRegExp = /\s/ if (spaceRegExp.test(char)) { current++ continue } // 如果是括号则退出后果中 if (char === '(' || char === ')') { tokens.push({ type: 'paren', value: char }) // 指针指向下一位，开始下次循环 current++ continue } // 如果是小写字母（这里暂且只反对小写字母） // 则累计遍历到最初一个小写字母再放入后果中 const letterRegExp = /[a-z]/ if (letterRegExp.test(char)) { let value = '' while (letterRegExp.test(char)) { value += char char = input[++current] } tokens.push({ type: 'name', value }) continue } // 如果是数字则累加遍历到最初一个数组放入后果中 const numberRegExp = /[0-9]/ if (numberRegExp.test(char)) { let value = '' while (numberRegExp.test(char)) { value += char char = input[++current] } tokens.push({ type: 'number', value }) continue } throw new Error('词法剖析失败，有不反对的单词类型') } return tokens}大抵的逻辑就是设定一个指针，通过适合的规定一直的一个个向后寻找符合条件的单词。
Syntactic Analysis
再接下来就是语法分析，把刚刚失去的单词们关联起来，把一整个语句生成一个树形构造，也就是形象语法树。
看上去会像这样：
{ "type": "Program", "body": [ { "type": "CallExpression", "name": "add", "params": [ { "type": "NumberLiteral", "value": 100 }, { "type": "CallExpression", "name": "substract", "params": [ { "type": "NumberLiteral", "value": 3 }, { "type": "NumberLiteral", "value": 2 } ] } ] } ]}这一步就相当于把单词连成句子，用树形构造示意他们之间的关系。
比方函数就有类型，函数名，参数。这些实践上都能够自定义，依据每一种不同的语言的须要。
次要是代码的实现，因为每一个子节点都有可能是各种类型，所以用递归显著会更不便实现一些，具体代码如下。
function parser(tokens) { // 设定一个指针，从0开始 let current = 0 // 这里用递归更容易实现 function parse() { let token = tokens[current] // 如果是数字则返回数字节点，指针指向下一个 if (token.type === 'number') { current++ return { type: 'NumberLiteral', value: +token.value, } } // 如果是左括号 if (token.type === 'paren' && token.value === '(') { // 生成一个类型为调用表达式的节点 const node = { type: 'CallExpression', name: '', params: [], } // 指向下一个token，失常状况下肯定是name类型的 token = tokens[++current] if (token.type !== 'name') { throw new Error('没有提供函数名') } node.name = token.value // 再指向下一个token token = tokens[++current] // 只有不是右括号则始终退出参数中 while (!(token.type === 'paren' && token.value === ')')) { node.params.push(parse()) // 更新以后指针 token = tokens[current] } // 跳过右括号 current++ return node } throw new Error('token类型谬误') } const ast = { type: 'Program', body: [], } // 把所有的token生成的节点放入body中（如果是多行语句则会有多个对象） while (current < tokens.length) { ast.body.push(parse()) } return ast}大抵的思路就是parse函数针对特定类型的值有特定的解决形式，而有那种须要依赖其余值的语法的时候（比方参数调用，参数可能是任何内容）就递归的调用，同时保护一个指针来确立地位。
Transformation
事实上如果咱们的需要只是生成代码的话，通过下面失去的AST就能够间接进行下一步Code Generation了，但那样必须要针对咱们本人的树形构造生成对应的JavaScript代码，理论状况下两种语法可能是不同语言的，所以更好的是将咱们之前的AST转换成更规范的语法。
天经地义的，目前市面上也有比拟罕用的标准estree，比方非常罕用的编译器acorn就是合乎这项规范的。（目前webpack, rollup都是基于他，@babel/parser也是参考的他）具体各种生成后果能够在 https://astexplorer.net/ 尝试。
于是咱们接下来思考把咱们的AST变成合乎estree标准的AST。
所以咱们必须要遍历所有节点，于是咱们针对每个节点都设定本人的处理函数，整体叫做visitor，大略是这样。
const visitor = { Program: function (node, parent) { // ... }, NumberLiteral: function (node, parent) { // ... }, // ...}对于每个函数须要的参数能够依据具体须要做考量，这里为了取得最简略的关系对应暂且传入以后节点和父节点。
另外因为咱们的需要比较简单，所以也不须要在意拜访工夫点，如果需要的话能够设定拜访开始和拜访完结之类的工夫点比方
const visitor = { Program: { enter () { // ... }, exit () { // ... }, } // ...对于咱们这里就不须要了，接下来实现一下具体代码。
function traverser(ast, visitor) { // 拜访单个节点 function traverseNode (node, parent) { // 执行以后拜访函数 const method = visitor[node.type] method && method(node, parent) // 如果有子节点则遍历子节点 switch(node.type) { case 'Program': traverseArray(node.body, node) break case 'CallExpression': traverseArray(node.params, node) break case 'NumberLiteral': break default: throw new Error('节点类型谬误') } } // 拜访数组节点 function traverseArray(array, parent) { array.forEach(child => { traverseNode(child, parent) }) } // 拜访ast根节点 traverseNode(ast, null)}这个函数提供了AST以及visitor，能够让咱们拜访到每一个节点，而对于每个节点的具体操作则要依据须要来，咱们这里是心愿把语法转换成合乎estree规范的语法，所以再实现一个转换函数。
function transform(ast) { const newAst = { type: 'Program', body: [], } // 这里设置一个属性指向新的AST上下文 ast._context = newAst.body traverser(ast, { NumberLiteral(node, parent) { // 转换为estree规范的数字节点，放入父节点上下文 parent._context.push({ type: 'Literal', value: node.value, }) }, CallExpression(node, parent) { // estree规范的调用节点构造 let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name, }, arguments: [], } // 把上下文设置为参数数组 node._context = expression.arguments // 如果父节点不是调用表达式则表达式外层须要套一层，estree规范 if (parent.type !== 'CallExpression') { expression = { type: 'ExpressionStatement', expression, } } // 以后表达式放入父节点上下文中 parent._context.push(expression) }, }) return newAst}这个函数的外部实现事实上是齐全依据须要来的，因为咱们须要这里转换格局所以生成了一个新的AST，再判断节点，把对应节点转换过的新格局放入新的树中。
这样之后咱们失去的后果是这样：
{ "type": "Program", "body": [ { "type": "ExpressionStatement", "expression": { "type": "CallExpression", "callee": { "type": "Identifier", "name": "add" }, "arguments": [ { "type": "Literal", "value": 100 }, { "type": "CallExpression", "callee": { "type": "Identifier", "name": "substract" }, "arguments": [ { "type": "Literal", "value": 3 }, { "type": "Literal", "value": 2 } ] } ] } } ]}目前这个树结构是合乎estree规范的，以至于咱们能够应用其余第三方库来操作这个树。比方escodegen，能够通过estree生成代码，对下面这个树结构的执行后果是：
add(100, substract(3, 2));Code Generation
尽管下面曾经能够用其余库实现了，不过咱们这里还是来理解一下通过AST生成代码的原理吧。大略的原理理论很简略，就是判断以后节点的类型对其以及其子节点递归的去生成代码。
function generateCode(node) { switch(node.type) { case 'Program': // 对body每一个节点生成代码用换行隔开 return node.body.map(generateCode).join('\n') case 'Literal': // 字面量间接返回值 return node.value case 'ExpressionStatement': // 表达式则返回表达式生成的代码，加上分号结尾 return generateCode(node.expression) + ';' case 'CallExpression': // 如果是函数调用，则把参数生成的代码通过逗号隔开 return `${node.callee.name}(${node.arguments.map(generateCode).join(', ')})` default: throw new Error('节点类型谬误') }}把下面几步加起来大略会是上面这样：
const tokens = tokenizer(code)const ast = parser(tokens)const newAst = transform(ast)const result = generateCode(newAst)console.log(result)// => add(100, substract(3, 2));那么这样就实现了。
总结
这次介绍了编译器大抵的工作原理，在各种场景下应用时样子可能不太一样不过核心思想就是这么几步，之后面对各种理论状况踊跃的去改良吧！
本文参考了the-super-tiny-compiler这个我的项目的许多内容，举荐大家去学习。
参考
- the-super-tiny-compiler
- 相干代码
- 原文地址