使用JavaScript语言实现迷你版本的编译器(二)-语法分析

编译原理 JavaScript

使用JavaScript语言实现迷你版本的编译器(二)-语法分析

上一篇文章主要介绍了如何将源代码转换为一系列的 tokens 。本篇将开始讲解如何将这些 **tokens ** 转换为抽象语法树。

1. 概念讲解

1.1 什么是语法分析？

语法分析 ( Parsing) 是编译过程中的一个阶段，它接受词法分析阶段生成的 tokens，并将他们组织成语法结构。这种结构通常表示为一个树，即抽象语法树 AST （Abstract Syntax Tree）。抽象语法树是源代码的层级表示，展示了代码的各个部分如何组合在一起。

1.2 关键术语

Token，中文直译过来就是令牌的意思。它是词法解析的产出物，代表了源代码中最小的有意义的单元，比如数字、字符串、括号等等。
AST ，抽象语法树，是代码的树形结构表示方法，可以展示代码各部分语法关联关系。每个节点代表代码中的一构造，比如一个数字、一个字符串，或者一个函数调用。

1.3 使用图来说明 AST

为了更好地理解 AST，我们可以将其可视化。考虑以下的数学表达式：

(add 2 (subtract 4 2))

对应的 AST 可以用一棵树来表示，其中每个节点都是一个操作或值：

      CallExpression (add)
      /             \
 NumberLiteral (2)   CallExpression (subtract)
                    /               \
         NumberLiteral (4)   NumberLiteral (2)

这个树状结构清晰地表明了代码的逻辑结构：一个add函数调用包含了两个参数，其中一个参数是数字2，另一个是 subtract 函数调用的结果。

1.4 从 tokens 到 AST 的结构变化

下面展示了从 tokens 到 AST 的结构变化

tokens：

[                                        
     { type: 'parenthesis', value: '(' },       
     { type: 'name', value: 'add' },      
     { type: 'number', value: '2' },      
     { type: 'parenthesis', value: '(' },       
     { type: 'name', value: 'subtract' }, 
     { type: 'number', value: '4' },      
     { type: 'number', value: '2' },      
     { type: 'parenthesis', value: ')' },       
     { type: 'parenthesis', 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"
                        }
                    ]
                }
            ]
        }
    ]
}

上面的 AST 主要反映了 Lisp 语言源代码的结构：一个 add 函数的调用，包括两个参数，一个是数字2，另一个是 subtract 的函数调用。

2. 实现语法分析器

2.1 逻辑梳理

在转换前，让我们先理清楚逻辑。我们的目标肯定是要先遍历 tokens 数组，将遇到的每一个 token 先转化成 AST 节点。当我们遇到函数调用时，例如包括括号和函数名，我们需要特别注意，这里面可能会包含嵌套的表达式，处理的时候我们需要使用递归的方法去处理。

首先我们将创建一个 walk() 函数，它的主要职责为处理单个 token ，并返回相应的 AST 节点，函数的大体逻辑如下：

碰到 number 类型 token ,转为 AST NumberLiteral 节点，并将token的值作为节点的值。
碰到 string 类型 token ,转换为 AST StringLiteral 节点，并将token的值作为节点的值。
碰到 parenthesis 类型并且是 ( ，说明这是一个函数调用的开始。这里需要创建一个 CallExpression 的节点，同时使用递归去处理函数参数。
遇到未知的 token 类型，直接抛出一个错误。

这个过程有点像小时候搭积木一样，我们逐个检查每一个 token ，并决定如何将它们组成更大的结构。

2.2 编写代码

按照上面梳理的逻辑，我们开始逐步实现这个函数。

function parser(tokens) {
    // 这个函数主要将 tokens 转换为 ast 语法
    let currentIndex = 0;  // 跟踪 token 数组中位置

    // 定义 walk 函数用来遍历 tokens ,同时使用递归的方式, 不再使用 while 循环
    function walk() {
        let token = tokens[currentIndex];

        // 1. 处理 number 类型,转为 AST NumberLiteral 节点
        // 假设我们有一个数字 token { type: 'number', value: '2' }，解析器会创建一个节点 { type: 'NumberLiteral', value: '2' }。
        if (token.type === 'number') {
            currentIndex++;
            return {
                "type": "NumberLiteral",
                "value": token.value
            }
        }

        // 2. 处理 string类型,转换为 AST  StringLiteral 节点
        if (token.type === 'string') {
            currentIndex++;
            return {
                "type": "StringLiteral",
                "value": token.value
            }
        }

        // 3. 创建 CallExpression 节点(CallExpressions)

        // 3.1 如果遇到当前的类型为 parenthesis 并且为 ( 的话,我们直到这是一个函数调用的开始
        if (token.type === 'parenthesis' && token.value === '(') {
            // 3.2 跳过当前的开括号
            currentIndex++;
            token = tokens[currentIndex];

            // 定义一个 CallExpression 类型的节点, name为当前 Token 的value. 定义一个空的参数数组(params).
            // 假设我们的 tokens 数组是这样的：[{ type: 'paren', value: '(' }, { type: 'name', value: 'add' }, ...]，解析器将创建一个节点 { type: 'CallExpression', name: 'add', params: [] }。

            let astNode = {
                "type": "CallExpression",
                "name": token.value,
                "params": []
            }

            // 3.3 跳过函数名字的 token
            currentIndex++;
            token = tokens[currentIndex];


            // 处理参数
            // 3.4 由于函数的参数可能会是复杂的表达式,包括其他函数的调用. 我们需要递归调用 walk 函数来处理每个函数

            // 在 Lisp中是支持 嵌套的括号的,我们接下来将会处理这种情况
            //   (add 2 (subtract 4 2)) 的 token 会是下面这样
 
            
            // 上面的函数调用解析器将首先为 add 创建一个 'CallExpression' 节点，并且其参数将是一个数字字面量和另一个 'CallExpression' 节点。
            // 后面的节点又是一个需要递归解析的节点
            // 所以我们碰到嵌套的 CallExpression 时,使用 walk 函数递归进行处理
            // 直到遇到闭合括号
            // 循环中将调用 walk 函数返回一个节点,我们将节点放到 node.params 中
            while (
                (token.type !== 'parenthesis') ||
                (token.type === 'parenthesis' && token.value !== ')')
                ) {
                // 调用 walk 函数将返回的节点加入到参数中

                astNode.params.push(walk());
                token = tokens[currentIndex]
            }

            // 跳过闭合括号
            currentIndex++;

            return astNode;
        }


        // 其他类型直接抛出异常
        throw new TypeError(token.type);
    }


    // 创建 AST 根节点  Program
    let rootNode = {
        "type": "Program",
        body: []
    }

    // 开始遍历 tokens, 将通过 walk() 函数返回的节点压入 rootNode.body 中
    // 之所以要这么循环的原因是可能有连续的 CallExpression ,不仅仅是嵌套
    // 如果 tokens 数组表示 (add 2 2) (subtract 4 2)，AST 的 body 将包含两个 'CallExpression' 节点。
    while (currentIndex < tokens.length) {
        rootNode.body.push(walk());
    }

    
    return rootNode;
}

这段代码实现了我们之前描述的逻辑，定义了一个 walk() 方法来递归构建抽象语法树。 parser() 方法初始化了 AST 并且填充了 body 属性，最后返回完整的抽象语法树。

这里需要注意的是，我们假设方法的入参是完全正确的，并没有使用额外的逻辑去判断是否有语法错误或者其他的异常情况。

3. 代码测试

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

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


const assert = require('assert');


const tokens = [
    {type: 'parenthesis', value: '('},
    {type: 'name', value: 'add'},
    {type: 'number', value: '2'},
    {type: 'parenthesis', value: '('},
    {type: 'name', value: 'subtract'},
    {type: 'number', value: '4'},
    {type: 'number', value: '2'},
    {type: 'parenthesis', value: ')'},
    {type: 'parenthesis', value: ')'}
];

const 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'
            }]
        }]
    }]
};


assert.deepStrictEqual(parser(tokens), ast, 'Parser should turn `tokens` array into `ast`');

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

执行运行命令：

node test.js

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

4. 结语

下一章节我们将进行抽象语法树的转换。