发表于 2022-07-24

|

更新于 2022-08-27

| 分类于 Compiler

Kaleidoscope

本教程我们将从零开始设计一门玩具版编程语言——Kaleidoscope。Kaleidoscope 支持函数定义、条件语句、数学运算等。在教程的各个章节中，我们将对 Kaleidoscope 的语言特性进行扩展，支持 if/then/else 语句、for 循环、自定义操作符、JIT 编译、调试信息等。

为了简化数据类型，我们设计的 Kaleidoscope 只有一种数据类型是 64 位浮点类型，即 C 语言中的 double 类型。因此，所有值都是隐式双精度类型，并且无需进行类型声明。如下所示，为基于 Kaleidoscope 的斐波那契计算方法。

def fib(x)
  if x < 3 then
    1
  else
    fib(x-1)+fib(x-2)

fib(40)

此外，我们将支持 Kaleidoscope 调用标准库函数。因此，我们可以在使用函数之前使用 extern 关键字来定义函数。例如：

extern sin(arg);
extern cos(arg);
extern atan2(arg1 arg2);

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

下面，我们开始为 Kaleidoscope 语言逐步实现编译器吧！

词法分析器

事实上，实现编程语言的本质其实是实现编程语言的编译器。首先，我们要实现编译器的文本处理与内容识别能力，即 词法分析器（Lexer）。词法分析器将输入内容分解为 token。词法分析器返回的每个 token 都包含相关元数据，如：token 值、token 类型等。如下所示，为 token 定义类型。

// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
    tok_eof = -1,

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

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

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

词法分析器返回的 token 的类型可以分为两大类：

• 预定义类型，即 Token 枚举中定义的枚举值，使用负整数表示。
• 未知字符，如：+，使用 [0-255] 正整数表示。

当词法分析器解析到 tok_identifier 类型或 tok_number 类型的 token 时，会进行以下处理。

• 如果当前 token 类型是 tok_identifier 时，则使用全局变量 IdentifierStr 保存标识符的名称，作为 token 值。
• 如果当前 token 类型是 tok_number，则使用全局变量 NumVal 保存数值，作为 token 值。

注意，这里其实与 lex 工具使用 yyval 保存 token 值，yytext 保存标识符有着异曲同工之妙。

词法分析器的核心部分由 gettok 函数实现。每一次调用 gettok 函数都将从标准输入中返回下一个 token。gettok 的具体实现如下所示：

/// gettok - Return the next token from standard input.
static int gettok() {
  static int LastChar = ' ';

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

if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
    IdentifierStr = LastChar;
    while (isalnum((LastChar = getchar())))
      IdentifierStr += LastChar;

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

if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
    std::string NumStr;
    do {
      NumStr += LastChar;
      LastChar = getchar();
    } while (isdigit(LastChar) || LastChar == '.');

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

if (LastChar == '#') {
    // Comment until end of line.
    do
      LastChar = getchar();
    while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');

if (LastChar != EOF)
      return gettok();
  }

// Check for end of file.  Don't eat the EOF.
  if (LastChar == EOF)
    return tok_eof;

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

gettok 函数使用 C 函数 getChar() 读取标准输入的字符，并通过 while 循环忽略 token 之间的空格。然后，根据第一个字符进行分类处理。

• 如果第一个字符是字母，那么 gettok 开始识别标识符和关键字，并将标识符存入 IdentifierStr 全局变量，返回对应的 token 类型。
• 如果第一个字符是数字或 .，那么 gettok 开始识别数值，并将数值存入 NumVal 全局变量，返回 token 类型 tok_number
• 如果第一个字符是 #，那么 gettok 识别注释，该符号之后整行内容均为注释内容，进行忽略处理。
• 如果第一个字符是 EOF，那么识别文件结束符，返回 token 类型 token_eof。
• 其它情况，则返回该字符的 ASCII 值。

如下所示，为 gettoken 函数的工作原理示意图。

至此，我们实现了 Kaleidoscope 的词法分析器。下一章，我们将实现语法分析器（Parser），从而构建抽象语法树（Abstract Syntax Tree）。当实现了词法分析器和语义分析器后，我们会实现一个驱动器（Driver）来使两者协同进行工作，并进行测试。