编译器原理

大多数编译器分为三个主要阶段：解析、转换和代码生成

解析（Parsing）

解析是将

源代码 转换为 抽象语法树（AST） 的过程。 Source Text --> Lexer --> Token --> Parser --> AST 解析通常分为两个子阶段：词法分析 和 语法分析。 解析的产物是 AST，它为后续的转换和代码生成阶段提供了基础。

词法分析

词法分析阶段是由词法分析器（也称为扫描器）完成的。 词法分析器的主要任务是将源代码转换为一系列记号（tokens），每个记号代表源代码中的一个基本语法单元。以下是词法分析器的具体功能：

读取源代码：词法分析器从头到尾读取源代码的字符流。
识别记号：根据语言的词法规则，将字符序列识别为有意义的记号，每个记号代表源代码中的基本单元，如关键字、标识符、操作符、字面量和分隔符。
忽略无关字符：词法分析器通常会忽略不重要的字符，比如空格、换行和注释，以便简化后续的分析过程。
生成记号流：词法分析器的产物是一个记号流（token stream），这些记号将被传递给语法分析器进行进一步处理。
错误检测：在识别记号的过程中，词法分析器也负责检测和报告词法错误，例如非法字符或不完整的记号。

语法分析

语法分析阶段是由语法分析器（也称为解析器）完成的。 语法分析器的主要任务是将词法分析器生成的记号流（token stream）转换为抽象语法树（AST），并检查记号序列是否符合语言的语法规则。以下是语法分析器的具体功能：

读取记号流：语法分析器接收词法分析器生成的记号流，作为输入。
构建抽象语法树（AST）：语法分析器根据语言的语法规则，将记号流解析为抽象语法树。AST 是代码的结构化表示，反映了代码的层次结构和操作顺序。
语法检查：语法分析器检查记号序列是否符合语言的语法规则，确保代码的语法正确性。
- 例如，语法分析器会检查括号是否匹配、语句是否完整等。
错误报告：在解析过程中，如果发现语法错误，语法分析器会生成相应的错误消息，以帮助开发者定位和修复问题。
生成 AST：语法分析器的产物是抽象语法树（AST），它表示代码的语法结构，并为后续的代码转换和生成阶段提供了基础。 :::details 小案例对于以下 LISP 语法的函数调用：

1(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"，
      }，
     ]，
    }，
   ]，
  }，
 ]，
}

:::

转换（Transformation）

转换阶段是由转换器（Transformer）完成的。转换器的主要任务是根据特定的转换规则或插件，对 AST 进行遍历和修改，以实现特定的功能，例如优化代码、语法降级等。以下是转换器的具体功能：

遍历 AST：
- 转换器会遍历整个抽象语法树，访问每一个节点。
- 这个过程可以使用不同的遍历策略，例如深度优先遍历或广度优先遍历。
应用转换规则：
- 在遍历过程中，转换器会根据配置的转换规则或插件，对特定类型的节点进行修改。
- 例如，将箭头函数转换为普通函数表达式，或者将现代 JavaScript 语法转换为旧版本的语法。
修改 AST：
- 转换器可以对 AST 进行各种修改，包括添加、删除或替换节点。
- 这些修改可以是为了优化代码、实现语法降级、插入调试信息等。
生成新的 AST：
- 转换器的产物是经过修改的 AST，这个新的 AST 反映了应用转换规则后的代码结构。

代码生成（Code Generation）

代码生成阶段是由代码生成器完成的。代码生成器的主要任务是将抽象语法树（AST）转换为可执行的目标代码。这个过程通常是编译器的最后一个阶段，生成的代码可以是机器码、字节码或其他形式的代码表示。

实战：迷你编译器

1const tokenizer = require("./tokenizer")
2const parser = require("./parser")
3const transformer = require("./transformer")
4const codeGenerator = require("./codeGenerator")
5const input = "(add 2 (subtract 4 2))"
6const tokens = tokenizer(input)
7const ast = parser(tokens)
8const newAst = transformer(ast)
9const output = codeGenerator(newAst)
10console.log(output)

1/**
2 * 词法分析器
3 * @param {*} input 代码字符串
4 * @returns tokes array
5 */
6function tokenizer(input) {
7 let current = 0
8 let tokens = []
9 while (current < input.length) {
10  let char = input[current]
11  if (char === "(") {
12   tokens.push({
13    type: "paren"，
14    value: "("，
15   })
16   current++
17   continue
18  }
19  if (char === ")") {
20   tokens.push({
21    type: "paren"，
22    value: ")"，
23   })
24   current++
25   continue
26  }
27        // 跳过空格
28  let WHITESPACE = /\s/
29  if (WHITESPACE.test(char)) {
30   current++
31   continue
32  }
33        // 处理数字
34  let NUMBERS = /[0-9]/
35  if (NUMBERS.test(char)) {
36   // 我们将创建一个`value`字符串，我们将字符推送到其中。
37   let value = ""
38   // 然后我们将遍历序列中的每个字符，直到遇到不是数字的字符，
39   // 将每个是数字的字符推送到我们的`value`中，并在此过程中递增`current`。
40   while (NUMBERS.test(char)) {
41    value += char
42    char = input[++current]
43   }
44   // 之后我们将我们的`number`标记推送到`tokens`数组中。
45   tokens.push({ type: "number"， value })
46   // 然后我们继续。
47   continue
48  }
49        // 处理字符串
50  if (char === '"') {
51   let value = ""
52   // 跳过开头双引号。
53   char = input[++current]
54   while (char !== '"') {
55    value += char
56    char = input[++current]
57   }
58   // 跳过结尾的双引号。
59   char = input[++current]
60   tokens.push({ type: "string"， value })
61   continue
62  }
63  let LETTERS = /[a-z]/i
64  if (LETTERS.test(char)) {
65            // 用于存储连续的字母字符。
66   let value = ""
67   while (LETTERS.test(char)) {
68    value += char
69    char = input[++current]
70   }
71   tokens.push({ type: "name"， value })
72   continue
73  }
74  // 最后，如果我们到现在还没有匹配到一个字符，我们将抛出一个错误并完全退出。
75  throw new TypeError("我不知道这个字符是什么：" + char)
76 }
77 // 返回tokens数组。
78 return tokens
79}
80module.exports = tokenizer

1/**
2 * 语法分析器
3 * @param {*} tokens
4 * @returns
5 */
6function parser(tokens) {
7 let current = 0
8 // 递归
9 function walk() {
10  let token = tokens[current]
11  // 处理 number 类型
12  if (token.type === "number") {
13   current++
14   // 我们将返回一个名为`NumberLiteral`的新AST节点，并将其值设置为我们标记的值。
15   return {
16    type: "NumberLiteral"，
17    value: token.value，
18   }
19  }
20        // 处理  string 类型
21  if (token.type === "string") {
22   current++
23            // 我们将返回一个名为`StringLiteral`的新AST节点，并将其值设置为我们标记的值。
24   return {
25    type: "StringLiteral"，
26    value: token.value，
27   }
28  }
29        // 处理 左括号
30  if (token.type === "paren" && token.value === "(") {
31   token = tokens[++current]
32   let node = {
33    type: "CallExpression"，
34    name: token.value，
35    params: []，
36   }
37            console.log(token.value)
38   token = tokens[++current]
39   while (
40    token.type !== "paren" ||
41    (token.type === "paren" && token.value !== ")")
42   ) {
43    node.params.push(walk())
44    token = tokens[current]
45   }
46   current++
47   return node
48  }
49  throw new TypeError(token.type)
50 }
51 let ast = {
52  type: "Program"，
53  body: []，
54 }
55 
56 while (current < tokens.length) {
57  ast.body.push(walk())
58 }
59 // 返回AST。
60 return ast
61}
62module.exports = parser

1// 遍历器
2function traverser(ast， visitor) {
3 // 一个traverseArray函数，它将允许我们遍历一个数组并调用我们将定义的下一个函数：traverseNode。
4 function traverseArray(array， parent) {
5  array.forEach((child) => {
6   traverseNode(child， parent)
7  })
8 }
9 // traverseNode将接受一个node及其parent节点。这样它可以将两者传递给我们的访问者方法。
10 function traverseNode(node， parent) {
11  // 我们首先测试访问者上是否存在与type匹配的方法。
12  let methods = visitor[node.type]
13  // 如果该节点类型有一个enter方法，我们将使用node及其parent调用它。
14  if (methods && methods.enter) {
15   methods.enter(node， parent)
16  }
17  // 接下来我们将根据当前节点类型分开处理。
18  switch (node.type) {
19   case "Program":
20    traverseArray(node.body， node)
21    break
22   case "CallExpression":
23    traverseArray(node.params， node)
24    break
25   case "NumberLiteral":
26   case "StringLiteral":
27    break
28   default:
29    throw new TypeError(node.type)
30  }
31  // 如果该节点类型有一个exit方法，我们将使用node及其parent调用它。
32  if (methods && methods.exit) {
33   methods.exit(node， parent)
34  }
35 }
36 // 最后我们通过调用traverseNode并传入我们的ast来启动遍历器，因为AST的顶层没有父节点，所以传入null。
37 traverseNode(ast， null)
38}
39/**
40 * 转换
41 * @param {*} ast
42 * @returns
43 */
44function transformer(ast) {
45 let newAst = {
46  type: "Program"，
47  body: []，
48 }
49 // 接下来我要作弊一点，创建一个小技巧。我们将在父节点上使用一个名为context的属性，
50 // 我们将节点推送到它们父节点的context中。通常你会有一个比这更好的抽象，
51 // 但为了我们的目的，这使事情变得简单。
52 // 只需注意，context是从旧AST到新AST的引用。
53 ast._context = newAst.body
54 // 我们将从调用带有访问者的遍历器函数开始。
55 traverser(ast， {
56  // 第一个访问者方法接受任何NumberLiteral
57  NumberLiteral: {
58   // 我们将在进入时访问它们。
59   enter(node， parent) {
60    // 我们将创建一个同样名为NumberLiteral的新节点，并将其推送到父context中。
61    parent._context.push({
62     type: "NumberLiteral"，
63     value: node.value，
64    })
65   }，
66  }，
67  // 接下来是StringLiteral
68  StringLiteral: {
69   enter(node， parent) {
70    parent._context.push({
71     type: "StringLiteral"，
72     value: node.value，
73    })
74   }，
75  }，
76  // 接下来是CallExpression。
77  CallExpression: {
78   enter(node， parent) {
79    // 我们开始创建一个带有嵌套Identifier的新节点CallExpression。
80    let expression = {
81     type: "CallExpression"，
82     callee: {
83      type: "Identifier"，
84      name: node.name，
85     }，
86     arguments: []，
87    }
88    // 接下来我们将在原始CallExpression节点上定义一个新的context，
89    // 该context将引用expression的arguments，以便我们可以推送参数。
90    node._context = expression.arguments
91    // 然后我们将检查父节点是否是CallExpression。
92    // 如果不是...
93    if (parent.type !== "CallExpression") {
94     // 我们将用一个ExpressionStatement包装我们的CallExpression节点。
95     // 我们这样做是因为JavaScript中的顶层CallExpression实际上是语句。
96     expression = {
97      type: "ExpressionStatement"，
98      expression: expression，
99     }
100    }
101    // 最后，我们将（可能包装的）CallExpression推送到父context中。
102    parent._context.push(expression)
103   }，
104  }，
105 })
106 return newAst
107}
108module.exports = transformer

1/**
2 * 代码生成器
3 * @param {*} node
4 * @returns
5 */
6function codeGenerator(node) {
7 switch (node.type) {
8  // 如果我们有一个Program节点。我们将遍历body中的每个节点，
9  // 并将它们传递给代码生成器，并用换行符连接它们。
10  case "Program":
11   return node.body.map(codeGenerator).join("\n")
12  // 对于ExpressionStatement，我们将调用代码生成器处理嵌套的表达式，并添加一个分号...
13  case "ExpressionStatement":
14   return (
15    codeGenerator(node.expression) + ";" 
16   )
17  // 对于CallExpression，我们将打印callee，添加一个左括号，
18  // 遍历arguments数组中的每个节点，并将它们传递给代码生成器，
19  // 用逗号连接它们，然后添加一个右括号。
20  case "CallExpression":
21   return (
22    codeGenerator(node.callee) +
23    "(" +
24    node.arguments.map(codeGenerator).join("， ") +
25    ")"
26   )
27  // 对于Identifier，我们将只返回node的名称。
28  case "Identifier":
29   return node.name
30  // 对于NumberLiteral，我们将只返回node的值。
31  case "NumberLiteral":
32   return node.value
33  // 对于StringLiteral，我们将在node的值周围添加引号。
34  case "StringLiteral":
35   return '"' + node.value + '"'
36  // 如果我们没有识别出节点，我们将抛出一个错误。
37  default:
38   throw new TypeError(node.type)
39 }
40}
41module.exports = codeGenerator

:::

编译器原理#

解析（Parsing）#

词法分析#

语法分析#

转换（Transformation）#

代码生成（Code Generation）#