编译器中的Lexer，词法分析器

最近在对LLVM IR起了兴趣，应为它可以将它支持的所有编程语言都转换成同一个IR语言。LLVM IR生成步骤有三步，首先是词法解析，然后是语法分析生成AST，然后AST可以通过代码生成，得到IR。我是跟着LLVM的官方教程学习的，这个教程通过一个很简单的，虚构的编程语言Kaleidoscope来教你一步步实现自己的编程语言以及对应的编译器。

Kaleidoscope语言

Kaleidoscope是一个程序性语言，简单起见，我们规定Kaleidoscope中的数字类型仅有双精度浮点数类型，因此也无需进行类型声明。这样Kaleidoscope就有了很简单的语法，下面的例子是Kaleidoscope写成的斐波那契数列函数。

# Compute the x'th fibonacci number.
def fib(x)
  if x < 3
    return 1
  else
    return fib(x-1)+fib(x-2)

# This expression will compute the 40th number.
fib(40)

此外，我们还允许Kaleidoscope调用标准库中的函数，之后的LLVM JIT会使实现这个功能变得非常简单。Kaleidoscope通过关键字extern在使用之前定义一个函数（在手动定义递归函数中也有用），下面是一个例子。

# 声明三个标准库中的函数
extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

atan2(sin(.4), cos(42))

这里我们可以基本上理解了Kaleidoscope语言的基本语法，下面就开始实现这个语言的第一步，词法分析器。

词法分析器，Lexer

首先介绍一下编译器编译代码的第一步，词法分析器，Lexer。

词法分析器处理编程语言的代码文本，并理解这些文本表达了什么。词法分析器lexer（也称为scanner），将代码文本识别成一系列token，每个token被识别为一个编程语言中的定义，例如关键字，标识符，literal等。每个token包含一个token的代码以及可能的一些信息（例如，如果该token是一个数字，那么包含的信息还有这个数字的值）。

下面，我们将所有可能出现的token类型进行枚举。

// 词法分析器如果遇到识别不了的字符，那么返回该字符的ASCII码，即[0-255]
// 如果是可以识别的类型，那么返回下面定义的负数。
enum Token
{
    tok_eof = -1,   // end of file

    // 关键字
    tok_def = -2,
    tok_if = -3,
    tok_else = -4,
    tok_return = -5,

    // 主要类型
    tok_identifier = -6,
    tok_number = -7,

    // 注释
    tok_comment = -8
};

static std::string identifier_str;  // 如果识别为identifier，那么将它的文本储存到这里
static double num_val;              // 如果识别为数字，那么将其值储存到这里
static std::string comment_line;    // 如果识别为注释，那么将注释字符串储存到这里

Lexer返回的每个token只有两种情况，一是上面枚举类型中存在的负数，二是不能识别的字符，例如”+”，这时lexer返回的是该字符的ASCII码值，范围为0-255。

如果识别到标识符identifier，那么我们将该标识符的名称赋值给identifier_str。如果识别到数字，那么我们将该数字表示的值赋值给num_val。如果识别到注释行，那么我们将注释的字符串赋值给comment_line。注意这里我们简单起见，使用的是全局变量来储存这些值，但这并不是一个好的选择，在真实的编译器实现中，显然不会用这个函数。

Lexer的实现是通过一个函数get_tok实现的，它持续读取代码文本的下一个字符，直到识别到下一个token并返回。下面我们通过一个简单的实现对这个函数进行解释。

std::ifstream fin;  // 全局变量，C++读文件的流，在使用时应先打开一个文件，最后关闭

// 返回的是int值，如果是负数，则是之前定一个Token枚举类型中的值
// 如果是正数，则是未识别的字符的ASCII码
int get_tok()
{
    // 读取到的字符
    static int last_char = ' ';
    // 通过fin.get()函数从标准输入中一次读取一个字符
    // 首先是跳过所有的空白字符
    while (isspace(last_char))
        last_char = fin.get();

    // 然后是识别标识符，并判断是不是关键字
    // 标识符identifier的正则: [a-zA-Z][a-zA-Z0-9_]*
    // 标识符仅由字母，数字和下划线组成，并由字母开头
    // isalpha判断当前字符是否是字母
    if (isalpha(last_char))
    {
        // 全局变量identifier_str储存标识符的名称
        identifier_str = last_char;
        last_char = fin.get();
        // isalnum判断是否是字母或数字
        // 符合标识符命名的情况下，持续读取
        while (isalnum(last_char) || last_char == '_')
        {
            // 将下一个字符拼接到标识符名称后
            identifier_str += last_char;
            // 读取下一个字符
            last_char = fin.get();
        }

        // 判断识别到的标识符是否是关键字
        // 如果是关键字，则返回关键字对应的token id
        if (identifier_str == "def")
            return tok_def;
        else if (identifier_str == "if")
            return tok_if;
        else if (identifier_str == "else")
            return tok_else;
        else if (identifier_str == "return")
            return tok_return;
        // 如果不是关键字，则表明是自定义标识符，返回identifier的id
        // 这时自定义的标识符的名字则储存在全局变量identifier_str中
        return tok_identifier;
    }

    // 然后是数字，简单起见，我们将这里的数字的正则定义为[0-9.]+
    if (isdigit(last_char) || last_char == '.')
    {
        // num_str用来储存数字值的字符串
        std::string num_str;
        do
        {
            num_str += last_char;
            last_char = fin.get();
        }
        while (isdigit(last_char) || last_char == '.');
        
        // 接下来需要将用字符表示的值转换为双精度浮点值
        // strtod是C标准库中的函数，将str转换为双精度浮点值
        num_val = strtod(num_str.c_str(), nullptr);
        // 返回数字的id，同时数字的值被储存在全局变量num_val中
        return tok_number;

        // 由于我们简单起见将数字定义为[0-9.]+，这会导致一个问题
        // 就是这也会识别例如1.23.4.5这样的序列，这在strtod函数后只会保留前面有效的部分，即1.23，这是不对的
        // 因此在真正实现时还要考虑这一点，例如限制小数点只能识别到一次等
    }

    // 接下来是注释，之前我们也了解到Kaleidoscope语言的注释仅有行注释，而没有块注释，行注释由#号开始
    // 因此当识别到#时，表示接下来的一行都是注释
    if (last_char == '#')
    {
        comment_line = last_char;
        do
        {
            last_char = fin.get();
            comment_line += last_char;
        }
        while (last_char != EOF && last_char != '\n' && last_char != '\r');
        // 只要不识别到文件结束，或者换行，则都是注释的内容
        // 最后将注释的id返回，此时注释的内容储存在全局变量comment_line中
        return tok_comment;
    }

    // 判断是否是到了文件结束
    if (last_char == EOF)
        return tok_eof;

    // 如果当前字符串不是Token枚举类中列出的，则将其ASCII码返回
    int this_char = last_char;
    last_char = fin.get();
    return this_char;
}

到这里我们就完成了一个简单的lexer的核心，get_tok函数。我们在外面再写一个驱动，用于循环调用get_tok函数，并接受它的输出，对它识别到的每一个token进行我们需要的处理，下面我们写一个简单的函数，将get_tok函数读取到的token输出。

int main()
{
    fin.open("fibonacci.ks", std::ios::in);
    if (!fin.is_open())
    {
        std::cout << "Cannot open file 'fibonacci.ks'." << std::endl;
        return 1;
    }
    while (true)
    {
        int res = get_tok();
        if (res == tok_def || res == tok_if || res == tok_else || res == tok_return)
        {
            std::cout << "Keywords: " << identifier_str << std::endl;
        }
        else if (res == tok_identifier)
        {
            std::cout << "Identifier: " << identifier_str << std::endl;
        }
        else if (res == tok_number)
        {
            std::cout << "Number: " << num_val << std::endl;
        }
        else if (res == tok_comment)
        {
            std::cout << "Comment line: " << comment_line << std::endl;
        }
        else if (res == tok_eof)
        {
            std::cout << "End of file" << std::endl;
        }
        else
        {
            std::cout << "Unknown char: " << char(res) << ", ASCII code: " << res << std::endl;
        }

        if (res == EOF)
        {
            fin.close();
            return 0;
        }
    }
}

这时我们将上面的斐波那契数列的Kaleidoscope代码储存在fibonacci.ks文件中，就可以得到下面的输出。

Comment line: # Compute the x'th fibonacci number.

Keywords: def
Identifier: fib
Unknown char: (, ASCII code: 40
Identifier: x
Unknown char: ), ASCII code: 41
Keywords: if
Identifier: x
Unknown char: <, ASCII code: 60
Number: 3
Keywords: return
Number: 1
Keywords: else
Keywords: return
Identifier: fib
Unknown char: (, ASCII code: 40
Identifier: x
Unknown char: -, ASCII code: 45
Number: 1
Unknown char: ), ASCII code: 41
Unknown char: +, ASCII code: 43
Identifier: fib
Unknown char: (, ASCII code: 40
Identifier: x
Unknown char: -, ASCII code: 45
Number: 2
Unknown char: ), ASCII code: 41
Comment line: # This expression will compute the 40th number.

Identifier: fib
Unknown char: (, ASCII code: 40
Number: 40
Unknown char: ), ASCII code: 41
End of file

到这里我们就实现了一个简单的词法分析器，接下来，就到了parser和AST的实现了。