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 章中包含了一個更有趣的範例，我們在其中編寫了一個小的萬花筒應用程式，該應用程式顯示了各種放大倍率的曼德博集合。
讓我們深入研究這個語言的實作！
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;
}
有了這個，我們就有了基本萬花筒語言的完整詞法分析器（詞法分析器的完整程式碼清單可在教學的下一章中找到）。 接下來，我們將建立一個簡單的剖析器，它使用這個剖析器來建立抽象語法樹。 當我們有了它之後，我們將包含一個驅動程式，以便您可以一起使用詞法分析器和剖析器。