基於 js 實現一個小型編譯器

本文內容基於 https://github.com/jamiebuilds/the-super-tiny-compiler 倉庫源碼進行學習

最近在研究一些構建側的東西,在翻 babel 官網的時候看到了這樣一段話:

For an awesome tutorial on compilers, check out the-super-tiny-compiler, which also explains how Babel itself works on a high level.

出於學習的心態,去翻了一下這個倉庫源碼,以下是筆者的一些學習的記錄,希望看完之後能對你理解 babel 的工作原理有一些幫助~

前言

the-super-tiny-compiler是一個代碼行數只有不到 200 行的超級小型的 compiler,但通過這個 compiler 能學習到最基礎的 compile 原理,包括 babel 也是基於這樣的原理來進行開發的。
倉庫本身的例子是將一組 lisp 風格的函數語法編譯成了 C 風格的函數語法,舉例子來說:

SAJroL

這就大概是這次 compiler 需要完成的事情,可能看上去語法不是很完整,但是也能夠演示現代編譯器的主要部分思想了。

大多數的 Compilers 都會把編譯過程分成三個主要的過程: parse、transform 以及 code generate:

  1. parse 主要是將源碼轉換成一種更抽象的代碼表達

  2. transform 則是將上面抽象的表達進行任意 compiler 想進行的操作

  3. code generate 將 transform 處理之後的代碼生成一種新的代碼

Parse

parse 主要分爲兩個步驟: 詞法分析以及語法分析。

  1. 詞法分析將源碼根據表達切分一個個的 tokens,tokens 是一組用來描述單獨語法的對象,可以是 numbers、labels、punctuation、operators 等

  2. 語法分析則是將詞法分析生成的 tokens 進行重新編排得到一個叫做抽象語法樹 (AST) 的結構,AST 是一種易於使用且能展示完整信息的嵌套樹狀結構。

例如前面提到的 add 2 (subtract 4 2)表達式被詞法分析處理之後生成的 tokens 大概是:

[
  { 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',
            }
           ]
         }]
      }]
}

Transform

transform 主要就是拿到 parse 得到的抽象語法樹,並基於此做出一些修改。tranform 這個過程既可以基於當前語言的風格去修改 ast 也可以使用一種新的語言風格。
下面基於前面的 ast 結構來展示 transform 這個過程的工作流程。
可以看到,ast 裏面的元素看起來都很相似,這些元素組成了 ast 的子結點,這些子結點的數據結構類型描述了代碼中的一個單獨的部分 (例如變量、聲明語句,表達式等等)。
例如上面提到的類型是 NumberLiteral的節點:

{
  type: 'NumberLiteral',
  value: '2',
}

或者更復雜一點的子節點類型:

{
    type: 'CallExpression',
    name: 'substract',
    params: [...nested nodes here ...],
}

在 transfrom 這個過程中,我們可以通過增 / 刪 / 改來操作抽象語法樹結點,或者可以直接基於當前的抽象語法樹創建一個新的出來。
既然這裏我們的目標是將輸入的代碼轉換成一種新的語言風格的代碼 (Lisp -> C),所以這裏會創建一個針對新語言的全新 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'
      }]
    }]
  }]
}

遍歷流程是這樣的:

如果直接在 ast 內部操作而不是產生一個新的 ast,可能就需要介紹所有的種類的抽象。但目前來看,訪問所有結點的方法已經足夠了。
訪問 (visiting) 這個詞代表一種在對象結構內對元素進行操作的模式。

Visitors(訪問)

這裏我們可以創建一個 visitor 對象,這個對象包括一些方法用於接收不同的結點。
例如:

var visitor = {
  NumberLiteral() {},
  CallExpression() {}
};

因此當我們遍歷 ast 的時候,如果匹配到了對應 type 的結點,可以調用 visitor 中的方法來處理。

Code generate

Compiler 的最後一個階段就是 generate, 這個階段做的事情可能會和 transformation 重疊,但是代碼生成最主要的部分還是根據 AST 來輸出代碼。
Generate 有幾種不同的工作方式,有些 Compilers 會重用之前生成的 token,有些則會創建獨立的代碼表示,以便於線性輸出代碼,但接下來我們還是着重於使用之前生成好的 AST。
我們的生成器需要知道如何打印 AST 中的所有類型結點,然後遞歸調用自身,知道所有的代碼都被打印到一個很長的字符串中。

代碼實現

以上就是 Compiler 所有的部分了,但並不是所有的 Compiler 都是這樣,不同的 compiler 目的不同,所以也可能需要不同的步驟。
接下來就開始代碼的編寫:

詞法分析器 (tokenizer)

按照前面的理論分析,我們一步先進行 parser 這個階段裏面的詞法分析器 (tokenizer)。
這個函數接收一個字符串,然後將其分割成由 token 組成的數組:
ex:
(add 2 (substract 4 2)) =>[{ type: 'paren', value: '('}, ...]

因此可以編寫這樣的一個函數:

const tokenizer = (input) => {
  const tokens = [];
  let current = 0;
  while (current < input.length) {
    let char = input[current];
    if (char === '(') {
      tokens.push({
        type: 'paren',
        value: '(',
      })

      current++;
      continue;
    }

    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      })
      current ++;
      continue;
    }

    // 空格目前不需要處理
    if (/\s/.test(char)) {
      current++;
      continue;
    }

    // 處理數字
    if (/[0-9]/.test(char)) {
      let value = '';
      // 一直遍歷直到遇到非數字的字符
      while (/[0-9]/.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'number',
        value,
      })
      continue;
    }

    // 處理字符串
    if(/[a-z]/i.test(char)) {
      let value = '';

      while(/[a-z]/i.test(char)) {
        value += char;
        char = input[++current];
      }
      tokens.push({
        type: 'name',
        value,
      });

      continue;
    }

    // 如果存在匹配不上的 token 就拋錯
    throw new Error(`Unknown token: ${char}`);
  }
  return tokens;
}

語法分析器 (parser)

詞法分析器接收語法分析得到的 token 數組,然後將其轉換成 AST 結構。
例如:
[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }

const parser = (tokens) => {
  let current = 0;
  
  const walk = () => {
    let token = tokens[current];
    // 如果是 number 類型的結點,返回一個新的 ast 節點即可
    if (token.type === 'number') {
      current++;
      return {
        type: 'NumberLiteral',
        value: token.value,
      }
    }

    // 接下來檢查 CallExpression 類型,先從左圓括號開始
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {
      // 跳過左圓括號
      token = tokens[++current];
      // 首先會創建一個 CallExpression 的根節點,然後 name 設置成當前的 token.value
      // 因爲左圓括號後的 token 一定是函數名稱
      const node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      // 這裏再跳一次函數名稱
      token = tokens[++current];

      // 通過循環遍歷接下來的每個 token,直到遇到右圓括號
      // 這些 token 會成爲 `CallExpression` 的  `params`

      // 以 lisp 風格的代碼來說: (add 2 (substract 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 函數來處理
       *
       */
      while (
        token.type !== 'paren' ||
        (token.value !== ')' && token.type === 'paren')
      ) {
        node.params.push(walk());
        token = tokens[current];
      }
      current++;
      return node;
    }
    throw new Error(`Unknown token type: ${token.type}`);
  }

  const ast = {
    type: 'Program',
    body: [],
  }

  /**
   * 使用遞歸函數將結點處理進 ast.body 中
   */
  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

遍歷器 (visitors)

通過語法分析得到 ast 之後,接下來需要一個遍歷器 (visitors) 去遍歷結點。然後當遇到某個類型的結點的時候,可以調用 visitors 中對應的類型處理函數:

traverse(ast, {
  Program(node, parent) {
    // ...
  },
  
  CallExpression(node, parent) {
    // ...
  },
  
  NumberLiteral(node, parent) {
    // ...
  },
});

因此我們的代碼可以這樣寫:

const traverser = (ast, visitor) => {

  // 用於對數組中的每個元素都調用 traverseNode 函數
  const traverseArray = (array, parent) => {
    array.forEach((child) => {
      traverseNode(child, parent);
    });
  }

  // 函數接收一個 node 以及其父結點作爲參數
  // 這個結點會被傳入到 visitor 中相應的處理函數那裏
  const traverseNode = (node, parent) => {
    const method = visitor[node.type];
    if (method) {
      method(node, parent);
    }
    // 對不同的結點分開處理
    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;
        
      // 這種情況下就沒有子節點了,直接 break 出去
      case 'NumberLiteral':
        break;
      
      default:
        throw new Error(`Unknown node type: ${node.type}`);
    }
  }

  traverseNode(ast, null);
}

轉換器 (transformer)

轉換器配合上面的遍歷器來一起使用,它接收之前構建好的 ast,然後將其和 visitor 一起傳入遍歷器中,從而得到一個全新的 AST 出來。
原始的 AST 結構爲 (add 2 (subtract 4 2)):

{
  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'
      }]
    }]
  }]
}

轉換之後生成的 AST 結構爲 (add(2, subtract(4, 2))):

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

接下來我們可以這樣編寫對應的轉換器代碼:

const transformer = (ast) => {
  const newAst = {
    type: 'Program',
    body: [],
  }

  ast._context = newAst.body;

  traverser(ast, {
    // 處理 NumberLiteral 類型
    NumberLiteral: (node, parent) => {
      parent._context.push({
        type: 'NumberLiteral',
        value: node.value,
      });
    },

    // 處理 CallExpression 類型
    CallExpression: (node, parent) => {

      // 初始化一個 CallExpression 的新節點
      // 裏面放個嵌套的 Identifier 節點
      let expression = {
        type: 'CallExpression',
        callee: {
          type: 'Identifier',
          name: node.name
        },
        arguments: [],
      };

      node._context = expression.arguments;

      // 看看父節點是不是 CallExpression
      if (parent.type !== 'CallExpression') {

        // 如果不是的話,就將 CallExpression 節點包在一個叫 `ExpressionStatement` 的語句節點裏
        // 這麼做是因爲 top level 的 CallExpression 在 JavaScript 中也可以被當成是聲明語句
        expression = {
          type: 'ExpressionStatement',
          expression,
        };
      }

      // 最後我們把 CallExpression 放入父結點的 context 中
      parent._context.push(expression);
    }
  });

  return newAst;
}

代碼生成器 (code generator)

代碼生成器同樣是個遞歸函數,最後會將 AST 中的每個結點打印到一個大的字符串中:

const codeGenerator = (node) => {
  switch (node.type) {
    // 如果是 Program,則會遍歷 'body' 屬性中的每個結點
    // 並且對這些結點進行遞歸 codeGenerator,再把結果打印進新的一行裏面
    case 'Program':
      return node.body.map(codeGenerator).join('\n');
    
    // 對於 ExpressionStatement 對 expression 屬性進行遞歸調用,並加個分號
    case 'ExpressionStatement':
      return `${codeGenerator(node.expression)};`;
    
    // 對於 CallExpression 對 callee 屬性進行遞歸調用,接着加上(括號
    // 然後對 arguments 屬性進行遞歸調用,並加上)括號
    case 'CallExpression':
      return `${codeGenerator(node.callee)}(${node.arguments.map(codeGenerator).join(', ')})`;

    // 對於 Identifier,直接返回 name
    case 'Identifier':
      return node.name;
    
    // 對於 NumberLiteral,直接返回 value
    case 'NumberLiteral':
      return node.value;
    
    default:
      throw new Error(`Unknown node type: ${node.type}`);
  }
}

編譯器 (Compiler)

到這一步,基本上所有的流程就已經完成了,我們可以創建一個 compiler 函數,通過調用上面的函數就可以完成整個 compiler 的工作了:

  1. input => tokenizer => tokens

  2. tokens => parser => ast

  3. ast => transformer => newAst

  4. newAst => generator => output

代碼只需要以下簡單幾步即可:

const compiler = (input) => {
  const tokens = tokenizer(input);
  const ast = parser(tokens);
  const newAst = transformer(ast);
  
  return codeGenerator(newAst);
}

我們可以輸入前面的幾組測試例子,能保證得到的結果是正確的。

總結

至此一個 tiny-compiler 就被造出來了,babel 的編譯流程也是基於此來完成,因爲 babel 本身是個 source to source 的 compiler,整個流程也是分爲 parser -> transform -> code generate 這三個步驟完成,具體可以參考 https://babeljs.io/docs/en/#babel-is-a-javascript-compiler

希望本文能幫助讀者理解相關編譯工具的編譯流程。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/LRH_taDz7OC_uzj0ySNKLQ