第一章 教程简介与词法分析器

原文:Tutorial Introduction and the Lexer

教程介绍

欢迎走进“LLVM开发新语言”教程。本教程详细介绍了一门简单语言的实现过程；你将会看到，这个过程既轻松又有趣。本教程将伴你一起搭建一套框架，它可以成为你今后实现其他语言的基础。教程中的代码就是供你把玩LLVM的各种功能的试验田。

本教程的目标是循序渐进地描绘一门语言，并详述它的开发过程。在这一过程中，我们将针对语言设计以及LLVM的用法等问题展开讨论。与此同时，我们会给出代码并进行讲解，你免各种细节把你弄得晕头转向。

需要提前说明的是，这一教程讲授的是编译器技术和LLVM，不是四平八稳的现代化软件工程准则。换言之，方便起见，我们会采用一些不太正规的手法。譬如对内存泄漏孰视无睹、滥用全局变量、无视visitor等成熟设计模式等等……一切从简。如果你有意深究，并打算把这些代码用作今后项目的基础，这些毛病也不难修。

我试着编排了本教程的各个章节，碰到熟悉的或是不感兴趣的章节，你大可直接跳过。本教程的结构如下：

• 第一章：Kaleidoscope语言及其词法解析器简介

  阐明我们的目的，并明确新语言应该具备哪些基本功能。为了让这份教程尽量易于理解、易于入手，我们决定不采用任何词法分析器和语法分析器的生成器[1]，而是直接用C++实现所有功能。当然，LLVM与这些工具配合使用也完全没问题，如果愿意，你大可放手一试。

• 第二章：实现语法分析器和AST

  完成词法分析器之后，我们就开始讨论语法解析技术，进而开始构造基本的AST。这份教程共介绍了递归下降解析和运算符优先级解析两种解析技术。第一章和第二章的内容与LLVM完全无关，至此，我们的代码甚至都不需要链接LLVM库。 :-)

• 第三章：LLVM IR代码生成

  搞定AST之后，我们忍不住要炫耀一番，让你看看LLVM IR的生成过程是多么的简单。

• 第四章：添加JIT和优化支持

  很多人都有意将LLVM用作JIT，有鉴于此，我们打算在此深入一下，让你见识一下区区三行代码搞定JIT支持。尽管LLVM在其他方面也应用广泛，但说到炫技，还是这三行代码最简单、最“惊艳”。

• 第五章：语言扩展：流程控制

  我们的语言已经可以运行了，现在来看看如何为它添加流程控制能力（即if/then/else和“for”循环）。在此我们还将借机介绍一下简单的SSA构造和流程控制。

• 第六章：语言扩展：用户自定义运算符

  这一章用处不大，但却很有意思。我们再次对语言进行了扩展，赋予了用户在程序中自行定义任意一元和二元运算符的能力（还可以设置优先级！）。这一机制使得我们得以将该“语言”的很大一部分实现成库函数。

• 第七章：语言扩展：可变变量

  本章介绍的是用户自定义局部变量和赋值运算符的实现。最有意思的地方在于，在LLVM中构造SSA form简单至极：不，实际上LLVM压根儿就不要求你在前端[2]构造SSA form！

• 第八章：结论以及其他和LLVM有关的内容

  本章对整个系列教程作出了总结，不仅讨论了多种潜在的语言扩展方向，还针对一系列“专题”给出了参考资料，例如垃圾回收支持、异常、调试、“麻花栈[3]”支持等，此外，还提到了很多其他的窍门和技巧。

截至本教程末尾为止，不算注释和空行，我们总共只需编写不到700行代码。面对这样一门相对复杂的语言，只用了这么点儿代码就我们实现了一款颇为像样的编译器，其中包括手工打造的词法分析器、语法分析器、AST，还实现了带JIT编译器的代码生成。我想，相对于其他系统给出的那些“hello world”级别的教程，这篇教程的广度足以诠释LLVM的强大；如果你对语言和编译器设计感兴趣，它应该能够说服你认真考虑LLVM。

最后说一句：我们希望你能够进一步扩展这一语言，好好玩味一番。拿着代码疯狂地hack去吧，编译器并非令人恐惧的怪兽——把玩程序语言，奇乐无穷！

初级语言

本教程介绍了一门玩具语言，名叫“Kaleidoscope”（取“美仑美奂、形态万千、多姿多彩”之意）[4]。Kaleidoscope是一个过程式语言，用户可以定义函数、使用条件语句、执行数学运算等等。随着教程的深入，我们将逐步扩展Kaleidoscope，为它增加if/then/else结构、for循环、用户自定义运算符，以及带有简单命令行界面的JIT编译器等等。

简单起见，Kaleidoscope只支持一种数据类型，即64位浮点数（也就是C中的“double”）。这样一来，所有的值都是双精度浮点数，类型申明也省了，语言的语法简洁明快。以下是一个用于计算斐波那契数的简单示例：

# 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”关键字对函数进行申明[5]（碰到相互递归调用的函数[6]时也需要这么做）。例如：

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

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

第六章的例子更有意思：我们用Kaleidoscope编写了一个小应用，可以按不同尺度显示Mandelbrot集合。

让我们来细细品味一下这门语言的实现过程吧！

词法分析器

要实现一门语言，第一要务就是要能够处理文本文件，搞明白其中究竟写了些什么。传统上，我们会先利用“词法分析器”（也称为“扫描器”）将输入切成“语元（token）”，然后再做处理。词法分析器返回的每个语元都带有一个语元编号，此外可能还会附带一些元数据（比如某个数值）。首先，我们把所有可能出现的语元都定义出来：

//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//

// 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

我们的词法分析器返回的语元，要么是上述若干个语元枚举值之一，要么是诸如“+”这样的“未知”字符。对于后一种情况，词法分析器返回的是这些字符的ASCII值。如果当前语元是标识符，其名称将被存入全局变量IdentifierStr。如果当前语元是数值常量（比如1.0），其值将被存入NumVal。注意，简单起见，我们动用了全局变量，在真正的语言实现中这可不是最佳选择 :-) 。

Kaleidoscope的词法分析器由一个名为gettok的函数实现。调用该函数，就可以得到标准输入中的下一个语元。它的开头是这样的：

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

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

gettok通过C标准库的getchar()函数从标准输入中逐个读入字符。它一边识别读取的字符，一边将最后读入的字符存入LastChar，留待后续处理。这个函数干的第一件事就是利用上面的循环剔除语元之间的空白符。

接下来，gettok开始识别标识符和“def”、“extern”等关键字。这个任务由下面的循环负责，很简单：

  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;
  }

注意，标识符一被识别出来就被存入全局变量IdentifierStr。此外，语言中的关键字也由这个循环负责识别，在此处一并处理。数值的识别过程与此类似：

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

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

处理输入字符的代码简单明了。只要碰到代表数值的字符串，就用C标准库中的strtod函数将之转换为数值并存入NumVal。注意，这里的错误检测并不完备：这段代码会将“1.23.45.67”错误地识别成“1.23”。改还是不改，那就随你的便了 :-) 。下面我们来处理注释：

  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;
}

至此，完整的Kaleidoscope词法分析器就完成了（完整源码参见本教程的下一章）。接下来，我们将编写一个简单的语法分析器并利用它来构建抽象语法树。届时，我们还会再加上一段引导代码，让词法分析器和语法分析器珠联璧合、天衣无缝。

脚注

[1]	例如lex/yacc或flex/bison——译者注。

[2]	这里指的是编译器或解释器的前端——译者注。

[3]	Spaghetti Stack，spaghetti的本意是意大利面——译者注。

[4]	Kaleidoscope意即“万花筒”——译者注。

[5]	原文中用的是define；但从上下文来看此处应该是函数原型声明，而非函数定义，故改译作“声明”——译者注。

[6]	指函数A调用函数B，函数B又反过来调用函数A，从而形成递归调用的情况——译者注。