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

编译原理 JavaScript

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

1. 基本介绍

词法分析，也称作分词 ( 英文术语为 tokenizer 或者是 lexer ) ，是编译过程的第一个阶段。它的作用是将输入的源代码字符串拆分为一系列标记 ( 英文术语是 tokens ) 。这些 tokens 是构成编程语言的基本元素，比如数字、字符串、括号、操作符等。

在本教程中，我们将用 JavaScript 编写一个简易的编译器，处理 Lisp 风格的源代码并转换成 JavaScript 风格的源代码。 Lisp 语言使用其独特的 **前缀表示法 **( 也称作 Polish Notation) 而著名，它将操作置于操作符前面，这样使得嵌套函数的调用表示更为自然。对于习惯了其他语言的写法的话，看到这种写法可能会有点不太适应。

例如，下面是一个 Lisp 语言的表达式：

(add 2 (subtract 4 2))

这个表达式的执行流程如下：

先执行 (subtract 4 2) 表示执行 4 - 2 ，结果为 2。
再执行 add 函数进行相加，跟之前的结果 2 相加后得到结果 2 + 2 = 4

通过词法分析，上述 Lisp 表达式可以转换为下面的 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: ')' },       
]

这种代表源代码的结构，可以很清晰的反映原始语句的结构，而且也可以为后面的语法分析提供了便利。词法分析的过程也有点像我们做英语阅读时，将长难句拆分成一段段的短句以及标点符号。这样拆分有助于我们理解和解释文本的含义。同样的，在编译器中，这有助于我们理解和解释源代码的含义。

2. 实现词法分析器

2.1 逻辑梳理

在开始编写代码前，我们先思考下如何解析上面的这条语句 (add 2 (subtract 4 2)) 。

分析流程大概如下：

循环遍历整个语句字符串。
根据不同的 token 进行不同的处理。这里判断 token 的类型，我们可以使用正则进行匹配，可以很方便地判断对应的类型。
如果匹配到未知的 token ，就直接抛出异常即可。

针对不同类型标记 (token) 的处理逻辑如下：

括号：如果匹配到 ( 或者 ) ，直接添加到 token 集合中。
空格：如果匹配到空格，就直接跳过去，空格只是用来分割代码中的元素。
数字：如果匹配到数字的话，数字可能会有好几位，要一直匹配到不是数字为止，将整个数字当做一个 token。
字符串：如果遇到 " 的话，说明这是个字符串的开始，继续往后进行读取，直接遇到闭合的 " 为止，将整个字符串当做一个 token。
标识符：如果遇到字母的话，说明应该是一个函数名或者是变量名。向后进行读取，直到不是大小写字母为止。最后将整个标识符当做一个 token。

2.2 代码实现

有了上面的大致逻辑后，开始编写相对应的代码，这里新建一个 tiny-js-compiler.js 文件，按照上面的逻辑逐步实现代码：

function tokenizer(input) {
    // 当前的一个遍历字符串的下标
    let currentIndex = 0;
    let tokens = [];

    while (currentIndex < input.length) {
        // 1. 处理 (
        
        // 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 (
        let currentChar = input[currentIndex];
        if (currentChar === '(') {
            tokens.push({
                "type": "parenthesis",
                "value": "("
            });
            currentIndex++;
            continue
        }

        // 2. 处理)
        // 括号直接添加到 tokens数组即可, 类型为 parenthesis, 值为 )
        if (currentChar === ')') {
            tokens.push({
                "type": "parenthesis",
                "value": ")"
            });
            currentIndex++;
            continue
        }

        // 3. 处理空格
        // 使用正则匹配当前字符是否为空格,空格就直接跳过
        let spaceReg = /\s/
        if (spaceReg.test(currentChar)) {
            currentIndex++;
            continue
        }

        // 4. 处理数值
        let numberReg = /[0-9]/
        if (numberReg.test(currentChar)) {
            let numberString = "";
          
            // 数值使用正则去匹配,因为数值可能有多位, 所以需要在循环中再开一个循环.
            // 从当前位置开始向后依次遍历,一直遍历到不是数值的那位. 同时需要注意外层循环的 currentIndex 是需要一直变化的
            while (numberReg.test(currentChar)) {
                numberString = numberString + currentChar;
                currentIndex++;
                currentChar = input[currentIndex];
            }
             // 添加到 tokens 数组, 类型为 number, 值为获取到的数值
            tokens.push({
                "type": "number",
                "value": numberString
            })
            continue
        }

        // 5. 处理使用 " 包裹的字符串
        // 例子:  (concat "foo" "bar")
        if (currentChar === '"') {
            let wrapString = "";
            currentIndex++;

            // 从当前位置开始向后遍历,一直遍历到不是 " 的前一个位置.
        	// 获取2个 " 之间的字符
            while (currentChar !== '"') {
                wrapString = wrapString + currentChar;
                currentIndex++;
                currentChar = input[currentIndex];
            }
            
            // 添加到  tokens 数组, 类型为 string, 值就是字符串
            tokens.push({
                "type": "number",
                "value": wrapString
            })
        }

        // 6. 处理字母标识符
        // 使用正则判断是否为  a-z 的字母,这是 lisp 语言的定义
        // 循环往后查找为字母标识符的字符一直到结束
        // 添加到  tokens 数组, 类型为 name, 值就是字符串
        // 例子 (add 2 4)  . add 就是 name
        let letterReg = /[a-z]/
        if (letterReg.test(currentChar)) {
            let letterString = "";

            while (letterReg.test(currentChar)) {
                letterString = letterString + currentChar;
                currentIndex++;
                currentChar = input[currentIndex];
            }

            tokens.push({
                "type": "name",
                "value": letterString
            })
            continue
        }

        // 7. 其他类型
        // 直接抛出异常错误,暂时不支持这种类型
        throw new TypeError('unknown character is: ' + char);
    }


    return tokens;
}

3. 代码测试

验证代码逻辑是否符合预期，我们将编写一个测试用例来测试。

3.1 导出 tokenizer 函数

为了访问上面的 tokenizer() 函数，我们需要将函数暴露出去。在 tiny-js-compiler.js 的最底部添加如下代码：

..... 这里是tokenizer() 函数的代码

module.exports = {
    tokenizer
};

在 JavaScript 中，module.exports是CommonJS规范提供的一个特性，用于导出模块中的对象、函数、变量等，使其可以被其他JavaScript文件（模块）通过require函数导入并使用。

3.2 编写测试用例

这里在跟 tiny-js-compiler.js 的同级目录下新建一个 test.js文件，填入如下内容：

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

const assert = require('assert');

const input = '(add 2 (subtract 4 2))';

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

assert.deepStrictEqual(tokenizer(input), tokens, 'Tokenizer should turn `input` string into `tokens` array');

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

3.3 运行测试用例

这里我们直接使用 node 程序直接运行 test.js 文件，进入到源代码目录，使用命令行执行如下命令：

node test.js

如果看到 Test case Passed! 则说明测试通过，编写的 tokenizer() 函数达到了我们想要的效果。这里的 tokens 正是我们词法分析器的预期输出。函数将源代码文本转换成了一个易于后续处理的 tokens 数组。

4. 结语

接下来，我们将在下一章节我们将进行语法分析。