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

2022-04-16 13:00:23

前言

the-super-tiny-compiler 是一個程式碼行數只有不到 200 行的超級小型的 compiler，但通過這個 compiler 能學習到最基礎的 compile 原理，包括 babel 也是基於這樣的原理來進行開發的。

倉庫本身的例子是將一組 lisp 風格的函數語法編譯成了 C 風格的函數語法，舉例子來說:

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

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

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

parse 主要是將原始碼轉換成一種更抽象的程式碼錶達
transform 則是將上面抽象的表達進行任意 compiler 想進行的操作
code generate 將 transform 處理之後的程式碼生成一種新的程式碼

Parse

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

詞法分析將原始碼根據表達切分一個個的 tokens，tokens 是一組用來描述單獨語法的物件，可以是 numbers、labels、punctuation、operators 等
語法分析則是將詞法分析生成的 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'
      }]
    }]
  }]
}

遍歷流程是這樣的:

Program - 從 AST 的頂結點開始
CallExpression (add) - Program 的第一個子元素
NumberLiteral (2) - CallExpression (add) 的第一個子元素
CallExpression (subtract) - CallExpression (add) 的第二個子元素
NumberLiteral (4) - CallExpression (subtract) 的第一個子元素
NumberLiteral (2) - CallExpression (subtract) 的第二個子元素

如果直接在 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 = () => {
    const 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 節點
      const 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 的工作了:

input => tokenizer => tokens
tokens => parser => ast
ast => transformer => newAst
newAst => generator => output

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

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

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