如何编写 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)

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}

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}