LLVM学习入门(1):Kaleidoscope语言及词法分析

该学习是来源于LLVM的 My First Language Frontend with LLVM Tutorial，目的是通过LLVM实现了一个简单的编译器，在学习的过程中加入自己的一些理解笔记。

1.1 Kaleidoscope语言

我们的目标就是实现对Kaleidoscope语言如下代码的编译。

# 利用递归，计算 x 的斐波那契数列
def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)
# 假设 x = 40
fib(40)
1
2
3
4
5
6
7
8

为了代码的简单，我们假设我们使用的数值类型都是64位的浮点型，类似C++中的double类型。

同时LLVM JIT实现了调用标准库函数功能，所以我们可以是使用extern关键字定义函数。例如：

# 定义函数
extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);
# 调用函数
atan2(sin(.4), cos(42))
1
2
3
4
5
6

1.2 词法分析

实现一种语言，第一步是处理文本文件了解其意思，也就是词法分析，其功能是将文本输入转换为多个 tokens。例如如下例子：

# 源代码
atan2(sin(.4), cos(42))
1
2

转换为：

# tokens
tokens = ["atan2", "(", "sin", "(", .4, ")", ",", "cos", "(", 42, ")", ")"]
1
2

我们利用C++来编写这个Lexer词法分析。

1.2.1 定义 token

// 如果不是以下情况，Lexer返回[0-255]的ASCII值，否则返回以下枚举值
enum Token {
  TOKEN_EOF = -1,         // 文件结束标识符
  TOKEN_DEF = -2,         // 关键字def
  TOKEN_EXTERN = -3,      // 关键字extern
  TOKEN_IDENTIFIER = -4,  // 名字
  TOKEN_NUMBER = -5       // 数值
};

std::string g_identifier_str;  // 如果输入是标识符
double g_number_val;           // 如果输入是数字
1
2
3
4
5
6
7
8
9
10
11

我们设置了五个枚举，分别代表不同的数值，如果不在这五个枚举，我们将返回其的ASCII值。为了简单，我们设置了两个全局变量，分别代表标识符和数字。

1.2.2 Gottok 函数

// 从标准输入解析一个Token并返回
int GetToken() {
  static int last_char = ' ';
  // 忽略空白字符
  // isspace 是空白字符返回 true
  while (isspace(last_char)) {
    last_char = getchar();
  }
  // 识别字符串
  // isalpha 判断是否为字符，是字母返回 true 
  if (isalpha(last_char)) {
    g_identifier_str = last_char;
    // isalnum 是字母或者数字返回 true
    while (isalnum((last_char = getchar()))) {
      g_identifier_str += last_char;
    }
    // 判断字符串是否为上边枚举的关键字
    if (g_identifier_str == "def") {
      return TOKEN_DEF;
    } 
    else if (g_identifier_str == "extern") {
      return TOKEN_EXTERN;
    } 
    else {
      return TOKEN_IDENTIFIER;
    }
  }
  // 识别数值
  // isdigit 如果是数字，返回 true
  // 小数点也是数字的一部分
  if (isdigit(last_char) || last_char == '.') {
    std::string num_str;
    do {
      num_str += last_char;
      last_char = getchar();
    } while (isdigit(last_char) || last_char == '.');
    // strtod 函数将字符串 num_str 转换为浮点数
    g_number_val = strtod(num_str.c_str(), nullptr);
    return TOKEN_NUMBER;
  }
  // 忽略注释
  if (last_char == '#') {
    do {
      last_char = getchar();
    } while (last_char != EOF && last_char != '\n' && last_char != '\r');

    if (last_char != EOF) {
      return GetToken();
    }
  }
  // 识别文件结束
  if (last_char == EOF) {
    return TOKEN_EOF;
  }
  // 如果没有以上定义的关键字或者数值，则直接返回 ASCII
  int this_char = last_char;
  last_char = getchar();
  return this_char;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

使用词法分析对前面的 Kaleidoscope 源码处理结果如下，用空格隔开：

def fib ( x ) if x < 3 then 1 else fib ( x - 1 ) + fib ( x - 2 ) fib ( 40 ) extern sin ( arg )
extern cos ( arg ) extern atan2 ( arg1 arg2 ) atan2 ( sin ( 0.4 ) , cos ( 42 ) )
1
2

在下一篇：LLVM学习入门(2):实现解析器 Parser 和语法树 AST 中，我们将描述实现整个解析器，从而最终输出构建构建语法树 AST。