Kaleidoscope: Tutorial Introduction and the Lexer

Posted on Edited on In

The Basic Language

Kaleidoscope 是一个面向过程的语言, 允许你定义函数, 使用条件判断, 数学计算等. 在后面的教程中, 我们还会扩展 Kaleidoscope 使它支持 if/then/else 结构, 循环结构和用户定义的操作符.

Kaleidoscope 中唯一的数据类型是 64 bit 的浮点类型 (double in C). 下面是使用 Kaleidoscope 实现的斐波拉契数列.

1
2
3
4
5
6
7
8
# Compute the x'th Fibonacci Number
def fib(x)
    if x < 3
    then 1
    else fib(x-1) + fib(x-2)

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

我们还允许 Kaleidoscope 能够调用标准库函数 (LLVM JIT 能够轻易的实现它). 你可以使用 extern 关键字来定义一个函数.

1
2
3
4
5
extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

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

The Lexer

当实现一个语言时, 第一件事就是能够处理源代码文件, 并知道它想表达的意思. 传统的做法是使用 lexer (scanner) 将输入的源文件处理为 tokens. Lexer 返回的每个 token 都包括一个 token code 和一些 metadata (比如数字的值). 首先我们定义这些可能使用到的数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// The lexer return tokens [0-255]
// if it is an unknown character,
// otherwise one of these known things.
enum Token {
    tok_eof = -1,

    // commands
    tok_def    = -2,
    tok_extern = -3,

    // primary
    tok_identifier = -4,
    tok_number     = -5,
};

// Filled in if tok_identifier
static std::string IdentifierStr;
// Filled in if tok_number
static double NumVal;

Lexer 返回的每个 token 要么是 Token 枚举中的值, 要么是一个 “未知” 的字符的 ascii 值, 比如 +. 如果当前的 token 是一个标识符, 那么 IdentifierStr 会保存它的名字. 如果当前 token 是一个数字, 那么 NumVal 会保存它的值.

Lexer 实现是 gettok() 函数, gettok() 被调用之后, 会返回从标注输入中获取的下一个 token.

1
2
3
4
5
6
7
8
int gettok() {
    static int LastChar = ' ';

    // Skip any whitespace
    while (isspace(LastChar))
    {
        LastChar = getchar();
    }

gettok 通过调用 getchar() 从标准输入中读取字符, 并忽略 tokens 之间的空格, 它仅仅是将字符存储到 LastChar 中, 不进行处理.

gettok 接下来要识别标识符和关键字.

1
2
3
4
5
6
7
8
9
10
11
12
if (isalpha(LastChar)) {
    IdentifierStr = LastChar;
    while (isalnum(LastChar = getchar()))
    {
        IdentifierStr += LastChar;
    }

    if (IdentifierStr == "def") return tok_def;
    if (IdentifierStr == "extern") return tok_extern;

    return tok_identifier;
}

如果不是标识符和关键字，那进一步判断是否为数字.

1
2
3
4
5
6
7
8
9
10
11
if (isdigit(LastChar) || LastChar == '.') {
    std::string NumStr;
    do
    {
        NumStr += LastChar;
        LastChar = getchar();
    } while (isdigit(LastChar) || LastChar == '.');

    NumVal = strtod(NumStr.c_str(), 0);
    return tok_number;
}

当读取的字符为数字时, 使用 strtod() 将它转化为 double 并存储在 NumVal 中. 这一步没有做异常处理, 有需要的可以添加.

然后我们处理注释:

1
2
3
4
5
6
7
8
9
10
if (LastChar == '#') {
    // Comment until end of line
    do
    {
        LastChar = getchar();
    } while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
    // Return the next token
    if (LastChar != EOF)
        return gettok();
}

注释会跳过 # 后面所有的字符，直到下一行或者 EOF. 当跳过之后, 需要重新进行处理并返回下一个 token， 所以直接尾递归调用 gettok() 即可. 如果输入不匹配标识符和关键字, 也不匹配数字, 只有可能是 + 之类的操作符, 和 EOF.

1
2
3
4
5
6
7
8
9
10
// Check for end of file. Don't eat EOF
    if (LastChar == EOF) {
        return tok_eof;
    }

    // Otherwise, just return the character as its ascii value
    int ThisChar = LastChar;
    LastChar = getchar();
    return ThisChar;
}

以上就是 Kaleidoscope 的 lexer.