如何编写 JavaScript 引擎?
JavaScript 引擎是解释和执行 JavaScript 代码的核心组件。
词法分析器
词法分析器是编译器中的一个重要组成部分,其作用是将源程序中的字符流转换为词法单元流,以便后续的语法分析。设计词法分析器的基本步骤如下:
- 确定词法单元的类型和模式词法单元是源程序中的最小语法单位,例如标识符、关键字、常量、运算符等。在设计词法分析器时,需要确定每种词法单元的类型和对应的正则表达式模式,以便识别源程序中的词法单元。
例如,对于一个简单的算术表达式语言,可以定义如下的词法单元类型和模式:
- 标识符:以字母或下划线开头,后跟任意个字母、数字或下划线。
- 数字常量:一个或多个数字组成的字符串。
- 运算符:加号、减号、乘号、除号等。
- 左右括号:左括号、右括号。
- 编写正则表达式模式确定词法单元类型和模式后,需要编写对应的正则表达式模式,以便识别源程序中的词法单元。正则表达式是一种描述字符串模式的语言,可以用来匹配符合某种模式的字符串。
例如,对于标识符,可以使用正则表达式[a-zA-Z_][a-zA-Z0-9_]*来匹配以字母或下划线开头、后跟任意个字母、数字或下划线的字符串。
- 实现词法分析器在实现词法分析器时,可以使用自动机或递归下降分析等算法,对源程序进行扫描和识别。具体实现方式可以参考以下步骤:
- 读入源程序字符流,逐个字符进行扫描。
- 对每个字符进行分类,判断其属于哪种词法单元。
- 根据词法单元类型和模式,使用正则表达式进行匹配。
- 如果匹配成功,则生成对应的词法单元,并将其加入词法单元流中;否则,报告词法错误。
- 输出词法单元流在词法分析器完成扫描和识别后,需要将生成的词法单元流输出给后续的语法分析器。词法单元流可以使用链表、数组等数据结构来表示。
例如,对于一个简单的算术表达式语言,源程序"1+2*(3-4)"的词法单元流可以表示为:
类型 |
值 |
数字常量 |
1 |
运算符 |
+ |
数字常量 |
2 |
运算符 |
* |
左括号 |
( |
数字常量 |
3 |
运算符 |
- |
数字常量 |
4 |
右括号 |
) |
设计词法分析器
词法分析器是编译器的一个重要组成部分,用于将源代码转换成标记流(Token Stream)。下面是一个简单的词法分析器的设计:
- 定义 Token 类,用于表示标记。Token 类应该包含以下属性:
- type:标记类型,例如关键字、标识符、运算符等。
- value:标记的值,例如标识符的名称、数字的值等。
- line:标记所在的行号。
- 定义词法分析器类,用于将源代码转换成标记流。词法分析器类应该包含以下方法:
- getNextToken():从源代码中读取下一个标记,并返回一个 Token 对象。
- tokenize():将整个源代码转换成标记流。
- 在 getNextToken()方法中,可以按照以下步骤进行:
- 跳过空格、制表符、换行符等空白字符。
- 判断当前字符是否为数字,如果是数字则读取整个数字,并返回一个数字类型的 Token 对象。
- 判断当前字符是否为字母,如果是字母则读取整个标识符,并判断是否为关键字,如果是则返回一个关键字类型的 Token 对象,否则返回一个标识符类型的 Token 对象。
- 判断当前字符是否为运算符,如果是则返回一个运算符类型的 Token 对象。
- 如果当前字符不是数字、字母或运算符,则返回一个未知类型的 Token 对象。
- 在 tokenize()方法中,可以按照以下步骤进行:
- 读取整个源代码。
- 循环调用 getNextToken()方法,直到读取完所有的标记。
- 返回一个包含所有 Token 对象的数组。
设计语法分析器
语法分析器是编译器的另一个重要组成部分,用于将标记流转换成抽象语法树(Abstract Syntax Tree,AST)。下面是一个简单的语法分析器的设计:
- 定义 AST 节点类,用于表示抽象语法树的节点。AST 节点类应该包含以下属性:
- type:节点类型,例如表达式、语句、变量声明等。
- value:节点的值,例如变量名、常量值等。
- children:子节点列表,用于表示节点的子节点。
- 定义语法分析器类,用于将标记流转换成抽象语法树。语法分析器类应该包含以下方法:
- parse():解析标记流,并返回一个 AST 根节点。
- 在 parse()方法中,可以按照以下步骤进行:
- 读取标记流中的第一个标记,并根据标记的类型创建一个根节点。
- 根据语法规则,递归调用子节点的解析方法,创建子节点,并将子节点添加到根节点的子节点列表中。
- 如果当前标记不符合语法规则,则抛出语法错误异常。
- 重复步骤 2 和 3,直到解析完整个标记流。
- 在 AST 节点类中,可以定义一些辅助方法,例如:
- isLeaf():判断当前节点是否为叶子节点。
- getChildren():返回当前节点的子节点列表。
- getType():返回当前节点的类型。
- getValue():返回当前节点的值。以上是一个简单的语法分析器的设计,实际上还需要考虑很多细节,例如处理优先级、左结合性、右结合性等特殊情况。
实现 JavaScript 运行时
实现 JavaScript 运行时需要实现以下几个部分:
-
词法分析器:读取 JavaScript 代码并将其转换成标记流(Token Stream)。
-
语法分析器:将标记流转换成抽象语法树(Abstract Syntax Tree,AST)。
-
执行引擎:遍历抽象语法树,并执行其中的代码。
-
内置对象和函数:实现 JavaScript 的内置对象和函数,例如 Object、Array、Function 等。
下面是一个简单的 JavaScript 运行时的实现:
-
词法分析器:使用正则表达式匹配 JavaScript 代码中的标记,并返回一个标记流(Token Stream)。
-
语法分析器:使用递归下降算法(Recursive Descent Parsing)将标记流转换成抽象语法树(Abstract Syntax Tree,AST)。
-
执行引擎:遍历抽象语法树,并执行其中的代码。
- 对于变量声明语句,创建一个变量并赋初值,将变量存入当前作用域中。
- 对于赋值语句,找到变量,并将其值赋为表达式的值。
- 对于表达式语句,计算表达式的值并忽略结果。
- 对于条件语句(if 语句),根据条件表达式的值判断执行哪个分支。
- 对于循环语句(for、while 语句),根据条件表达式的值判断是否执行循环体。
- 对于函数声明语句,创建一个函数对象并将其存入当前作用域中。
- 对于函数调用表达式,找到函数,并执行函数体。
- 对于对象属性访问表达式,找到对象并获取属性值。
- 对于数组元素访问表达式,找到数组并获取元素值。
- 内置对象和函数:实现 JavaScript 的内置对象和函数,例如 Object、Array、Function 等。可以使用 JavaScript 语言本身来实现这些内置对象和函数。
以上是一个简单的 JavaScript 运行时的实现,实际上还需要考虑很多细节,例如作用域、闭包、类型转换等特殊情况。
实现 JavaScript 解释器
JavaScript 解释器的设计应该包括以下几个部分:
词法分析器:将 JavaScript 代码转换为标记流
词法分析(Lexical Analysis):将代码分解成单个的词法单元(tokens),例如关键字、标识符、运算符等。这可以通过正则表达式或手写解析器实现
语法分析器:将标记流转换为语法树
语法分析(Parsing):将词法单元转换成语法树(Abstract Syntax Tree,AST),并检查语法错误。这可以通过手写递归下降解析器、LL 或 LR 分析器等实现。
语义分析器:对语法树进行语义分析
语义分析(Semantic Analysis):对 AST 进行语义分析,检查类型、作用域、函数调用等。这可以通过遍历 AST 并应用静态或动态分析算法实现。
执行器:执行语法树并输出结果
将 AST 转换成可执行的机器代码或字节码。这可以通过直接解释、编译成本地代码或编译成中间代码并交给虚拟机执行等方式实现。
点击查看 JavaScript 解释器的实现
1// 词法分析器
2function tokenize(code) {
3 const tokens = []
4 let pos = 0
5
6 while (pos < code.length) {
7 let match = null
8
9 // 匹配关键字和标识符
10 match = code.slice(pos).match(/^(\s+|let|if|else|while|for|[a-zA-Z]\w*)/)
11 if (match) {
12 tokens.push({ type: match[1].trim() })
13 pos += match[0].length
14 continue
15 }
16
17 // 匹配数字
18 match = code.slice(pos).match(/^(\d+)/)
19 if (match) {
20 tokens.push({ type: 'number', value: Number(match[1]) })
21 pos += match[0].length
22 continue
23 }
24
25 // 匹配运算符
26 match = code.slice(pos).match(/^(\+|\-|\*|\/|\=|\>|\<|\!|\&|\|)/)
27 if (match) {
28 tokens.push({ type: 'operator', value: match[1] })
29 pos += match[0].length
30 continue
31 }
32
33 // 匹配括号和分号
34 match = code.slice(pos).match(/^(\(|\)|\{|\}|\;)/)
35 if (match) {
36 tokens.push({ type: match[1] })
37 pos += match[0].length
38 continue
39 }
40
41 // 无法匹配的字符
42 throw new Error(`Unexpected character at position ${pos}`)
43 }
44
45 return tokens
46}
47
48// 语法分析器
49function parse(tokens) {
50 let pos = 0
51
52 function parseExpression() {
53 // 匹配数字
54 if (tokens[pos].type === 'number') {
55 const node = { type: 'NumberLiteral', value: tokens[pos].value }
56 pos++
57 return node
58 }
59
60 // 匹配标识符
61 if (tokens[pos].type === 'let') {
62 const node = { type: 'VariableDeclaration', name: tokens[pos + 1].type }
63 pos += 2
64 return node
65 }
66
67 // 匹配括号
68 if (tokens[pos].type === '(') {
69 pos++
70 const node = parseExpression()
71 if (tokens[pos].type !== ')')
72 throw new Error(`Expected ')' at position ${pos}`)
73
74 pos++
75 return node
76 }
77
78 // 无法匹配的表达式
79 throw new Error(`Unexpected token at position ${pos}`)
80 }
81
82 function parseStatement() {
83 // 匹配变量声明语句
84 if (tokens[pos].type === 'let') {
85 const node = { type: 'VariableDeclaration', name: tokens[pos + 1].type }
86 pos += 2
87 if (tokens[pos].type !== '=')
88 throw new Error(`Expected '=' at position ${pos}`)
89
90 pos++
91 node.value = parseExpression()
92 if (tokens[pos].type !== ';')
93 throw new Error(`Expected ';' at position ${pos}`)
94
95 pos++
96 return node
97 }
98
99 // 匹配条件语句
100 if (tokens[pos].type === 'if') {
101 const node = { type: 'IfStatement' }
102 pos++
103 if (tokens[pos].type !== '(')
104 throw new Error(`Expected '(' at position ${pos}`)
105
106 pos++
107 node.test = parseExpression()
108 if (tokens[pos].type !== ')')
109 throw new Error(`Expected ')' at position ${pos}`)
110
111 pos++
112 node.consequent = parseStatement()
113 if (tokens[pos].type === 'else') {
114 pos++
115 node.alternate = parseStatement()
116 }
117 return node
118 }
119
120 // 无法匹配的语句
121 throw new Error(`Unexpected token at position ${pos}`)
122 }
123
124 const ast = { type: 'Program', body: [] }
125
126 while (pos < tokens.length)
127 ast.body.push(parseStatement())
128
129 return ast
130}
131
132const code = `
133 let x = 1;
134 if (x > 0) {
135 console.log('Positive');
136 } else {
137 console.log('Non-positive');
138 }
139`
140
141const tokens = tokenize(code)
142const ast = parse(tokens)
143
144console.log(ast)
实现 JavaScript 编译器
词法编译器(Lexical Analyzer)
词法编译器(Lexical Analyzer)也被称为词法分析器(Lexer),是编译器中的一个组件,用于将源代码转换为令牌(Token)序列。令牌是编程语言中的基本单元,它们由词素(Lexeme)和令牌类型(Token Type)组成。
词法编译器通常由两个主要部分组成:令牌定义和扫描器。令牌定义是一组正则表达式,用于描述编程语言中的各种令牌类型。扫描器则根据这些正则表达式,对源代码进行扫描,并将其转换为令牌序列。
点击查看词法编译器的实现
1const TOKEN_TYPES = {
2 IDENTIFIER: 'IDENTIFIER',
3 NUMBER: 'NUMBER',
4 OPERATOR: 'OPERATOR',
5 PUNCTUATION: 'PUNCTUATION',
6 KEYWORD: 'KEYWORD',
7};
8
9const KEYWORDS = ['if', 'else', 'while', 'for', 'function', 'var', 'let', 'const', 'return'];
10
11const OPERATORS = ['+', '-', '*', '/', '=', '==', '!=', '<', '>', '<=', '>=', '&&', '||'];
12
13const PUNCTUATIONS = ['(', ')', '{', '}', ',', ';'];
14
15function tokenize(code) {
16 const tokens = [];
17 let current = 0;
18
19 while (current < code.length) {
20 let char = code[current];
21
22 // 处理数字
23 if (/\d/.test(char)) {
24 let value = '';
25
26 while (/\d/.test(char)) {
27 value += char;
28 char = code[++current];
29 }
30
31 tokens.push({ type: TOKEN_TYPES.NUMBER, value });
32 continue;
33 }
34
35 // 处理标识符和关键字
36 if (/[a-zA-Z]/.test(char)) {
37 let value = '';
38
39 while (/[a-zA-Z]/.test(char)) {
40 value += char;
41 char = code[++current];
42 }
43
44 if (KEYWORDS.includes(value)) {
45 tokens.push({ type: TOKEN_TYPES.KEYWORD, value });
46 } else {
47 tokens.push({ type: TOKEN_TYPES.IDENTIFIER, value });
48 }
49
50 continue;
51 }
52
53 // 处理运算符
54 if (OPERATORS.includes(char)) {
55 let value = '';
56
57 while (OPERATORS.includes(char)) {
58 value += char;
59 char = code[++current];
60 }
61
62 tokens.push({ type: TOKEN_TYPES.OPERATOR, value });
63 continue;
64 }
65
66 // 处理标点符号
67 if (PUNCTUATIONS.includes(char)) {
68 tokens.push({ type: TOKEN_TYPES.PUNCTUATION, value: char });
69 current++;
70 continue;
71 }
72
73 current++;
74 }
75
76 return tokens;
77}
定义了一组令牌类型,包括标识符、数字、运算符、标点符号和关键字。然后,我们使用正则表达式和数组常量来定义这些令牌类型的规则。
tokenize 函数中,遍历源代码中的每个字符,并根据其类型生成相应的令牌。例如,如果字符是数字,则我们将其解析为数字令牌,并将其添加到令牌序列中。
代码生成器:将语法树转换为可执行的机器代码
代码生成器(Code Generator)是编译器中的一个组件,用于将抽象语法树(AST)转换为目标代码,例如机器代码、字节码或其他编程语言的代码。
代码生成器通常由两个主要部分组成:代码生成规则和代码生成器。代码生成规则是一组规则,用于描述如何将 AST 节点转换为目标代码。代码生成器则根据这些规则,对 AST 节点进行遍历,并将其转换为目标代码。
点击查看代码生成器的实现
1function generate(node) {
2 if (node.type === 'Program')
3 return node.body.map(generate).join('\n')
4
5 if (node.type === 'NumberLiteral')
6 return node.value
7
8 if (node.type === 'Identifier')
9 return node.name
10
11 if (node.type === 'CallExpression')
12 return `${node.name}(${node.params.map(generate).join(', ')})`
13
14 throw new Error(`Invalid AST node: ${node.type}`)
15}
执行器:执行机器代码并输出结果
执行器(Executor)是编译器中的一个组件,用于执行目标代码,例如机器代码或字节码,并输出结果。执行器通常由两个主要部分组成:解释器和虚拟机。
解释器是一种直接执行目标代码的方法,它将目标代码逐条解释并执行。虚拟机是一种模拟计算机硬件的方法,它将目标代码转换为一组指令,并在虚拟计算机上执行这些指令。
点击查看 JavaScript 编译器的实现
1function execute(code) {
2 const program = compile(code)
3 const bytecode = generate(program)
4 const instructions = parse(bytecode)
5 const vm = createVM(instructions)
6 const result = vm.run()
7 return result
8}
9
10function createVM(instructions) {
11 let ip = 0
12 let sp = -1
13 const stack = Array.from({ length: 256 }).fill(0)
14
15 function push(value) {
16 stack[++sp] = value
17 }
18
19 function pop() {
20 return stack[sp--]
21 }
22
23 function run() {
24 while (ip < instructions.length) {
25 const instruction = instructions[ip++]
26
27 switch (instruction.opcode) {
28 case 'LOAD': {
29 push(instruction.value)
30 break
31 }
32 case 'ADD': {
33 const b = pop()
34 const a = pop()
35 push(a + b)
36 break
37 }
38 case 'SUB': {
39 const b = pop()
40 const a = pop()
41 push(a - b)
42 break
43 }
44 case 'MUL': {
45 const b = pop()
46 const a = pop()
47 push(a * b)
48 break
49 }
50 case 'DIV': {
51 const b = pop()
52 const a = pop()
53 push(a / b)
54 break
55 }
56 case 'PRINT': {
57 const value = pop()
58 console.log(value)
59 break
60 }
61 default: {
62 throw new Error(`Invalid opcode: ${instruction.opcode}`)
63 }
64 }
65 }
66
67 return pop()
68 }
69
70 return { run }
71}
在这个例子中,我们定义了一个 execute 函数,它接受一个 JavaScript 源代码字符串作为输入,并将其编译为目标代码,然后使用虚拟机执行目标代码,并输出结果。
在 createVM 函数中,我们定义了一组虚拟机指令,包括 LOAD(将常量加载到栈中)、ADD(将栈顶两个值相加)、SUB(将栈顶两个值相减)、MUL(将栈顶两个值相乘)、DIV(将栈顶两个值相除)和 PRINT(打印栈顶的值)。然后,我们使用一个简单的栈来模拟虚拟机的堆栈,并在 run 函数中执行指令序列。
在 execute 函数中,我们首先将源代码编译为目标代码,然后将其解析为指令序列,并使用 createVM 函数创建一个虚拟机。最后,我们调用虚拟机的 run 函数,执行指令序列,并输出结果。