1. Kaleidoscope：Kaleidoscope 簡介和詞法分析器

1.1. Kaleidoscope 語言

本教學使用一種稱為「Kaleidoscope」（源自「美麗、形式和視野」之意）的玩具語言來說明。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」關鍵字定義函式之前使用它（這對於相互遞迴函式也很有用）。例如

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

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

第 6 章中包含一個更有趣的範例，其中我們編寫了一個小的 Kaleidoscope 應用程式，用於 以各種放大級別顯示曼德博集合。

讓我們深入研究這種語言的實現！

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”。Kaleidoscope 使用以下簡單迴圈來完成此操作：

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 語言的完整詞法分析器（詞法分析器的完整程式碼可在本教學的下一章中找到）。接下來，我們將構建一個簡單的語法分析器，使用它來構建抽象語法樹。完成後，我們將包含一個驅動程式，以便您可以同時使用詞法分析器和語法分析器。

下一步：實現語法分析器和 AST