阅读全文,可以得到两部分知识
背景
很多vue前端开发者,都会使用.vue来描述一个组件,其中.vue文件一般包含三部分内容template
,script
,style
, 正常来说在我们构建应用的时候,webpack、rollup等工具是不认识.vue文件类型,构建过程都需要使用一些编译器转换成最终产物js、json、字符串等。关系一般如下
所以很多人都认为编译器离我们的日常工作很远,但是我们平时使用很多高级语法都是离不开编译工具的,因此我们也有必要了解编译器基本原理。
接下来我们会基于一个十分迷你的编译器the-super-tiny-compiler学习编译器的核心要点。
编译器主要流程
the-super-tiny-compiler
演示了如何把lisp
风格函数调用转换为C语言风格
含义 | LISP | 产物 |
---|---|---|
2+(4-2) | (add 2 (subtract 4 2) | add(2, subtract(4, 2) |
一般来说编译器会分为以下几个阶段
解析
解析一般被分为两个部分:词法分析和语法分析。
- 词法分析 通过一个叫做tokenizer(词素生成器,也叫lexer)的工具将源代码分解成一个个词素。词素是描述编程语言语法的对象。它可以描述数字,标识符,标点符号,运算符等等
- 语法分析 接收词素并将它们组合成一个描述了源代码各部分之间关系的中间表达形式:抽象语法树。抽象语法树是一个深度嵌套的对象,这个对象以一种既能够简单地操作又提供很多关于源代码信息的形式来展现代码
比如(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: ')' },
* ]
而产生的抽象语法树会像下面这样:
* {
* 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',
* }]
* }]
* }]
* }
词法分析
词法分析一般的流程就是通过一个指针不断向右移动遍历,遇到不同的类型则停下来处理,push词素
到数组中
/**
* 我们从解析步骤的第一个部分开始,词法分析。也就是tokenizer词素生成器的工作。
*
* 我们将源代码分解成一个词素数组。
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/
// 我们首先需要接收一个代码字符串,并且我们需要设置两个变量……
function tokenizer(input) {
// `current`变量跟踪我们现在在源代码中的什么地方,就像一个光标一样。
let current = 0
// `tokens`变量,顾名思义,用来储存词素的数组。
let tokens = []
// 我们从创建一个`while`循环开始,在这个循环里我们会根据需求增加`current`变量的值。
//
// 注意由于词素的长度不同的,我们可能需要在一次循环中多次增加`current`的值。
while (current < input.length) {
// 我们将input中的当前字符存到char变量中。
let char = input[current]
// 我们需要检测的第一个情况就是开括号,这在之后会被函数调用`CallExpression`所用到。但是
// 现在我们只需要关心字符即可。
//
// 我们检测我们是否有一个开括号:
if (char === '(') {
// 如果我们有一个开括号,我们创建一个类型为`paren`的词素并将value设置为开括号。
tokens.push({
type: 'paren',
value: '('
})
// 之后我们增加`current`
current++
// 然后我们继续进行下一个循环
continue
}
// 接下来我们需要检测的是闭括号。这里的行为和开括号的一模一样:检查是否是一个闭括号,如果是
// 的话,创建一个新词素,增加`current`然后执行下一个循环。
if (char === ')') {
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)) {
// 我们会创造一个`value`字符串,这个字符串用来存储字符。
let value = ''
// 之后我们遍历序列中的每一个字符直到遇到一个不是数字的字符,把每一个字符添加到`value`
// 字符串中并且增加`current`的值。
while (NUMBERS.test(char)) {
value += char
char = input[++current]
}
// 之后我们将我们的数字词素添加到`tokens`数组。
tokens.push({ type: 'number', value })
// 然后我们继续下一个循环。
continue
}
// 我们同样支持字符串,字符串是由双引号"包裹的文字内容。
//
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
//
// 我们引号开始检测。
if (char === '"') {
// 创造一个`value`变量保存我们的字符串。
let value = ''
// 跳过意味着字符串开始的那个引号。
char = input[++current]
// 之后我们遍历每一个字符直到我们到达了另一个引号。
while (char !== '"') {
value += char
char = input[++current]
}
// 跳过意味着字符串结尾的引号。
char = input[++current]
// 然后创造字符串词素并添加到`tokens`数组。
tokens.push({ type: 'string', value })
continue
}
// 最后一种词素是`name`词素。这是一个字母序列,在我们lisp语法中是函数的名称。
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i
if (LETTERS.test(char)) {
let value = ''
// 和其他情况一样,我们遍历字母并将它们添加到`value`变量。
while (LETTERS.test(char)) {
value += char
char = input[++current]
}
// 之后创建词素并添加到`tokens`变量。
tokens.push({ type: 'name', value })
continue
}
// 最后如果我们并不能匹配到任何情况的话,我们就抛出一个错误并退出。
throw new TypeError('I dont know what this character is: ' + char)
}
// 最后我们返回词素数组tokens。
return tokens
}
有的编译器在词法分析阶段就会去做修改,比如prettier
自动追加分号
语法解析
这个阶段就是把词素数组递归遍历组装成一个AST,ast你可以理解为他是一个描述一段语法的多叉树
unction parser(tokens) {
// 我们还是创建一个`current`变量跟踪我们所处的位置。
let current = 0
// 但是这一次我们使用的是递归而不是一个`while`循环。所以我们定义一个`walk`函数。
function walk() {
// 在walk函数中我们首先获取当前词素。
let token = tokens[current]
// 针对不同类型的词素,我们的处理方式也不同,从数字词素开始。
//
// 我们检测当前词素是否为一个数字词素。
if (token.type === 'number') {
// 如果是一个数字词素,我们增加`current`变量的值。
current++
// 之后我们返回一个类型为`NumberLiteral`类型的抽象语法树节点,并且设置这个节点的value。
return {
type: 'NumberLiteral',
value: token.value
}
}
// 如果我们有一个字符串词素,那么和数字词素的情况类似,只不过这里我们返回一个`StringLiteral`
// 类型的词素。
if (token.type === 'string') {
current++
return {
type: 'StringLiteral',
value: token.value
}
}
// 接下来我们检测是否是一个函数调用。我们在碰到一个开括号的时候处理这种情况。
if (token.type === 'paren' && token.value === '(') {
// 我们会增加`current`变量的值来跳过开括号以选取下一个词素,这是因为在我们的抽象语法树
// 中开括号本身并没有意义。
token = tokens[++current]
// 我们创建一个类型为`CallExpression`的基础词素,之后我们将它的名字设置为当前词素的value。
// 这是因为开括号之后的词素的value就是函数的名字。
let node = {
type: 'CallExpression',
name: token.value,
params: []
}
// 我们再一次增加`current`变量来跳过包含了函数名的词素。
token = tokens[++current]
// 现在我们遍历每一个会成为我们`CallExpression`词素的`params`的词素直到我们遇到一个
// 闭括号为止。
//
// 这就是需要递归的时候。我们使用递归而不是试图直接分析可能有无限多层嵌套节点的参数。
//
// 为了解释这个概念,以我们的lisp代码为例。你可以观察到`add`的参数是一个数字和一个嵌套
// 的`CallExpression`,而这个`CallExpression`又拥有自己的参数。
//
// (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: ')' }, <<< 闭括号
// ]
//
// 我们依赖嵌套的`walk`函数在处理每一个嵌套的CallExpression`的时候增加我们的`current`变量。
// 所以我们创建一个`while`循环直到我们碰到一个类型为`paren`并且`value`是闭括号的词素。
while (
token.type !== 'paren' ||
(token.type === 'paren' && token.value !== ')')
) {
// 我们调用`walk`函数,`walk`函数会返回一个节点然后我们将这个节点添加到我们的`node.params`。
node.params.push(walk())
token = tokens[current]
}
// 最后我们还需要增加`current`变量来跳过闭括号。
current++
// 返回这个节点。
return node
}
// 同样,如果我们没有匹配到以上任何类型,我们抛出一个错误。
throw new TypeError(token.type)
}
// 现在,我们来创建我们的抽象语法树。抽象语法树的根节点是一个`Program`节点。
let ast = {
type: 'Program',
body: []
}
// 然后我们调用我们的`walk`函数,将返回的节点都添加到`ast.body`数组中。
//
// 我们在一个循环中这样做的原因是因为我们可能有多个单独的函数调用,而不是相互嵌套。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk())
}
// 最后,语法分析器会返回抽象语法树。
return 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,当我们向下遍历语法树的时候,我们会碰到所谓的叶子节点。我们在处理完一个节点后会“离开”这个节点。 所以向下遍历树的时候我们“进入”节点,而向上返回的时候我们“离开”节点。
-> 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)
为了支持上面所讲的功能,我们的访问者对象的最终形态如下:
var visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
}
};
我们希望有一个traverser
函数,在深度遍历ast的时候,能够在碰到一个节点的时候调用访问者对象相应的方法
traverse(ast, {
Program: {
enter (node, parent) {
// 修改节点
},
exit (node, parent) {
// 修改节点
}
},
CallExpression: {
enter (node, parent) {
// 修改节点
},
exit (node, parent) {
// 修改节点
}
},
})
traverser实现要点
怎么理解进入和离开子点的遍历呢。如果你能理解二叉树的前中后序遍历这个框架
function traverseNode(root) {
if (root == null) {
return;
}
// 前序位置 进入节点
traverseNode(root.left);
// 中序位置
traverseNode(root.right);
// 后序位置 离开节点
}
那么traverser是多叉树的前中后序遍历
function traverseNode(node) {
if (node.children.length === 0) {
return;
}
// 前序位置 进入节点enter()
node.children.forEach(traverseNode)
// 后序位置 离开节点exit()
}
所以traverser
的实现也是基于这个框架变形的
function traverser(ast, visitor) {
// `traverseArray`函数,这个函数允许我们遍历一个数组并且调用我们接下来定义的函数:"traverseNode`。
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent)
})
}
// `traverseNode`函数会接收一个节点以及这个节点的父节点。这样它就可以将这两个参数传递给我们
// 的访问者对象的方法。
function traverseNode(node, parent) {
//我们首先检测访问者对象是否含有一个匹配当前类型节点的方法。
let methods = visitor[node.type]
// 如果当前类型节点有相匹配的`enter`方法,我们调用这个方法`enter`方法并传入节点以及父节点。
if (methods && methods.enter) {
methods.enter(node, parent)
}
// 接下来我们根据当前节点类型分情况处理。
switch (node.type) {
// 我们从最顶层的`Program`开始。由于Program节点的body属性是一个节点数组,我们调用
// `traverseArray`函数来向下遍历它们。
//
// (请注意'traverseArray`会调用`traverseNode`所以我们会递归地遍历抽象语法树。)
case 'Program':
traverseArray(node.body, node)
break
// 对于`CallExpression`节点,我们遍历它的`params`属性。
case 'CallExpression':
traverseArray(node.params, node)
break
// 对于`NumberLiteral`和`StringLiteral`的情况,我们并没有任何子节点去访问,所以我们
// 直接break。
case 'NumberLiteral':
case 'StringLiteral':
break
// 同样的,如果出现没有匹配的情况,我们抛出一个错误。
default:
throw new TypeError(node.type)
}
// 如果访问者对象针对当前类型节点存在着一个`exit`方法的话,我们在这里调用它并传入节点和父节点。
if (methods && methods.exit) {
methods.exit(node, parent)
}
}
// 最后,我们通过调用`traverseNode`并传入ast和null来开始遍历。这里传入null作为父节点的原
// 因是因为抽象语法树的根节点并没有父节点。
traverseNode(ast, null)
}
转换
我们转换器的目的是接收我们创造的抽象语法树并将它和一个访问者对象传给traverser函数。然后创造一个新的抽象语法树。
----------------------------------------------------------------------------
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'
| }]
| }
| }]
| }
所以我们定义一个transformer函数,这个函数接收一个lisp抽象语法树对象。
function transformer(ast) {
// 我们会创建一个`newAst`,这个新抽象语法树和之前的抽象语法树一样有一个Program节点。
let newAst = {
type: 'Program',
body: []
}
// 接下来我会小小地作弊一下并使用一个小小的hack。我们会给父节点添加一个`context`属性,我们
// 会将子节点添加到它们的父节点的`context`属性中。通常情况下你会有一个比这个更好的抽象,
// 但是针对我们的目的这样做更简洁。
//
// 只要记住`context`是一个从旧的抽象语法树到新的抽象语法树的引用即可。
ast._context = newAst.body
// 我们从调用traverser函数并传入抽象语法树和访问者对象开始。
traverser(ast, {
// 访问者对象处理的第一种情况是`NumberLiteral`节点。
NumberLiteral: {
// 我们会在进入节点的时候访问节点。
enter(node, parent) {
//我们创建一个`NumberLiteral`类型的新节点并添加到父节点的`context`。
parent._context.push({
type: 'NumberLiteral',
value: node.value
})
}
},
// 接下来是`StringLiteral`类型节点。
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value
})
}
},
// 接着是`CallExpression`类型节点。
CallExpression: {
enter(node, parent) {
// 我们创建一个新的`CallExpression`类型节点,这个新节点还有一个嵌套的`Identifier`对象。
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name
},
arguments: []
}
// 接下来我们给原始的`CallExpression`节点定义一个`context`属性。这个属性指向
// `expression`的arguments属性,这样我们就可以添加参数了。
node._context = expression.arguments
// 接下来我们检测父节点是否是一个`CallExpression`,如果不是的话……
if (parent.type !== 'CallExpression') {
// 我们将我们的`CallExpression`节点包裹在`ExpressionStatement`节点中。
// 我们这样做的原因是因为JS中顶层的`CallExpression`实际上是语句。
expression = {
type: 'ExpressionStatement',
expression: expression
}
}
// 最后,我们将我们的`CallExpression`(可能被包裹)添加到父节点的`context`属性。
parent._context.push(expression)
}
}
})
// 最后,转换器会返回我们刚刚创造的全新抽象语法树。
return newAst
}
代码生成
有了转换后的ast,那么定义递归调用,不断拼接,最终返回一个字符串产物
function codeGenerator(node) {
// 我们根据节点类型分情况处理。
switch (node.type) {
// 如果我们有一个`Program`节点。我们会使用代码生成器遍历`body`属性中的所有节点然后使用
// 换行符\n连接起来。
case 'Program':
return node.body.map(codeGenerator).join('\n')
// 针对`ExpressionStatement`我们会对节点的expression属性调用代码生成器,并加上一个分号……
case 'ExpressionStatement':
return (
codeGenerator(node.expression) + ';' // << (...because we like to code the *correct* way)
)
// 针对`CallExpression`我们会打印出`callee`,也就是函数名,加上一个开括号,我们会对
// `arguments`数组中的每一个节点调用代码生成器,使用逗号连接它们,然后我们添加一个闭括号。
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator).join(', ') +
')'
)
// 针对`Identifier`,我们简单地返回节点的name属性。
case 'Identifier':
return node.name
// 针对`NumberLiteral`,我们简单地返回节点的值。
case 'NumberLiteral':
return node.value
// 针对StringLiteral`,我们在节点value周围加上引号。
case 'StringLiteral':
return '"' + node.value + '"'
// 如果没有匹配,我们抛出一个错误。
default:
throw new TypeError(node.type)
}
}
最终实现
let tokens = tokenizer(input)
let ast = parser(tokens)
let newAst = transformer(ast)
let output = codeGenerator(newAst)
// 返回输出!
return output
}
console.log("