js编译原理 自己实现

实现简易 JavaScript 编译器的核心步骤

词法分析（Lexical Analysis）

词法分析器将源代码字符串分解为有意义的标记（tokens）。每个 token 包含类型和值，例如标识符、数字、运算符等。

function tokenize(code) {
  const tokens = [];
  let current = 0;

  while (current < code.length) {
    let char = code[current];

    // 跳过空白字符
    if (/\s/.test(char)) {
      current++;
      continue;
    }

    // 处理数字
    if (/[0-9]/.test(char)) {
      let value = '';
      while (/[0-9]/.test(code[current])) {
        value += code[current++];
      }
      tokens.push({ type: 'NUMBER', value });
      continue;
    }

    // 处理标识符和关键字
    if (/[a-zA-Z]/.test(char)) {
      let value = '';
      while (/[a-zA-Z0-9]/.test(code[current])) {
        value += code[current++];
      }
      tokens.push({ type: 'IDENTIFIER', value });
      continue;
    }

    // 处理运算符
    if (/[\+\-\*\/=]/.test(char)) {
      tokens.push({ type: 'OPERATOR', value: char });
      current++;
      continue;
    }

    throw new Error(`Unknown character: ${char}`);
  }

  return tokens;
}

语法分析（Syntax Analysis）

语法分析器将 tokens 转换为抽象语法树（AST）。这里使用递归下降解析法处理简单的算术表达式。

function parse(tokens) {
  let current = 0;

  function walk() {
    let token = tokens[current];

    if (token.type === 'NUMBER') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value
      };
    }

    if (token.type === 'IDENTIFIER') {
      current++;
      return {
        type: 'Identifier',
        name: token.value
      };
    }

    if (token.type === 'OPERATOR') {
      const node = {
        type: 'BinaryExpression',
        operator: token.value,
        left: null,
        right: null
      };
      current++;
      node.left = walk();
      node.right = walk();
      return node;
    }

    throw new TypeError(token.type);
  }

  return walk();
}

代码生成（Code Generation）

将 AST 转换为目标代码（如机器码或中间代码）。以下示例生成类似汇编的指令。

function generate(ast) {
  switch (ast.type) {
    case 'NumberLiteral':
      return `PUSH ${ast.value}`;

    case 'Identifier':
      return `LOAD ${ast.name}`;

    case 'BinaryExpression':
      const left = generate(ast.left);
      const right = generate(ast.right);
      return `${left}\n${right}\n${ast.operator.toUpperCase()}`;

    default:
      throw new TypeError(ast.type);
  }
}

完整流程示例

测试一个简单表达式 3 + 5 * 2 的编译过程：

const tokens = tokenize('3 + 5 * 2');
const ast = parse(tokens);
const output = generate(ast);

console.log(output);
/*
PUSH 3
PUSH 5
PUSH 2
*
+
*/

扩展功能方向

支持控制结构

增加 if 语句和循环的处理逻辑。需要在词法分析阶段识别新关键字，并在语法分析中增加相应节点类型。

类型系统

实现简单的类型检查，可在语法分析阶段验证操作数类型是否匹配。

优化策略

在代码生成阶段加入常量折叠等优化技术，例如预先计算 2 + 3 替换为 5。

目标代码选择

除了低级指令，还可选择生成其他高级语言代码（如 C 或 Python），或直接生成 JavaScript 可执行代码。

实现完整编译器需要逐步扩展这些模块，每个阶段都可能需要迭代优化。建议从简单算术表达式开始，逐步增加语言特性。