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

1.1. 万花筒语言

本教程以一种名为“万花筒”（源自“美丽、形式和视角的含义”）的玩具语言为例进行说明。万花筒是一种过程式语言，允许您定义函数、使用条件语句、数学运算等。在教程的过程中，我们将扩展万花筒以支持 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 章中包含了一个更有趣的示例，我们在其中编写了一个小型万花筒应用程序，该应用程序显示了不同放大倍数下的曼德勃罗集。

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

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