如何寫一個類似 LESS 的編譯工具？

/**
* 大多數編譯器可以分成三個階段：解析（Parsing），轉換（Transformation）以及代碼
* 生成（Code Generation）
*
* 1. *解析*是將最初原始的代碼轉換為一種更加抽象的表示（譯者註：即AST）。*
*
* 2. *轉換*將對這個抽象的表示做一些處理，讓它能做到編譯器期望
* 它做到的事情。
*
* 3. *代碼生成*接收處理之後的代碼表示，然後把它轉換成新的代碼。
*/

/**
* 解析（Parsing）
* -------
*
* 解析一般來說會分成兩個階段：詞法分析（Lexical Analysis）和語法分析（Syntactic Analysis）。
*
* 1. *詞法分析*接收原始代碼，然後把它分割成一些被稱為 Token 的東西，這個過程是在詞法分析
* 器（Tokenizer或者Lexer）中完成的。
*
* Token 是一個數組，由一些代碼語句的碎片組成。它們可以是數字、標籤、標點符號、運算符，
* 或者其它任何東西。
*
* 2. *語法分析* 接收之前生成的 Token，把它們轉換成一種抽象的表示，這種抽象的表示描述了代
* 碼語句中的每一個片段以及它們之間的關係。這被稱為中間表示（intermediate representation）
* 或抽象語法樹（Abstract Syntax Tree， 縮寫為AST）
*
* 抽象語法樹是一個嵌套程度很深的對象，用一種更容易處理的方式代表了代碼本身，也能給我們
* 更多信息。
*
* 比如說對於下面這一行代碼語句：
*
* (add 2 (subtract 4 2))
*
* 它產生的 Token 看起來或許是這樣的：
*
* [
* { type: "paren", value: "(" },
* { type: "name", value: "add" },
* { type: "number", value: "2" },
* { type: "paren", value: "(" },
* { type: "name", value: "subtract" },
* { type: "number", value: "4" },
* { type: "number", value: "2" },
* { type: "paren", value: ")" },
* { type: "paren", value: ")" }
* ]
*
* 它的抽象語法樹（AST）看起來或許是這樣的：
*
* {
* type: "Program",
* body: [{
* type: "CallExpression",
* name: "add",
* params: [{
* type: "NumberLiteral",
* value: "2"
* }, {
* type: "CallExpression",
* name: "subtract",
* params: [{
* type: "NumberLiteral",
* value: "4"
* }, {
* type: "NumberLiteral",
* value: "2"
* }]
* }]
* }]
* }
*/

/**
* 轉換（Transformation）
* --------------
*
* 編譯器的下一步就是轉換。它只是把 AST 拿過來然後對它做一些修改。它可以在同種語言下操
* 作 AST，也可以把 AST 翻譯成全新的語言。
*
* 下面我們來看看該如何轉換 AST。
*
* 你或許注意到了我們的 AST 中有很多相似的元素，這些元素都有 type 屬性，它們被稱為 AST
* 結點。這些結點含有若干屬性，可以用於描述 AST 的部分信息。
*
* 比如下面是一個「NumberLiteral」結點：
*
* {
* type: "NumberLiteral",
* value: "2"
* }
*
* 又比如下面是一個「CallExpression」結點：
*
* {
* type: "CallExpression",
* name: "subtract",
* params: [...nested nodes go here...]
* }
*
* 當轉換 AST 的時候我們可以添加、移動、替代這些結點，也可以根據現有的 AST 生成一個全新
* 的 AST
*
* 既然我們編譯器的目標是把輸入的代碼轉換為一種新的語言，所以我們將會著重於產生一個針對
* 新語言的全新的 AST。
*
*
* 遍歷（Traversal）
* ---------
*
* 為了能處理所有的結點，我們需要遍歷它們，使用的是深度優先遍歷。
*
* {
* type: "Program",
* body: [{
* type: "CallExpression",
* name: "add",
* params: [{
* type: "NumberLiteral",
* value: "2"
* }, {
* type: "CallExpression",
* name: "subtract",
* params: [{
* type: "NumberLiteral",
* value: "4"
* }, {
* type: "NumberLiteral",
* value: "2"
* }]
* }]
* }]
* }
*
* So for the above AST we would go:
* 對於上面的 AST 的遍歷流程是這樣的：
*
* 1. Program - 從 AST 的頂部結點開始
* 2. CallExpression (add) - Program 的第一個子元素
* 3. NumberLiteral (2) - CallExpression (add) 的第一個子元素
* 4. CallExpression (subtract) - CallExpression (add) 的第二個子元素
* 5. NumberLiteral (4) - CallExpression (subtract) 的第一個子元素
* 6. NumberLiteral (4) - CallExpression (subtract) 的第二個子元素
*
* 如果我們直接在 AST 內部操作，而不是產生一個新的 AST，那麼就要在這裡介紹所有種類的抽象，
* 但是目前訪問（visiting）所有結點的方法已經足夠了。
*
* 使用「訪問（visiting）」這個詞的是因為這是一種模式，代表在對象結構內對元素進行操作。
*
* 訪問者（Visitors）
* --------
*
* 我們最基礎的想法是創建一個「訪問者（visitor）」對象，這個對象中包含一些方法，可以接收不
* 同的結點。
*
* var visitor = {
* NumberLiteral() {},
* CallExpression() {}
* };
*
* 當我們遍歷 AST 的時候，如果遇到了匹配 type 的結點，我們可以調用 visitor 中的方法。
*
* 一般情況下為了讓這些方法可用性更好，我們會把父結點也作為參數傳入。
*/

/**
* 代碼生成（Code Generation）
* ---------------
*
* 編譯器的最後一個階段是代碼生成，這個階段做的事情有時候會和轉換（transformation）重疊，
* 但是代碼生成最主要的部分還是根據 AST 來輸出代碼。
*
* 代碼生成有幾種不同的工作方式，有些編譯器將會重用之前生成的 token，有些會創建獨立的代碼
* 表示，以便於線性地輸出代碼。但是接下來我們還是著重於使用之前生成好的 AST。
*
* 我們的代碼生成器需要知道如何「列印」AST 中所有類型的結點，然後它會遞歸地調用自身，直到所
* 有代碼都被列印到一個很長的字元串中。
*
*/

/**
* 好了！這就是編譯器中所有的部分了。
*
* 當然不是說所有的編譯器都像我說的這樣。不同的編譯器有不同的目的，所以也可能需要不同的步驟。
*
* 但你現在應該對編譯器到底是個什麼東西有個大概的認識了。
*
* 既然我全都解釋一遍了，你應該能寫一個屬於自己的編譯器了吧？
*
* 哈哈開個玩笑，接下來才是重點
*
* 所以我們開始吧...
*/

/**
* =======================================================================
* (/^▽^)/
* 詞法分析器（Tokenizer）!
* =======================================================================
*/

/**
* 我們從第一個階段開始，即詞法分析，使用的是詞法分析器（Tokenizer）。
*
* 我們只是接收代碼組成的字元串，然後把它們分割成 token 組成的數組。
*
* (add 2 (subtract 4 2)) =&> [{ type: "paren", value: "(" }, ...]
*/

// 我們從接收一個字元串開始，首先設置兩個變數。
function tokenizer(input) {

// `current`變數類似指針，用於記錄我們在代碼字元串中的位置。
var current = 0;

// `tokens`數組是我們放置 token 的地方
var tokens = [];

// 首先我們創建一個 `while` 循環， `current` 變數會在循環中自增。
//
// 我們這麼做的原因是，由於 token 數組的長度是任意的，所以可能要在單個循環中多次
// 增加 `current`
while (current &< input.length) { // 我們在這裡儲存了 `input` 中的當前字元 var char = input[current]; // 要做的第一件事情就是檢查是不是右圓括弧。這在之後將會用在 `CallExpressions` 中， // 但是現在我們關心的只是字元本身。 // // 檢查一下是不是一個左圓括弧。 if (char === "(") { // 如果是，那麼我們 push 一個 type 為 `paren`，value 為左圓括弧的對象。 tokens.push({ type: "paren", value: "(" }); // 自增 `current` current++; // 結束本次循環，進入下一次循環 continue; } // 然後我們檢查是不是一個右圓括弧。這裡做的時候和之前一樣：檢查右圓括弧、加入新的 token、 // 自增 `current`，然後進入下一次循環。 if (char === ")") { tokens.push({ type: "paren", value: ")" }); current++; continue; } // 繼續，我們現在檢查是不是空格。有趣的是，我們想要空格的本意是分隔字元，但這現在 // 對於我們儲存 token 來說不那麼重要。我們暫且擱置它。 // // 所以我們只是簡單地檢查是不是空格，如果是，那麼我們直接進入下一個循環。 var WHITESPACE = /s/; if (WHITESPACE.test(char)) { current++; continue; } // 下一個 token 的類型是數字。它和之前的 token 不同，因為數字可以由多個數字字元組成， // 但是我們只能把它們識別為一個 token。 // // (add 123 456) // ^^^ ^^^ // Only two separate tokens // 這裡只有兩個 token // // 當我們遇到一個數字字元時，將會從這裡開始。 var NUMBERS = /[0-9]/; if (NUMBERS.test(char)) { // 創建一個 `value` 字元串，用於 push 字元。 var value = ""; // 然後我們循環遍歷接下來的字元，直到我們遇到的字元不再是數字字元為止，把遇到的每 // 一個數字字元 push 進 `value` 中，然後自增 `current`。 while (NUMBERS.test(char)) { value += char; char = input[++current]; } // 然後我們把類型為 `number` 的 token 放入 `tokens` 數組中。 tokens.push({ type: "number", value: value }); // 進入下一次循環。 continue; } // 最後一種類型的 token 是 `name`。它由一系列的字母組成，這在我們的 lisp 語法中 // 代表了函數。 // // (add 2 4) // ^^^ // Name token // var LETTERS = /[a-z]/i; if (LETTERS.test(char)) { var value = ""; // 同樣，我們用一個循環遍歷所有的字母，把它們存入 value 中。 while (LETTERS.test(char)) { value += char; char = input[++current]; } // 然後添加一個類型為 `name` 的 token，然後進入下一次循環。 tokens.push({ type: "name", value: value }); continue; } // 最後如果我們沒有匹配上任何類型的 token，那麼我們拋出一個錯誤。 throw new TypeError("I dont know what this character is: " + char); } // 詞法分析器的最後我們返回 tokens 數組。 return tokens; } /** * ======================================================================= * ヽ/?o ? o? * 語法分析器（Parser）!!! * ======================================================================= */ /** * 語法分析器接受 token 數組，然後把它轉化為 AST * * [{ type: "paren", value: "(" }, ...] =&> { type: "Program", body: [...] }
*/

// 現在我們定義 parser 函數，接受 `tokens` 數組
function parser(tokens) {

// 我們再次聲明一個 `current` 變數作為指針。
var current = 0;

// 但是這次我們使用遞歸而不是 `while` 循環，所以我們定義一個 `walk` 函數。
function walk() {

// walk函數里，我們從當前token開始
var token = tokens[current];

// 對於不同類型的結點，對應的處理方法也不同，我們從 `number` 類型的 token 開始。
// 檢查是不是 `number` 類型
if (token.type === "number") {

// 如果是，`current` 自增。
current++;

// 然後我們會返回一個新的 AST 結點 `NumberLiteral`，並且把它的值設為 token 的值。
return {
type: "NumberLiteral",
value: token.value
};
}

// 接下來我們檢查是不是 CallExpressions 類型，我們從左圓括弧開始。
if (
token.type === "paren"
token.value === "("
) {

// 我們會自增 `current` 來跳過這個括弧，因為括弧在 AST 中是不重要的。
token = tokens[++current];

// 我們創建一個類型為 `CallExpression` 的根節點，然後把它的 name 屬性設置為當前
// token 的值，因為緊跟在左圓括弧後面的 token 一定是調用的函數的名字。
var node = {
type: "CallExpression",
name: token.value,
params: []
};

// 我們再次自增 `current` 變數，跳過當前的 token
token = tokens[++current];

// 現在我們循環遍歷接下來的每一個 token，直到我們遇到右圓括弧，這些 token 將會
// 是 `CallExpression` 的 `params`（參數）
//
// 這也是遞歸開始的地方，我們採用遞歸的方式來解決問題，而不是去嘗試解析一個可能有無限
// 層嵌套的結點。
//
// 為了更好地解釋，我們來看看我們的 Lisp 代碼。你會注意到 `add` 函數的參數有兩個，
// 一個是數字，另一個是一個嵌套的 `CallExpression`，這個 `CallExpression` 中
// 包含了它自己的參數（兩個數字）
//
// (add 2 (subtract 4 2))
//
// 你也會注意到我們的 token 數組中有多個右圓括弧。
//
// [
// { type: "paren", value: "(" },
// { type: "name", value: "add" },
// { type: "number", value: "2" },
// { type: "paren", value: "(" },
// { type: "name", value: "subtract" },
// { type: "number", value: "4" },
// { type: "number", value: "2" },
// { type: "paren", value: ")" }, &<&<&< 右圓括弧 // { type: "paren", value: ")" } &<&<&< 右圓括弧 // ] // // 遇到嵌套的 `CallExpressions` 時，我們將會依賴嵌套的 `walk` 函數來 // 增加 `current` 變數 // // 所以我們創建一個 `while` 循環，直到遇到類型為 `"paren"`，值為右圓括弧的 token。 while ( (token.type !== "paren") || (token.type === "paren" token.value !== ")") ) { // 我們調用 `walk` 函數，它將會返回一個結點，然後我們把這個節點 // 放入 `node.params` 中。 node.params.push(walk()); token = tokens[current]; } // 我們最後一次增加 `current`，跳過右圓括弧。 current++; // 返回結點。 return node; } // 同樣，如果我們遇到了一個類型未知的結點，就拋出一個錯誤。 throw new TypeError(token.type); } // 現在，我們創建 AST，根結點是一個類型為 `Program` 的結點。 var ast = { type: "Program", body: [] }; // 現在我們開始 `walk` 函數，把結點放入 `ast.body` 中。 // // 之所以在一個循環中處理，是因為我們的程序可能在 `CallExpressions` 後面包含連續的兩個 // 參數，而不是嵌套的。 // // (add 2 2) // (subtract 4 2) // while (current &< tokens.length) { ast.body.push(walk()); } // 最後我們的語法分析器返回 AST return ast; } /** * ======================================================================= * ⌒(?&>???& tokenizer =&> tokens
* 2. tokens =&> parser =&> ast
* 3. ast =&> transformer =&> newAst
* 4. newAst =&> generator =&> output
*/

function compiler(input) {
var tokens = tokenizer(input);
var ast = parser(tokens);
var newAst = transformer(ast);
var output = codeGenerator(newAst);

// 然後返回輸出!
return output;
}

/**
* =======================================================================
* (??????)
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!你做到了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* =======================================================================
*/

//匹配左括弧
function leftParen () {
return ch("(");
}

//匹配右括弧
function rightParen () {
return ch(")");
}

//匹配0到9之間的數字
function int () {
return action(range("0", "9"), function(ast){
return {
type: "NumberLiteral",
value: ast
}
});
}

//匹配由大小寫字母任意組合的標示符
function identifer () {
var result = repeat1(
choice(
range("a", "z"),
range("A", "Z")
)
)
return action(result, function(ast){
return ast.join("");
})
}