最小編譯器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. 需要對一個物件結構中的物件進行很多不同的並且不相關的操作，而需要避免這些操作“汙染”這些物件的類，也不希望在增加新操作時修改這些類。

參考文件

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

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

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

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

參考資料