1. 万花筒: 万花筒介绍和词法分析器

1.1. 万花筒语言

本教程通过一个名为“万花筒”（源自“meaning beautiful, form, and view”）的玩具语言进行说明。万花筒是一种过程式语言，允许您定义函数、使用条件语句、数学运算等。在本教程的过程中，我们将扩展万花筒以支持 if/then/else 结构、for 循环、用户定义的运算符、带有简单命令行界面的 JIT 编译、调试信息等等。

我们希望保持简单，因此万花筒中唯一的数据类型是 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)

我们也允许万花筒调用标准库函数 - LLVM JIT 使这变得非常容易。这意味着您可以使用 ‘extern’ 关键字在您使用函数之前定义它（这也对相互递归函数很有用）。例如

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

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

第 6 章包含一个更有趣的示例，我们在其中编写了一个小的万花筒应用程序，该应用程序显示了不同放大级别的 Mandelbrot 集。

让我们深入了解这种语言的实现！

1.2. 词法分析器

在实现一种语言时，首先需要的是处理文本文件并识别其内容的能力。传统的做法是使用“词法分析器”（也称为 ‘扫描器’）将输入分解为“标记”。词法分析器返回的每个标记都包含一个标记代码，并可能包含一些元数据（例如，数字的数值）。首先，我们定义可能性

// 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 枚举值之一，要么是 ‘+’ 这样的 ‘未知’ 字符，它作为其 ASCII 值返回。如果当前标记是标识符，则 IdentifierStr 全局变量保存标识符的名称。如果当前标记是数字字面量（如 1.0），则 NumVal 保存其值。为了简单起见，我们使用全局变量，但这对于真实的语言实现来说不是最佳选择:)。

词法分析器的实际实现是一个名为 gettok 的单一函数。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”。万花筒使用这个简单的循环来完成这个任务

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

有了这个，我们就有了基本万花筒语言的完整词法分析器（词法分析器的完整代码清单可在本教程的下一章中找到）。接下来，我们将构建一个简单的解析器，它使用这个解析器来构建抽象语法树。当我们有了这个解析器后，我们将包含一个驱动程序，以便您可以一起使用词法分析器和解析器。

下一步：实现解析器和 AST