基于JS怎么實現一個小型編譯器

這篇文章主要講解了“基于JS怎么實現一個小型編譯器”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“基于JS怎么實現一個小型編譯器”吧！

前言

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

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

這就大概是這次 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);
}

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

感謝各位的閱讀，以上就是“基于JS怎么實現一個小型編譯器”的內容了，經過本文的學習后，相信大家對基于JS怎么實現一個小型編譯器這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！