最小編譯器the-super-tiny-compiler

大 廠 技 術     堅 持 周 更     精 選 好 文

閲讀完本文，可以收穫如下內容：

1. 較為系統的瞭解編譯器基本工作流程和原理

2. 瞭解一種設計模式——訪問者模式

前言

在日常前端開發中，經常使用ES6+語法，但礙於用户使用的瀏覽器各不相同，新語法在舊版本瀏覽器中不支持，此時我們通常會使用babel將其轉換成支持度更為廣泛的ES5語法，這種“將不識別的語言轉換為可識別的語言”過程就叫「編譯」，所使用的工具就是編譯器。除了babel，常見的編譯器還有gcc等。

如果直接就看babel的源碼瞭解編譯器怎麼工作的，怕是很多人都會望而卻步，好在babel的維護者之一 James Kyle 有一個最小編譯器的開源項目 the-super-tiny-compiler ^[1] ，截止目前超過21.5k stars。項目去掉註釋大約200行代碼，代碼雖少，但足以展現編譯器的很多要點，通過學習這個項目，可以對編譯原理有一個較系統的理解。

這個編譯器的功能是把Lisp語言風格的 函數調用 轉換成C語言風格（不包含所有語法），比如假設我們有 add 和 subtract 兩個函數，兩種語言的風格如下：

Lisp風格	C風格
2 + 2	(add 2 2)	add(2, 2)
4 - 2	(subtract 4 2)	subtract(4, 2)
2 + (4 - 2)	(add 2 (subtract 4 2))	add(2, subtract(4, 2))

工作過程

大多數編譯器的過程可以分為三個階段：解析（parsing）、轉換（transformation）和代碼生成（code generation）:

• 解析：將原始代碼轉換為一種高度抽象的表示，通常為抽象語法樹（AST）;

• 轉換：處理高度抽象的表示，轉換成編譯器最終希望呈現的表示；

• 代碼生成：將處理後的高度抽象表示，轉換為新的代碼。

解析

通常解析需要經歷兩個步驟：詞法分析（Lexical Analysis）和語法分析（Syntatic Analysis）：

• 詞法分析：將原始代碼分割一個個令牌（Token），這些令牌通常由代碼語言組成，包含數字、標籤、標點符號、運算符等任何表示。分割的工具一般稱為詞法分析器（Tokenizer）

• 語法分析：將詞法分析的令牌，轉換成高度抽象的表示（如抽象語法樹，AST），這個表示描述了代碼語句中每一個片段以及他們之間的關係。轉換的工具一般稱為語法分析器（Parser）

接下來我們以 (add 2 (subtract 4 2)) 為例：

詞法分析器

詞法分析器輸出的結果大致如下：

[

    { 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: ')'        },

]

想到得到這樣的結果，就需要拆分輸入，並進行匹配。

 /**

 * 詞法分析器

 * @param input 代碼字符串

 * @returns token列表

 */

function tokenizer(input) {

   // 輸入字符串處理的索引

   let current = 0;

   // token列表

   let tokens = [];



   // 遍歷字符串，解析token

   while (current < input.length) {

     let char = input[current];



     // 匹配左括號

     if (char === '(') {

       // type 為 'paren'，value 為左圓括號的對象

       tokens.push({

         type: 'paren',

         value: '(',

       });



       // current 自增

       current++;



       // 結束本次循環，進入下一次循環

       continue;

     }



     // 匹配右括號

     if (char === ')') {

       // type 為 'paren'，value 為右圓括號的對象

       tokens.push({

         type: 'paren',

         value: ')',

       });

       current++;

       continue;

     }



     let WHITESPACE = /\s/;

     // 正則匹配空白字符，跳過空白字符

     if (WHITESPACE.test(char)) {

       current++;

       continue;

     }



     // 匹配如下數字

     //   (add 123 456)

     //        ^^^ ^^^

     let NUMBERS = /[0-9]/;

     // 正則匹配數字

     if (NUMBERS.test(char)) {

       let value = '';

       // 匹配連續數字，作為value

       while (NUMBERS.test(char)) {

         value += char;

         char = input[++current];

       }

       // type 為 'number'，value 為數字字符串

       tokens.push({

         type: 'number',

         value,

       });


       continue;

     }



     // 匹配如下字符串，以""包裹

     //   (concat "foo" "bar")

     //            ^^^   ^^^

     if (char === '"') {

       let value = '';



       // 跳過左雙引號

       char = input[++current];



       // 獲取雙引號之間的所有字符串

       while (char !== '"') {

         value += char;

         char = input[++current];

       }



       // 跳過右雙引號

       char = input[++current];



       // type 為 'string'，value 為字符串參數

       tokens.push({

         type: 'string',

         value,

       });

       continue;
     }



     // 匹配函數名

     //   (add 2 4)

     //    ^^^

     let LETTERS = /[a-z]/i;

     // 只包含小寫字母

     if (LETTERS.test(char)) {

       let value = '';



       // 獲取連續字符

       while (LETTERS.test(char)) {

         value += char;

         char = input[++current];

       }


       // type 為 'name'，value 為函數名

       tokens.push({

         type: 'name',

         value,

       });

       continue;
     }



     // 無法識別的字符，拋出錯誤提示

     throw new TypeError(`I dont know what this character is: ${char}`);

   }



   // 返回詞法分析器token列表

   return tokens;

 }

語法分析器

詞法分析完成後，還需要經過語法分析器，將token列表轉成如下的抽象語法樹（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',

            },

          ],

        },

      ],

    },

  ],

}

語法分析器的實現邏輯如下：

 /**

 * 語法分析器

 * @param {*} tokens token列表

 * @returns 抽象語法樹 AST

 */

function parser(tokens) {

  // token列表索引

  let current = 0;

  // 採用遞歸的方式遍歷token列表

  function walk() {

    // 獲取當前 token

    let token = tokens[current];



    // 數字類token

    if (token.type === 'number') {

      current++;



      // 生成 NumberLiteral 節點

      return {

        type: 'NumberLiteral',

        value: token.value,

      };

    }



    // 字符串類token

    if (token.type === 'string') {

      current++;



      // 生成 StringLiteral 節點

      return {

        type: 'StringLiteral',

        value: token.value,

      };

    }



    // 函數名

    if (token.type === 'paren' && token.value === '(') {

      // 跳過左括號，獲取下一個 token 作為函數名

      token = tokens[++current];



      let node = {

        type: 'CallExpression',

        name: token.value,

        params: [],

      };



      token = tokens[++current];



      // 以前面的詞法分析結果為例，有兩個右圓括號，表示有嵌套的函數

      //

      //   [

      //     { 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 (token.type !== 'paren' || (token.type === 'paren' && token.value !== ')')) {

        // 遞歸遍歷參數

        node.params.push(walk());

        token = tokens[current];

      }



      // 跳過右括號

      current++;



      return node;

    }

    // 無法識別的字符，拋出錯誤提示

    throw new TypeError(token.type);

  }



  // AST的根節點

  let ast = {

    type: 'Program',

    body: [],

  };



  // 填充ast.body

  while (current < tokens.length) {

    ast.body.push(walk());

  }



  // 返回AST

  return ast;

}

轉換

通過上面的例子可以看到，AST中有許多相似type類型的節點，這些節點包含若干其他屬性，用於描述AST的其他信息。當轉換AST的時候，我們可以直接添加、移動、替換原始AST上的這些節點（同種語言下的操作），也可以根據原始AST生成一個全新的AST（不同種語言）。

本編譯器的目標是兩種語言風格之間的轉換，故需要生成一個全新的AST。

遍歷器

針對AST這類“樹狀”的結構，可以採用深度優先的方式遍歷。以上面的AST為例，遍歷過程如下：

1. Program 類型 - 從 AST 的根節點開始

2. CallExpression (add) - 進入 Program 節點 body 屬性的第一個子元素

3. NumberLiteral (2) - 進入 CallExpression (add) 節點 params 屬性的第一個子元素

4. CallExpression (subtract) - 進入 CallExpression (add) 節點 params 屬性的第二個子元素

5. NumberLiteral (4) - 進入 CallExpression (subtract) 節點 params 屬性的第一個子元素

6. NumberLiteral (2) - 進入 CallExpression (subtract) 節點 params 屬性的第二個子元素

對於本編譯器而言，上述的節點類型已經足夠，即「訪問者」所需要提供的能力已經足夠。

訪問者對象

通過 訪問者模式 ，可以很好地分離行為和數據，實現解耦。在本編譯器中，可以創建一個類似下面的“訪問者”對象，它能夠提供訪問各種數據類型的方法。

var visitor = {

    NumberLiteral() {},

    CallExpression() {},

}

當遍歷AST的時，一旦匹配“進入”（enter）到特定類型的節點，就調用訪問者提供的方法。同時為了保證訪問者能夠拿到當前節點信息，我們需要將當前節點和父節點傳入。

var visitor = {

    NumberLiteral(node, parent) {},

    CallExpression(node, parent) {},

}

但是也存在需要退出的情況，還是以上面的AST為例：

- Program

  - CallExpression

    - NumberLiteral

    - CallExpression

      - NumberLiteral

      - NumberLiteral

當深度遍歷的時候，可能會進入葉子節點，此時我們就需要“退出”（exit）這個分支。當我們沿着樹深度遍歷時，每個節點會存在兩種操作，一種是“進入”（enter），一種是“退出”（exit）。

-> Program (enter)

  -> CallExpression (enter)

    -> Number Literal (enter)

    <- Number Literal (exit)

    -> Call Expression (enter)

       -> Number Literal (enter)

       <- Number Literal (exit)

       -> Number Literal (enter)

       <- Number Literal (exit)

    <- CallExpression (exit)

  <- CallExpression (exit)

<- Program (exit)

為了滿足這樣的操作，就需要繼續改造訪問者對象，最終大致如下：

const visitor = {

  NumberLiteral: {

    enter(node, parent) {},

    exit(node, parent) {},

  },

  CallExpression: {

    enter(node, parent) {},

    exit(node, parent) {},

  },

};

轉換器

結合上述遍歷器和訪問者對象的描述，轉換函數大致如下：

 /**

 * 遍歷器

 * @param {*} ast 語法抽象樹

 * @param {*} visitor 訪問者對象

 */

function traverser(ast, visitor) {

  // 遍歷數組中的節點

  function traverseArray(array, parent) {

    array.forEach(child => {

      traverseNode(child, parent);

    });

  }



  // 遍歷節點，參數為當前節點及其父節點

  function traverseNode(node, parent) {

    // 獲取訪問者對象上對應的方法

    let methods = visitor[node.type];

    // 執行訪問者的 enter 方法

    if (methods && methods.enter) {

      methods.enter(node, parent);

    }



    switch (node.type) {

      // 根節點

      case 'Program':

        traverseArray(node.body, node);

        break;

      // 函數調用

      case 'CallExpression':

        traverseArray(node.params, node);

        break;

      // 數值和字符串，不用處理

      case 'NumberLiteral':

      case 'StringLiteral':

        break;



      // 無法識別的字符，拋出錯誤提示

      default:

        throw new TypeError(node.type);

    }

    if (methods && methods.exit) {

      methods.exit(node, parent);

    }

  }

  // 開始遍歷

  traverseNode(ast, null);

}



 /**

 * 轉換器

 * @param {*} ast 抽象語法樹

 * @returns 新AST

 */

function transformer(ast) {

  // 創建一個新 AST

  let newAst = {

    type: 'Program',

    body: [],

  };



  // 通過 _context 引用，更新新舊節點

  ast._context = newAst.body;



  // 使用遍歷器遍歷原始 AST

  traverser(ast, {

    // 數字節點，直接原樣插入新AST

    NumberLiteral: {

      enter(node, parent) {

        parent._context.push({

          type: 'NumberLiteral',

          value: node.value,

        });

      },

    },

    // 字符串節點，直接原樣插入新AST

    StringLiteral: {

      enter(node, parent) {

        parent._context.push({

          type: 'StringLiteral',

          value: node.value,

        });

      },

    },

    // 函數調用

    CallExpression: {

      enter(node, parent) {

        // 創建不同的AST節點

        let expression = {

          type: 'CallExpression',

          callee: {

            type: 'Identifier',

            name: node.name,

          },

          arguments: [],

        };



        // 同樣通過 _context 引用參數，供子節點使用

        node._context = expression.arguments;



        // 頂層函數調用本質上是一個語句，寫成特殊節點 `ExpressionStatement`

        if (parent.type !== 'CallExpression') {

          expression = {

            type: 'ExpressionStatement',

            expression,

          };

        }

        parent._context.push(expression);

      },

    },

  });



  return newAst;

}

(add 2 (subtract 4 2)) 的 AST 經過該轉換器之後，就轉變成下面的新 AST ：

{

  type: 'Program',

  body: [

    {

      type: 'ExpressionStatement',

      expression: {

        type: 'CallExpression',

        callee: {

          type: 'Identifier',

          name: 'add',

        },

        arguments: [

          {

            type: 'NumberLiteral',

            value: '2',

          },

          {

            type: 'CallExpression',

            callee: {

              type: 'Identifier',

              name: 'subtract',

            },

            arguments: [

              {

                type: 'NumberLiteral',

                value: '4',

              },

              {

                type: 'NumberLiteral',

                value: '2',

              },

            ],

          },

        ],

      },

    },

  ],

};

代碼生成

有時候這個階段的工作會和轉換階段有重疊，但一般而言主要還是根據AST輸出對應代碼。

代碼生成有幾種不同的方式，有些編譯器會複用之前的token，有些會創建對立的代碼表示，以便於線性輸出代碼。

代碼生成器需要知道如何“打印”AST中所有類型的節點，然後遞歸調用自身，直到遍歷完AST，所有代碼轉換成字符串。

 /**

 * 代碼生成器

 * @param {*} node AST 中的 body 節點

 * @returns 代碼字符串

 */

function codeGenerator(node) {

  // 判斷節點類型

  switch (node.type) {

    // 根節點，遞歸 body 節點列表

    case 'Program':

      return node.body.map(codeGenerator).join('\n');



    // 表達式，處理表達式內容，以分好結尾

    case 'ExpressionStatement':

      return `${codeGenerator(node.expression)};`;



    // 函數調用，添加左右括號，參數用逗號隔開

    case 'CallExpression':

      return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;



    // 標識符，數值，直接輸出

    case 'Identifier':

      return node.name;

    case 'NumberLiteral':

      return node.value;



    // 字符串，用雙引號包起來

    case 'StringLiteral':

      return `"${node.value}"`;



    // 無法識別的字符，拋出錯誤提示

    default:

      throw new TypeError(node.type);

  }

}

編譯器

上述流程就是編譯器工作的三個基本步驟就是如下：

1. 輸入字符 -> 詞法分析 -> 令牌（Token） -> 語法分析 -> 抽象語法樹（AST）

2. 抽象語法樹（AST）-> 轉換器 -> 新AST

3. 新AST -> 代碼生成器 -> 輸出字符

 /**

 * 編譯器

 * @param {*} input 代碼字符串

 * @returns 代碼字符串

 */

function compiler(input) {

  let tokens = tokenizer(input);

  let ast = parser(tokens);

  let newAst = transformer(ast);

  let output = codeGenerator(newAst);



  return output;

}

雖然不同編譯器的目的不同，步驟會有些許區別，但萬變不離其宗，以上基本能讓讀者對編譯器有個較為系統的認識。

拓展

polyfill

babel是一個編譯器，默認只用於轉換js語法，而不會轉換新語法提供的API，比如Promise、Generator等，此時我們就需要使用polyfill來兼容這些新語法，其工作原理大致如下：

(function (window) {

  if (window.incompatibleFeature) {

    return window.incompatibleFeature;

  } else {

    window.incompatibleFeature = function () {

      // 兼容代碼

    };

  }

})(window);

訪問者模式

定義

表示一個作用於某對象結構中的各元素的操作。它使你可以在不改變各元素類的前提下定義作用於這些元素的新操作。本質是將行為與數據解耦，根據訪問者不同，所展示的行為也不同。

• Visitor：接口或者抽象類，定義了對每個 Element 訪問的行為，它的參數就是被訪問的元素，它的方法個數理論上與元素的個數是一樣的，因此，訪問者模式要求元素的類型要穩定，如果經常添加、移除元素類，必然會導致頻繁地修改 Visitor 接口，如果出現這種情況，則説明不適合使用訪問者模式。

• ConcreteVisitor：具體的訪問者，它需要給出對每一個元素類訪問時所產生的具體行為。

• Element：元素接口或者抽象類，它定義了一個接受訪問者（accept）的方法，其意義是指每一個元素都要可以被訪問者訪問。

• ElementA、ElementB：具體的元素類，它提供接受訪問的具體實現，而這個具體的實現，通常情況下是使用訪問者提供的訪問該元素類的方法。

• ObjectStructure：定義當中所提到的對象結構，對象結構是一個抽象表述，它內部管理了元素集合，並且可以迭代這些元素提供訪問者訪問。

例子

編譯器中使用的是“訪問者對象”，下面以“訪問者類”為例：

• 定義一組設備

class Keyboard {

    accept(computerPartVisitor) {

       computerPartVisitor.visit(this);

    }

}

class Monitor {

    accept(computerPartVisitor) {

       computerPartVisitor.visit(this);

    }

}

class Mouse {

    accept(computerPartVisitor) {

       computerPartVisitor.visit(this);

    }

}

• 定義電腦為一種設備，同時集成了其他設備

class Computer {

    constructor(){

       this.parts = [new Mouse(), new Keyboard(), new Monitor()];      

    } 

    accept(computerPartVisitor) {

       for (let i = 0; i < this.parts.length; i++) {

        this.parts[i].accept(computerPartVisitor);

       }

       computerPartVisitor.visit(this);

    }

}

• 定義訪問者接口

class ComputerPartDisplayVisitor{

    visit(device) {

        console.log(`Displaying ${device.constructor.name}.`);

    }

}

• 在使用的時候都只需要用設備接受新的訪問者即可實現對應訪問者的功能

const computer = new Computer();

computer.accept(new ComputerPartDisplayVisitor());

/**

 * output:

 * Displaying Mouse.

 * Displaying Keyboard.

 * Displaying Monitor.

 * Displaying Computer.

 */

優點

1. 符合單一職責原則：凡是適用訪問者模式的場景中，元素類中需要封裝在訪問者中的操作必定是與元素類本身關係不大且是易變的操作，使用訪問者模式一方面符合單一職責原則，另一方面，因為被封裝的操作通常來説都是易變的，所以當發生變化時，就可以在不改變元素類本身的前提下，實現對變化部分的擴展。

2. 擴展性良好：元素類可以通過接受不同的訪問者來實現對不同操作的擴展。

3. 使得數據結構和作用於結構上的操作解耦，使得操作集合可以獨立變化。

適用情況

1. 對象結構比較穩定，但經常需要在此對象結構上定義新的操作。

2. 需要對一個對象結構中的對象進行很多不同的並且不相關的操作，而需要避免這些操作“污染”這些對象的類，也不希望在增加新操作時修改這些類。

參考文檔

https://github.com/jamiebuilds/the-super-tiny-compiler

有史以來最小的編譯器源碼解析 ^[2]

https://developer.51cto.com/art/202106/668215.htm

訪問者模式一篇就夠了 ^[3]

參考資料