使用JavaScript语言实现迷你版本的编译器(四)-目标代码生成

在前三篇文章中，我们已经完成了词法分析、语法分析、构建了抽象语法树 ( AST ) 。 在这一篇中将介绍如何将 AST 转换成可以执行的 JavaScript 代码。理解这一过程对学习编译原理以及掌握编译器的工作流程至关重要。

1. 概念讲解

目标代码生成是编译过程的最后一步，它的任务是将前面步骤生成的抽象语法树 (AST) 转换成目标语言代码。

在我们这个例子中，生成目标 JavaScript 代码的逻辑还是相对比较简单的，接下来我们将通过具体的代码示例来一步步探索这一转换过程。

2. 实现目标代码生成

2.1 逻辑梳理

首先通过一个流程图来整理生成目标代码的一些逻辑，以便于更好的理解每一步的作用：

codeGenerator(astNode)
  │
  ├───> 类型：Program
  │       │
  │       └───> 遍历 body 中所有节点
  │             │
  │             └───> 对每个子节点调用 codeGenerator
  │                   │
  │                   └───> 拼接所有生成的代码，用换行符分隔
  │
  ├───> 类型：ExpressionStatement
  │       │
  │       └───> 调用 codeGenerator 处理 expression 属性
  │             │
  │             └───> 在生成的代码后加上分号
  │
  ├───> 类型：CallExpression
  │       │
  │       ├───> 调用 codeGenerator 处理callee属性
  │       │     │
  │       │     └───> 生成函数名
  │       │
  │       └───> 遍历 arguments 中所有节点
  │             │
  │             └───> 对每个参数节点调用 codeGenerator
  │                   │
  │                   └───> 拼接所有参数代码，用逗号分隔
  │                         │
  │                         └───> 生成完整的函数调用代码，参数用圆括号括起
  │
  ├───> 类型：Identifier
  │       │
  │       └───> 返回节点的name
  │
  ├───> 类型：NumberLiteral
  │       │
  │       └───> 返回节点的value
  │
  ├───> 类型：StringLiteral
  │       │
  │       └───> 返回节点的value，两侧加上双引号
  │
  └───> 类型：未知
        │
        └───> 抛出TypeError异常

2.2 编写代码

接下来根据上面梳理的逻辑，逐步开始实现 codeGenerator() 函数。 这个函数主要是遍历 AST 生成对应的 JavaScript 代码。

function codeGenerator(node) {
    // 根据节点类型进行分别处理

    switch (node.type) {
        //  针对 Program 节点,我们直接遍历 body 数组中的每一个节点
        // 并调用 codeGenerator 函数,通过换行符连接起来
        case "Program":
            return node.body.map(codeGenerator).join("\n");

        // 对于表达式语句节点,我们将内嵌的表达式调用 codeGenerator 函数,生成的代码后面添加一个分号
        case "ExpressionStatement":
            return (
                // 添加分号是因为我们需要遵守正确的代码风格
                codeGenerator(node.expression) + ";"
            )

        // 函数调用表达式处理,添加一个左括号,然后遍历 arguments 数组对每个参数调用 codeGenerator 函数,使用逗号串联起来,再添加一个右括号
        case "CallExpression":
            return (
                // 被调用的代码
                codeGenerator(node.callee) +
                // 函数入参
                "(" +
                node.arguments.map(codeGenerator).join(", ")
                + ")"
            );
        // 针对标识符直接返回节点名字即可
        case "Identifier":
            return node.name;
        // 针对数字字面量直接返回节点的值
        case "NumberLiteral":
            return node.value;
        // 字符串再值两边添加引号
        case "StringLiteral":
            return '"' + node.value + '"';

        // 未知的类型直接抛出错误
        default:
            throw new TypeError(node.type);
    }
}

3. 代码测试

在 test.js 函数中添加如下代码：

const {
    codeGenerator,
} = require('./tiny-js-compiler');


const assert = require('assert');


const output = 'add(2, subtract(4, 2));';

const newAst = {
    type: 'Program',
    body: [{
        type: 'ExpressionStatement',
        expression: {
            type: 'CallExpression',
            callee: {
                type: 'Identifier',
                name: 'add'
            },
            arguments: [{
                type: 'NumberLiteral',
                value: '2'
            }, {
                type: 'CallExpression',
                callee: {
                    type: 'Identifier',
                    name: 'subtract'
                },
                arguments: [{
                    type: 'NumberLiteral',
                    value: '4'
                }, {
                    type: 'NumberLiteral',
                    value: '2'
                }]
            }]
        }
    }]
};


assert.deepStrictEqual(codeGenerator(newAst), output, 'Code Generator should turn `newAst` into `output` string');

console.log('Test case Passed!');

执行运行命令：

node test.js

如果看到 Test case Passed! 则说明测试通过，编写的 parser() 函数达到了我们想要的效果。

4. 总结

至此，我们已经完成了迷你编译器的目标代码生成部分。 这个小型的编译器随便很简单，但是却包含了编译过程中的关键技术。 通过接触这个项目，可以为深入学习现代编译器提供一个良好的基础。